Optimal explicit small-depth formulas for the coin problem

Cites work

$\mathrm{AC}^0[p]$ lower bounds against MCSP via the coin problem
$\Sigma_ 1^ 1$-formulae on finite structures
A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus]$ via the Coin Problem
Amplification by Read-Once Formulas
Analysis of Boolean Functions
Approximation by DNF: Examples and Counterexamples
Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators
Bounds on the Size of Small Depth Circuits for Approximating Majority
Coin Theorems and the Fourier Expansion
Computational Complexity
Derandomization beyond connectivity: undirected Laplacian systems in nearly logarithmic space
Derandomized graph products
Derandomizing Homomorphism Testing in General Groups
Deterministic coupon collection and better strong dispersers
Efficient multiparty protocols via log-depth threshold formulae. (Extended abstract)
Eigenvalues and expansion of regular graphs
Entropy waves, the zig-zag graph product, and new constant-degree expanders
Expander graphs and their applications
Expanders, randomness, or time versus space
Extracting all the randomness and reducing the error in Trevisan's extractors
Hardness Amplification Proofs Require Majority
Hardness vs randomness
scientific article; zbMATH DE number 7561729 (Why is no real title available?)
scientific article; zbMATH DE number 7166711 (Why is no real title available?)
scientific article; zbMATH DE number 5485586 (Why is no real title available?)
Monotone Circuits for the Majority Function
New Algorithms for Finding Irreducible Polynomials Over Finite Fields
On the distribution of the number of roots of polynomials and explicit weak designs
On the shrinkage exponent for read-once formulae
Parity helps to compute majority
Poisson approximation for large deviations
Pseudorandom Generators from the Second Fourier Level and Applications to AC0 with Parity Gates
Ramanujan graphs
Randomness buys depth for approximate counting
Randomness-efficient low degree tests and short PCPs via epsilon-biased sets
Short monotone formulae for the majority function
Simple Constructions of Almost k-wise Independent Random Variables
Small-Bias Probability Spaces: Efficient Constructions and Applications
The average sensitivity of bounded-depth formulas
The coin problem for product tests
Two sides of the coin problem

This page was built for publication: Optimal explicit small-depth formulas for the coin problem

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