Sparsity lower bounds for probabilistic polynomials

Cites work

\(n^{{\Omega{}}(\log{} n)}\) lower bounds on the size of depth-3 threshold circuits with AND gates at the bottom
A new algorithm for optimal 2-constraint satisfaction and its implications
Beating brute force for systems of polynomial equations over finite fields
Certifying polynomials for AC^0(parity) circuits, with applications
Communication lower bounds using directional derivatives
Completeness for first-order properties on sparse structures with algorithmic applications
Computing Boolean functions by polynomials and threshold circuits
Correlation bounds for poly-size \(\mathrm{AC}^0\) circuits with \(n^{1 - o(1)}\) symmetric gates
Deterministic APSP, orthogonal vectors, and more: quickly derandomizing Razborov-Smolensky
Faster all-pairs shortest paths via circuit complexity
Faster Online Matrix-Vector Multiplication
Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
Matrix rigidity and the Croot-Lev-Pach lemma
More applications of the polynomial method to algorithm design
Multiparty communication complexity and threshold circuit size of AC^0
On Improved Degree Lower Bounds for Polynomial Approximation.
On polynomial approximations to \(\mathrm{AC}^0\)
On the complexity of k-SAT
On the computational power of depth-2 circuits with threshold and modulo gates
On the degree of Boolean functions as real polynomials
Polynomial representations of threshold functions and algorithmic applications
Polynomial threshold functions and Boolean threshold circuits
Polynomials that sign represent parity and Descartes' rule of signs
Probabilistic polynomials and Hamming nearest neighbors
Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy
Probabilistic rank and matrix rigidity
Progression-free sets in \(\mathbb{Z}_4^n\) are exponentially small
Representing Boolean functions as polynomials modulo composite numbers
Subquadratic algorithms for succinct stable matching
The complexity of satisfiability of small depth circuits
The expressive power of voting polynomials
The polynomial method in circuit complexity applied to algorithm design (invited talk)

This page was built for publication: Sparsity lower bounds for probabilistic polynomials

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