Two sides of the coin problem

DOI10.4230/LIPICS.APPROX-RANDOM.2014.618MaRDI QIDQ2969650zbMATH OpenOpenAlexFDO

Authors Gil Cohen, Anat Ganor, Ran Raz

Publication date 22 March 2017

Full work available at URL https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.618

zbMATH Keywords

read-once branching programsbounded depth circuitscoin problemSantha-Vazirani sources

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• A fixed-depth size-hierarchy theorem for AC ⁰ [⊕] via the coin problem
• Coin Theorems and the Fourier Expansion
• The Biased Coin Problem
• Coin flipping of \textit{any} constant bias implies one-way functions
• Optimal coin flipping

Cited in

(9)

• A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus]$ via the Coin Problem
• Fourier bounds and pseudorandom generators for product tests
• A robust version of Hegedűs's lemma, with applications
• Comparing computational entropies below majority (or: when is the dense model theorem false?)
• Query complexity lower bounds for local list-decoding and hard-core predicates (even for small rate and huge lists)
• The coin problem for product tests
• An instance-based algorithm for deciding the bias of a coin
• 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: Two sides of the coin problem

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