Satisfying degree-d equations of GF
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)
We study the problem where we are given a system of polynomial equations defined by multivariate polynomials over GF 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
Computer and Information Science
IdentifiersURN: urn:nbn:se:kth:diva-63053DOI: 10.1007/978-3-642-22935-0_21ScopusID: 2-s2.0-80052373840ISBN: 978-364222934-3OAI: oai:DiVA.org:kth-63053DiVA: 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 201409162012-01-212012-01-212014-09-16Bibliographically approved