Low-degree test with polynomially small error

DOI10.1007/S00037-016-0149-4MaRDI QIDQ2410685zbMATH OpenOpenAlexFDO

Authors Dana Moshkovitz

Publication date 18 October 2017

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00037-016-0149-4

zbMATH Keywords

direct productPCPlow-degree testingsliding scale conjecture

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Sub-Constant Error Low Degree Test of Almost-Linear Size
• Sub-constant error low degree test of almost-linear size
• scientific article; zbMATH DE number 7758310
• Lower bounds for linear degeneracy testing
• Lower bounds for linear degeneracy testing
• Robust testing of low dimensional functions
• Approximate testing with relative error
• A lower bound on the probability of error in multihypothesis testing
• Testing Low Degree Trigonometric Polynomials
• Efficient multivariate low-degree tests via interactive oracle proofs of proximity for polynomial codes

Cites work

• scientific article; zbMATH DE number 3167429 (Why is no real title available?)
• scientific article; zbMATH DE number 1263222 (Why is no real title available?)
• scientific article; zbMATH DE number 1097580 (Why is no real title available?)
• scientific article; zbMATH DE number 1559563 (Why is no real title available?)
• scientific article; zbMATH DE number 1405671 (Why is no real title available?)
• A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem
• A no-go theorem for derandomized parallel repetition: beyond Feige-Kilian
• Analytical approach to parallel repetition
• Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
• Composition of Low-Error 2-Query PCPs Using Decodable PCPs
• Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs
• Efficient probabilistically checkable proofs and applications to approximations
• Entropy waves, the zig-zag graph product, and new constant-degree expanders
• Expanders that beat the eigenvalue bound
• Improved low-degree testing and its applications
• New direct-product testers and 2-query PCPs
• Non-deterministic exponential time has two-prover interactive protocols
• PCP characterizations of NP: toward a polynomially-small error-probability
• Probabilistic checking of proofs
• Proof verification and the hardness of approximation problems
• Randomness conductors and constant-degree lossless expanders
• Randomness-efficient low degree tests and short PCPs via epsilon-biased sets
• Robust Characterizations of Polynomials with Applications to Program Testing
• Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
• Small value parallel repetition for general games
• Sub-Constant Error Low Degree Test of Almost-Linear Size
• Two-query PCP with subconstant error

Cited in

(6)

• Sub-constant error low degree test of almost-linear size
• ETH-hardness of approximating 2-CSPs and directed Steiner network
• Sub-Constant Error Low Degree Test of Almost-Linear Size
• Lower bounds for linear degeneracy testing
• A high dimensional Goldreich-Levin theorem
• Improved low-degree testing and its applications

This page was built for publication: Low-degree test with polynomially small error

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