Toward a general direct product testing theorem

DOI10.1145/3369939MaRDI QIDQ5053041zbMATH OpenOpenAlexWikidataFDO

Authors Elazar Goldenberg, C. S. Karthik

Publication date 5 December 2022

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

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

zbMATH Keywords

derandomizationdirect productJohnson graphPCPproperty testingRamanujan complex

Mathematics Subject Classification ID

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

Recommendations

• Direct sum testing (extended abstract)
• Direct sum testing
• New direct-product testers and 2-query PCPs
• Exponentially small soundness for the direct product Z-test
• New direct-product testers and 2-query PCPs

Cited in

(6)

• Direct sum testing (extended abstract)
• Towards a general direct product testing theorem
• Exponentially small soundness for the direct product Z-test
• Direct sum testing
• Testing Odd Direct Sums Using High Dimensional Expanders
• scientific article; zbMATH DE number 7754309 (Why is no real title available?)

This page was built for publication: Toward a general direct product testing theorem

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