scientific article; zbMATH DE number 7650122
From MaRDI portal
Publication:5875514
DOI10.4230/LIPIcs.APPROX-RANDOM.2019.55MaRDI QIDQ5875514
Publication date: 3 February 2023
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
discrepancysecret sharingpolynomial approximationsthreshold circuitsapproximate degreemargin complexity
Related Items (2)
Approximate Degree in Classical and Quantum Computing ⋮ Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Probabilistic communication complexity
- On the computational power of depth-2 circuits with threshold and modulo gates
- Near-optimal secret sharing and error correcting codes in \(\mathsf{AC}^0\)
- Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
- Dual lower bounds for approximate degree and Markov-Bernstein inequalities
- Bounded Indistinguishability and the Complexity of Recovering Secrets
- The Sign-Rank of AC$^0$
- The Pattern Matrix Method
- Hardness Amplification and the Approximate Degree of Constant-Depth Circuits
- Perceptrons of Large Weight
- Learning Complexity vs Communication Complexity
- Separating ${AC}^0$ from Depth-2 Majority 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
- Near-optimal lower bounds on the threshold degree and sign-rank of AC 0
- The polynomial method strikes back: tight quantum query bounds via dual polynomials
- Breaking the minsky-papert barrier for constant-depth circuits
- The Intersection of Two Halfspaces Has High Threshold Degree
- New degree bounds for polynomial threshold functions
- Evolvability
This page was built for publication:
