Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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, Published 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.
Series
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), ISSN 0302-9743
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:kth:diva-63053DOI: 10.1007/978-3-642-22935-0_21Scopus ID: 2-s2.0-80052373840ISBN: 9783642229343 (print)OAI: oai:DiVA.org:kth-63053DiVA: diva2:481572
Conference
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
Note

QC 20140916

Available from: 2012-01-21 Created: 2012-01-21 Last updated: 2017-03-28Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Authority records BETA

Håstad, Johan

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

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 47 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf