Agreement tests on graphs and hypergraphs

DOI10.1137/21M1397684MaRDI QIDQ7013987zbMATH OpenFDO

Authors Irit Dinur, Yuval Filmus, Prahladh Harsha

Publication date 11 March 2025

Published in SIAM Journal on Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1137/21M1397684

zbMATH Keywords

agreement testsagreement theoremdirect product testlow-degree testingp-biased distributionPCP

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20)

Cites work

• A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem
• A Parallel Repetition Theorem
• Agreement testing theorems on layered set systems
• Analyzing Boolean functions on the biased hypercube via higher-dimensional agreement tests
• Asymptotically good Quantum and locally testable classical LDPC codes
• Direct sum testing
• High dimensional expanders imply agreement expanders
• Linearity testing in characteristic two
• Locally testable codes with constant rate, distance, and locality
• New direct-product testers and 2-query PCPs
• Optimal testing of Reed-Muller codes
• Probabilistic checking of proofs
• Proof verification and the hardness of approximation problems
• Property testing and its connection to learning and approximation
• Pseudorandom sets in Grassmann graph have near-perfect expansion
• Robust Characterizations of Polynomials with Applications to Program Testing
• Self-testing/correcting with applications to numerical problems
• Sparse juntas on the biased hypercube
• Testing Reed–Muller Codes
• Towards a proof of the 2-to-1 games conjecture?

This page was built for publication: Agreement tests on graphs and hypergraphs

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