Breaking the Minsky--Papert Barrier for Constant-Depth Circuits (Q4554070): Difference between revisions

@@ Property / author @@
+Alexander A. Sherstov
@@ Property / author: Alexander A. Sherstov / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / cites work @@
+Quantum lower bounds for the collision and the element distinctness problems
+Normal rank
@@ Property / cites work @@
+Q3002756
@@ Property / cites work: Q3002756 / rank @@
+Normal rank
@@ Property / cites work @@
+Any AND-OR Formula of Size <i>N</i> Can Be Evaluated in Time $N^{1/2+o(1)}$ on a Quantum Computer
+Normal rank
@@ Property / cites work @@
+The expressive power of voting polynomials
@@ Property / cites work: The expressive power of voting polynomials / rank @@
+Normal rank
@@ Property / cites work @@
+Multiparty Communication Complexity and Threshold Circuit Size of $\ensuremath{\sfAC}^0$
+Normal rank
@@ Property / cites work @@
+Perceptrons, PP, and the polynomial hierarchy
@@ Property / cites work: Perceptrons, PP, and the polynomial hierarchy / rank @@
+Normal rank
@@ Property / cites work @@
+PP is closed under intersection
@@ Property / cites work: PP is closed under intersection / rank @@
+Normal rank
@@ Property / cites work @@
+Harmonic Analysis of Polynomial Threshold Functions
+Normal rank
@@ Property / cites work @@
+Polynomial Threshold Functions, $AC^0 $ Functions, and Spectral Norms
+Normal rank
@@ Property / cites work @@
+Dual lower bounds for approximate degree and Markov-Bernstein inequalities
+Normal rank
@@ Property / cites work @@
+Hardness Amplification and the Approximate Degree of Constant-Depth Circuits
+Normal rank
@@ Property / cites work @@
+Q3002797
@@ Property / cites work: Q3002797 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3002823
@@ Property / cites work: Q3002823 / rank @@
+Normal rank
@@ Property / cites work @@
+Majority gates vs. general weighted threshold gates
+Normal rank
@@ Property / cites work @@
+Q4320535
@@ Property / cites work: Q4320535 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4228473
@@ Property / cites work: Q4228473 / rank @@
+Normal rank
@@ Property / cites work @@
+On the Size of Weights for Threshold Gates
@@ Property / cites work: On the Size of Weights for Threshold Gates / rank @@
+Normal rank
@@ Property / cites work @@
+Q4449183
@@ Property / cites work: Q4449183 / rank @@
+Normal rank
@@ Property / cites work @@
+An efficient membership-query algorithm for learning DNF with respect to the uniform distribution
+Normal rank
@@ Property / cites work @@
+Learning intersections and thresholds of halfspaces
+Normal rank
@@ Property / cites work @@
+Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
+Normal rank
@@ Property / cites work @@
+Q3093360
@@ Property / cites work: Q3093360 / rank @@
+Normal rank
@@ Property / cites work @@
+Unconditional lower bounds for learning intersections of halfspaces
+Normal rank
@@ Property / cites work @@
+On the computational power of Boolean decision lists
+Normal rank
@@ Property / cites work @@
+On the computational power of depth-2 circuits with threshold and modulo gates
+Normal rank
@@ Property / cites work @@
+Computing Boolean functions by polynomials and threshold circuits
+Normal rank
@@ Property / cites work @@
+Communication Complexity
@@ Property / cites work: Communication Complexity / rank @@
+Normal rank
@@ Property / cites work @@
+Disjointness is hard in the multiparty number-on-the-forehead model
+Normal rank
@@ Property / cites work @@
+Q5595902
@@ Property / cites work: Q5595902 / rank @@
+Normal rank
@@ Property / cites work @@
+On the degree of Boolean functions as real polynomials
+Normal rank
@@ Property / cites work @@
+New degree bounds for polynomial threshold functions
+Normal rank
@@ Property / cites work @@
+Approximating threshold circuits by rational functions
+Normal rank
@@ Property / cites work @@
+Perceptrons of Large Weight
@@ Property / cites work: Perceptrons of Large Weight / rank @@
+Normal rank
@@ Property / cites work @@
+A Uniform Lower Bound on Weights of Perceptrons
@@ Property / cites work: A Uniform Lower Bound on Weights of Perceptrons / rank @@
+Normal rank
@@ Property / cites work @@
+The Sign-Rank of AC$^0$
@@ Property / cites work: The Sign-Rank of AC$^0$ / rank @@
+Normal rank
@@ Property / cites work @@
+Q5365063
@@ Property / cites work: Q5365063 / rank @@
+Normal rank
@@ Property / cites work @@
+Separating ${AC}^0$ from Depth-2 Majority Circuits
+Normal rank
@@ Property / cites work @@
+The Pattern Matrix Method
@@ Property / cites work: The Pattern Matrix Method / rank @@
+Normal rank
@@ Property / cites work @@
+Strong Direct Product Theorems for Quantum Communication and Query Complexity
+Normal rank
@@ Property / cites work @@
+Q3191590
@@ Property / cites work: Q3191590 / rank @@
+Normal rank
@@ Property / cites work @@
+The Intersection of Two Halfspaces Has High Threshold Degree
+Normal rank
@@ Property / cites work @@
+Q3191588
@@ Property / cites work: Q3191588 / rank @@
+Normal rank
@@ Property / cites work @@
+Optimal bounds for sign-representing the intersection of two halfspaces by polynomials
+Normal rank
@@ Property / cites work @@
+Communication Lower Bounds Using Directional Derivatives
+Normal rank
@@ Property / cites work @@
+The Multiparty Communication Complexity of Set Disjointness
+Normal rank
@@ Property / cites work @@
+Q3633949
@@ Property / cites work: Q3633949 / rank @@
+Normal rank
@@ Property / cites work @@
+Rational approximation techniques for analysis of neural networks
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1137/15m1015704
+Normal rank
@@ Property / OpenAlex ID @@
+W2898737300
@@ Property / OpenAlex ID: W2898737300 / rank @@
+Normal rank