scientific article; zbMATH DE number 7413502
DOI10.4086/toc.2021.v017a007OpenAlexW3200234314MaRDI QIDQ5158501
Publication date: 25 October 2021
Published in: Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.4086/toc.2021.v017a007
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
polynomial approximationsurjectivitydiscrepancypolynomial methodapproximate degreedual polynomialspolynomial threshold
Computational learning theory (68Q32) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Theory of computing (68Qxx)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Probabilistic communication complexity
- On approximate majority and probabilistic time
- Perceptrons of large weight
- On the computational power of Boolean decision lists
- Majority gates vs. general weighted threshold gates
- On the computational power of depth-2 circuits with threshold and modulo gates
- Inclusion-exclusion: exact and approximate
- Near-optimal secret sharing and error correcting codes in \(\mathsf{AC}^0\)
- A linear lower bound on the unbounded error probabilistic communication complexity.
- Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
- Dual lower bounds for approximate degree and Markov-Bernstein inequalities
- Threshold circuits of bounded depth
- The Sign-Rank of AC$^0$
- The Pattern Matrix Method
- Quantum lower bounds for the collision and the element distinctness problems
- Learning Complexity vs Communication Complexity
- Separating ${AC}^0$ from Depth-2 Majority Circuits
- Breaking the Minsky--Papert Barrier for Constant-Depth Circuits
- The Power of Asymmetry in Constant-Depth Circuits
- Improved Bounds on the Sign-Rank of AC^0
- Strong Direct Product Theorems for Quantum Communication and Query Complexity
- On the Power of Statistical Zero Knowledge
- The Intersection of Two Halfspaces Has High Threshold Degree
- Lower Bounds for Quantum Communication Complexity
- New degree bounds for polynomial threshold functions
- Evolvability
This page was built for publication:
