The coin problem for product tests

DOI10.1145/3201787MaRDI QIDQ4973882zbMATH OpenOpenAlexWikidataFDO

Authors Chin Ho Lee, Emanuele Viola

Publication date 6 December 2019

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

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

zbMATH Keywords

coin problemproduct test

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Other nonclassical models of computation (68Q09)

Recommendations

• Coin Theorems and the Fourier Expansion
• Two sides of the coin problem
• Testing non-uniform \(k\)-wise independent distributions over product spaces (extended abstract)
• Robust characterizations of k-wise independence over product spaces and related testing results
• Bounded independence versus symmetric tests

Cited in

(4)

• A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus]$ via the Coin Problem
• Fourier bounds and pseudorandom generators for product tests
• Depth-\(d\) threshold circuits vs. depth-\((d+1)\) and-or trees
• Optimal explicit small-depth formulas for the coin problem

This page was built for publication: The coin problem for product tests

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