On polynomial approximations to AC
From MaRDI portal
Publication:4633319
DOI10.1002/rsa.20786zbMath1421.68055OpenAlexW2345122596MaRDI QIDQ4633319
Prahladh Harsha, Srikanth Srinivasan
Publication date: 2 May 2019
Published in: Random Structures & Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/rsa.20786
constant-depth circuitsanti-concentration for polynomialsbounded independenceprobabilistic polynomials
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (8)
Approximate Degree in Classical and Quantum Computing ⋮ On the probabilistic degree of OR over the reals ⋮ Paradigms for Unconditional Pseudorandom Generators ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Near-optimal pseudorandom generators for constant-depth read-once formulas ⋮ Algorithms and lower bounds for de morgan formulas of low-communication leaf gates ⋮ Interactive proofs for social graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy
- Random symmetric matrices are almost surely nonsingular.
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- A lower bound for radio broadcast
- Hardness vs randomness
- On deterministic approximation of DNF
- Anti-concentration for polynomials of independent random variables
- Real Advantage
- Certifying polynomials for AC^0(parity) circuits, with applications
- Constant depth circuits, Fourier transform, and learnability
- Polylogarithmic independence fools AC 0 circuits
- Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
- 30th Conference on Computational Complexity (CCC 2015)
- New algorithms and lower bounds for circuits with linear threshold gates
- Analysis of Boolean Functions
- On the Correlation of Parity and Small-Depth Circuits
- On a lemma of Littlewood and Offord
This page was built for publication: On polynomial approximations to AC
