Direct sum testing

DOI10.1137/16M1061655MaRDI QIDQ5348457zbMATH OpenOpenAlexFDO

Authors Roee David, Irit Dinur, Elazar Goldenberg, Guy Kindler, Igor Shinkar

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

zbMATH Keywords

direct sumslinearity testingproperty testing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Recommendations

• Direct sum testing (extended abstract)
• Toward a general direct product testing theorem
• New direct-product testers and 2-query PCPs
• Tight bounds for testing k-linearity
• Algebraic testing and weight distributions of codes.

Cites work

• A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem
• A Parallel Repetition Theorem
• An orthogonal basis for functions over a slice of the Boolean hypercube
• Approximation resistance from pairwise independent subgroups
• Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
• Breaking the -soundness bound of the linearity test over GF(2)
• Derandomized parallel repetition via structured PCPs
• Derandomizing homomorphism testing in general groups
• Efficient probabilistically checkable proofs and applications to approximations
• Hardness amplification within NP
• Homological connectivity of random 2-complexes
• scientific article; zbMATH DE number 1246230 (Why is no real title available?)
• scientific article; zbMATH DE number 830463 (Why is no real title available?)
• Linearity testing in characteristic two
• New direct-product testers and 2-query PCPs
• Non‐Abelian homomorphism testing, and distributions close to their self‐convolutions
• On Yao's XOR-lemma
• Optimal testing of Reed-Muller codes
• Probabilistic checking of proofs
• Proof verification and the hardness of approximation problems
• Pseudorandom generators without the XOR lemma
• Randomness-efficient low degree tests and short PCPs via epsilon-biased sets
• Self-testing/correcting with applications to numerical problems
• Testing Reed–Muller Codes
• The PCP theorem by gap amplification
• The structure of winning strategies in parallel repetition games
• Tolerant Linearity Testing and Locally Testable Codes
• Uniform direct product theorems: simplified, optimized, and derandomized
• Using Nondeterminism to Amplify Hardness

Cited in

(11)

• Property testing and expansion in cubical complexes
• Direct sum testing (extended abstract)
• Toward a general direct product testing theorem
• Towards a general direct product testing theorem
• Exponentially small soundness for the direct product Z-test
• scientific article; zbMATH DE number 7250157 (Why is no real title available?)
• scientific article; zbMATH DE number 7650107 (Why is no real title available?)
• Testing Odd Direct Sums Using High Dimensional Expanders
• Small-set expansion in the Johnson graph
• Agreement tests on graphs and hypergraphs
• A near-optimal polynomial distance lemma over Boolean slices

This page was built for publication: Direct sum testing

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