scientific article; zbMATH DE number 7378647
From MaRDI portal
Publication:5009530
DOI10.4230/LIPIcs.APPROX-RANDOM.2018.35MaRDI QIDQ5009530
Publication date: 4 August 2021
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Related Items (5)
Approximate Degree in Classical and Quantum Computing ⋮ Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\) ⋮ Approximate Degree, Secret Sharing, and Concentration Phenomena ⋮ Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$ ⋮ Unnamed Item
Cites Work
- 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
- Computing Boolean functions by polynomials and threshold circuits
- Perceptrons, PP, and the polynomial hierarchy
- Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
- PP is closed under intersection
- Dual lower bounds for approximate degree and Markov-Bernstein inequalities
- Threshold circuits of bounded depth
- The Pattern Matrix Method
- Hardness Amplification and the Approximate Degree of Constant-Depth Circuits
- Quantum lower bounds for the collision and the element distinctness problems
- A Uniform Lower Bound on Weights of Perceptrons
- Separating ${AC}^0$ from Depth-2 Majority Circuits
- The Power of Asymmetry in Constant-Depth Circuits
- The Landscape of Communication Complexity Classes.
- 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
- Lower Bounds for Quantum Communication Complexity
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication:
