Direct sum testing (extended abstract)

DOI10.1145/2688073.2688078MaRDI QIDQ2989047zbMATH OpenOpenAlexFDO

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

Publication date 19 May 2017

Published in Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2688073.2688078

zbMATH Keywords

direct sumlinearity testingproperty testing

Mathematics Subject Classification ID

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

Recommendations

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

Cited in

(8)

• Toward a general direct product testing theorem
• Towards a general direct product testing theorem
• Exponentially small soundness for the direct product Z-test
• Optimization with uniform size queries
• Direct sum testing
• Testing Odd Direct Sums Using High Dimensional Expanders
• On approximability of satisfiable k-CSPs. III
• Tight characterizations for preprocessing against cryptographic salting

This page was built for publication: Direct sum testing (extended abstract)

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