Satisfying Degree-d Equations over GF[2] n

DOI10.1007/978-3-642-22935-0_21zbMath1343.68312OpenAlexW1559728639WikidataQ56958844 ScholiaQ56958844MaRDI QIDQ3088098

Johan T. Håstad

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) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (2)

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

Cites Work

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

This page was built for publication: Satisfying Degree-d Equations over GF[2] n