Cube vs. Cube Low Degree Test.

DOI10.4230/LIPIcs.ITCS.2017.40zbMath1402.68190arXiv1612.07491OpenAlexW2963493303MaRDI QIDQ4638094

Irit Dinur, Amey Bhangale, Navon Inbal Livni

Publication date: 3 May 2018

Full work available at URL: https://arxiv.org/abs/1612.07491

zbMATH Keywords

probabilistically checkable proofslocally testable codeslow-degree test

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Randomized algorithms (68W20)

Related Items (2)

Unnamed Item ⋮ Efficient multivariate low-degree tests via interactive oracle proofs of proximity for polynomial codes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sub-Constant Error Low Degree Test of Almost-Linear Size
• Free Bits, PCPs, and Nonapproximability---Towards Tight Results
• Robust Characterizations of Polynomials with Applications to Program Testing
• New Direct-Product Testers and 2-Query PCPs
• A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem
• Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem

This page was built for publication: Cube vs. Cube Low Degree Test.