New direct sum tests

DOI10.4230/LIPICS.ITCS.2025.94MaRDI QIDQ7296742zbMATH OpenFDO

Authors Alek Westover, Edward Yu, Kai Zhe Zheng

Publication date 14 July 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ITCS.2025.94

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem
• Adversarial low degree testing
• Agreement testing theorems on layered set systems
• Algebraic property testing: the role of invariance
• Approximation Resistance from Pairwise-Independent Subgroups
• Assignment testers: towards a combinatorial proof of the PCP-theorem
• Direct sum testing (extended abstract)
• scientific article; zbMATH DE number 1559563 (Why is no real title available?)
• scientific article; zbMATH DE number 7650107 (Why is no real title available?)
• scientific article; zbMATH DE number 7829322 (Why is no real title available?)
• Local decoding and testing of polynomials over grids
• Low-degree testing over grids
• New direct-product testers and 2-query PCPs
• Optimal testing of Reed-Muller codes
• Property testing with online adversaries
• Spreading of sets in product spaces and hypercontraction of the Markov operator
• The PCP theorem by gap amplification

This page was built for publication: New direct sum tests

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