scientific article; zbMATH DE number 7009611
From MaRDI portal
DOI10.4086/toc.2018.v014a012zbMath1412.68071OpenAlexW2897992026MaRDI QIDQ4612476
Srikanth Srinivasan, Swastik Kopparty
Publication date: 31 January 2019
Published in: Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.4086/toc.2018.v014a012
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Covering symmetric sets of the Boolean cube by affine hyperplanes, New algorithms and lower bounds for circuits with linear threshold gates, Parity helps to compute majority, Fourier bounds and pseudorandom generators for product tests, Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On approximate majority and probabilistic time
- \(k\)-subgraph isomorphism on \(\text{AC}^{0}\) circuits
- Linear-size constant-depth polylog-threshold circuits
- The expressive power of voting polynomials
- A complex-number Fourier technique for lower bounds on the mod-\(m\) degree
- Hilbert functions and the finite degree Zariski closure in finite field combinatorial geometry
- Mining circuit lower bound proofs for meta-algorithms
- Certifying polynomials for AC^0(parity) circuits, with applications
- Parity, circuits, and the polynomial-time hierarchy
- Algebraic immunity for cryptographically significant Boolean functions: analysis and construction
- Polylogarithmic independence fools AC 0 circuits
- 30th Conference on Computational Complexity (CCC 2015)
- New algorithms and lower bounds for circuits with linear threshold gates
- Computational Complexity
- Learning algorithms from natural proofs
- Natural proofs
