Satisfying degree-d equations over GF[2]^n

DOI10.1007/978-3-642-22935-0_21MaRDI QIDQ3088098zbMATH OpenOpenAlexWikidataFDO

Authors Johan Hastad

Publication date 17 August 2011

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-22935-0_21

Mathematics Subject Classification ID

Polynomials over finite fields (11T06) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20) Approximation algorithms (68W25)

Recommendations

• Satisfying degree-\(d\) equations over \(\mathrm{GF}[2]^n\)
• On the hardness of approximating max-satisfy
• A well-characterized approximation problem
• Is constraint satisfaction over two variables always easy?
• The Nonapproximability of Non-Boolean Predicates

Cites work

• Approximation resistant predicates from pairwise independence
• Free Bits, PCPs, and Nonapproximability---Towards Tight Results
• On the weight structure of Reed-Muller codes
• Probabilistic checking of proofs
• Proof verification and the hardness of approximation problems
• Some optimal inapproximability results
• Two-query PCP with subconstant error

Cited in

(5)

• Minimal achievable approximation ratio for MAX-MQ in finite fields
• Satisfying degree-\(d\) equations over \(\mathrm{GF}[2]^n\)
• A new method for solving polynomial systems with noise over \(\mathbb{F}_2\) and its applications in cold boot key recovery
• Solving polynomial systems with noise over \(\mathbb{F}_2\): revisited
• A well-characterized approximation problem

This page was built for publication: Satisfying degree-\(d\) equations over \(\mathrm{GF}[2]^{n}\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3088098)