Lower bounds and separations for torus polynomials
From MaRDI portal
Cites work
- \(n^{{\Omega{}}(\log{} n)}\) lower bounds on the size of depth-3 threshold circuits with AND gates at the bottom
- Almost-everywhere circuit lower bounds from non-trivial derandomization
- An average-case lower bound against \(\mathsf{ACC}^0\)
- Approximate Degree in Classical and Quantum Computing
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- Bounds for small-error and zero-error quantum algorithms
- Circuit lower bounds for nondeterministic quasi-polytime from a new easy witness lemma
- Dual lower bounds for approximate degree and Markov-Bernstein inequalities
- Geometry of numbers. In two parts, II (last part).
- Majority vs. approximate linear sum and average-case complexity below NC^1
- New lower bounds and derandomization for ACC, and a derandomization-centric view on the algorithmic method
- Non-deterministic quasi-polynomial time is average-case hard for ACC circuits
- Nonuniform ACC circuit lower bounds
- On ACC
- On Siegel's lemma
- On the degree of Boolean functions as real polynomials
- On the power of small-depth threshold circuits
- The power of the middle bit of a \(\#\)P function
- Torus polynomials: an algebraic approach to ACC lower bounds
- Upper bound for torus polynomials
This page was built for publication: Lower bounds and separations for torus polynomials
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7445616)