Change search
ReferencesLink to record
Permanent link

Direct link
Satisfying degree-d equations of GF[2]
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.ORCID iD: 0000-0002-5379-345X
2011 (English)In: Proceedings of the 14th international workshop and 15th international conference on Approximation, randomization, and combinatorial optimization:: algorithms and techniques, 2011, 242-253 p.Conference paper (Refereed)
Abstract [en]

We study the problem where we are given a system of polynomial equations defined by multivariate polynomials over GF[2] of fixed constant degree d > 1 and the aim is to satisfy the maximal number of equations. A random assignment approximates this problem within a factor 2-d and we prove that for any ε > 0, it is NP-hard to obtain a ratio 2-d + ε. When considering instances that are perfectly satisfiable we give a probabilistic polynomial time algorithm that, with high probability, satisfies a fraction 21-d - 21-2d and we prove that it is NP-hard to do better by an arbitrarily small constant. The hardness results are proved in the form of inapproximability results of Max-CSPs where the predicate in question has the desired form and we give some immediate results on approximation resistance of some predicates.

Place, publisher, year, edition, pages
2011. 242-253 p.
, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), ISSN 03029743
National Category
Computer and Information Science
URN: urn:nbn:se:kth:diva-63053DOI: 10.1007/978-3-642-22935-0_21ScopusID: 2-s2.0-80052373840ISBN: 978-364222934-3OAI: diva2:481572
14th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2011 and the 15th International Workshop on Randomization and Computation, RANDOM 2011; Princeton, NJ; United States; 17-19 August 2011

QC 20140916

Available from: 2012-01-21 Created: 2012-01-21 Last updated: 2014-09-16Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Håstad, Johan
By organisation
Theoretical Computer Science, TCS
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 28 hits
ReferencesLink to record
Permanent link

Direct link