Two sides of the coin problem

DOI10.4230/LIPICS.APPROX-RANDOM.2014.618zbMATH Open1360.68460OpenAlexW2240695625MaRDI QIDQ2969650FDOQ2969650

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

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

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)

Cited In (7)

• 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
• 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)