Breaking the Minsky--Papert Barrier for Constant-Depth Circuits

DOI10.1137/15M1015704zbMath1402.68108OpenAlexW2898737300MaRDI QIDQ4554070

Alexander A. Sherstov

Publication date: 7 November 2018

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/15m1015704

zbMATH Keywords

computational learning theorypolynomial threshold functionspolynomial representations of Boolean functionsthreshold degreepolynomial approximation theorycommunication complexity theory

Mathematics Subject Classification ID

Related Items (5)

Approximate Degree in Classical and Quantum Computing ⋮ Unnamed Item ⋮ Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$ ⋮ Unnamed Item ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Learning intersections and thresholds of halfspaces
• Disjointness is hard in the multiparty number-on-the-forehead model
• On the computational power of Boolean decision lists
• Unconditional lower bounds for learning intersections of halfspaces
• 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
• The expressive power of voting polynomials
• Approximating threshold circuits by rational functions
• On the degree of Boolean functions as real polynomials
• Perceptrons, PP, and the polynomial hierarchy
• An efficient membership-query algorithm for learning DNF with respect to the uniform distribution
• 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
• The Multiparty Communication Complexity of Set Disjointness
• Multiparty Communication Complexity and Threshold Circuit Size of $\ensuremath{\sfAC}^0$
• The Sign-Rank of AC$^0$
• Any AND-OR Formula of Size N Can Be Evaluated in Time $N^{1/2+o(1)}$ on a Quantum Computer
• The Pattern Matrix Method
• Hardness Amplification and the Approximate Degree of Constant-Depth Circuits
• Harmonic Analysis of Polynomial Threshold Functions
• Quantum lower bounds for the collision and the element distinctness problems
• Perceptrons of Large Weight
• A Uniform Lower Bound on Weights of Perceptrons
• Separating ${AC}^0$ from Depth-2 Majority Circuits
• Polynomial Threshold Functions, $AC^0 $ Functions, and Spectral Norms
• On the Size of Weights for Threshold Gates
• Rational approximation techniques for analysis of neural networks
• Communication Complexity
• Strong Direct Product Theorems for Quantum Communication and Query Complexity
• The Intersection of Two Halfspaces Has High Threshold Degree
• Communication Lower Bounds Using Directional Derivatives
• Optimal bounds for sign-representing the intersection of two halfspaces by polynomials
• New degree bounds for polynomial threshold functions

This page was built for publication: Breaking the Minsky--Papert Barrier for Constant-Depth Circuits