Direct Sum Testing
From MaRDI portal
Publication:5348457
DOI10.1137/16M1061655zbMath1371.68322OpenAlexW2741519875MaRDI QIDQ5348457
Guy Kindler, Irit Dinur, Roee David, Igor Shinkar, Elazar Goldenberg
Publication date: 16 August 2017
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/16m1061655
Related Items (4)
Property testing and expansion in cubical complexes ⋮ Unnamed Item ⋮ Testing Odd Direct Sums Using High Dimensional Expanders ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Derandomized parallel repetition via structured PCPs
- Homological connectivity of random 2-complexes
- Self-testing/correcting with applications to numerical problems
- An orthogonal basis for functions over a slice of the Boolean hypercube
- Breaking the $\epsilon$-Soundness Bound of the Linearity Test over GF(2)
- On Yao’s XOR-Lemma
- Linearity testing in characteristic two
- Proof verification and the hardness of approximation problems
- Testing Reed–Muller Codes
- Derandomizing homomorphism testing in general groups
- Randomness-efficient low degree tests and short PCPs via epsilon-biased sets
- Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized
- The Structure of Winning Strategies in Parallel Repetition Games
- Tolerant Linearity Testing and Locally Testable Codes
- Probabilistic checking of proofs
- A Parallel Repetition Theorem
- Optimal Testing of Reed-Muller Codes
- A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem
- New direct-product testers and 2-query PCPs
- Efficient probabilistically checkable proofs and applications to approximations
- Non‐Abelian homomorphism testing, and distributions close to their self‐convolutions
- Using Nondeterminism to Amplify Hardness
- Approximation resistance from pairwise independent subgroups
- Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
- The PCP theorem by gap amplification
- Hardness amplification within NP
- Pseudorandom generators without the XOR lemma
This page was built for publication: Direct Sum Testing
