Bounds on the Size of Small Depth Circuits for Approximating Majority
From MaRDI portal
Publication:3638024
DOI10.1007/978-3-642-02927-1_7zbMath1248.68193OpenAlexW1623626896MaRDI QIDQ3638024
Publication date: 14 July 2009
Published in: Automata, Languages and Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-02927-1_7
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Unnamed Item, Randomness buys depth for approximate counting, Advice Coins for Classical and Quantum Computation, A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus$ via the Coin Problem], Parity helps to compute majority, Fourier bounds and pseudorandom generators for product tests