Testing Odd Direct Sums Using High Dimensional Expanders

DOI10.4230/LIPICS.APPROX-RANDOM.2019.50MaRDI QIDQ5875508zbMATH OpenOpenAlexFDO

Authors Roy Gotlib, Tali Kaufman

Publication date 3 February 2023

Full work available at URL http://drops.dagstuhl.de/opus/volltexte/2019/11265/pdf/LIPIcs-APPROX-RANDOM-2019-50.pdf

zbMATH Keywords

direct sumhigh dimensional expandersproperty testing

Mathematics Subject Classification ID

Randomized algorithms (68W20) Approximation algorithms (68W25) Combinatorial optimization (90C27)

Recommendations

• An efficient deterministic test for Kloosterman sum zeros
• Direct sum testing (extended abstract)
• On the Validity of the Direct Sum Conjecture
• On the direct sum conjecture
• Counterexamples to Strassen's direct sum conjecture
• Towards a general direct product testing theorem
• Sum-product estimates via directed expanders
• Toward a general direct product testing theorem
• A polynomial time test to detect numbers with many exceptional points
• Hyperkloosterman sums revisited

Cites work

• Direct sum testing
• High dimensional expanders and property testing
• High dimensional random walks and colorful expansion
• scientific article; zbMATH DE number 2156274 (Why is no real title available?)
• Linearity testing in characteristic two
• Ramanujan complexes of type \(\widetilde A_d\)
• Randomness-efficient low degree tests and short PCPs via epsilon-biased sets
• Self-testing/correcting with applications to numerical problems
• The PCP theorem by gap amplification

Cited in

(2)

• High dimensional expanders and property testing
• Explicit SoS lower bounds from high-dimensional expanders

This page was built for publication: Testing Odd Direct Sums Using High Dimensional Expanders

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