Optimal bounds for sign-representing the intersection of two halfspaces by polynomials (Q5891428): Difference between revisions

@@ Property / cites work @@
+The complexity of properly learning simple concept classes
+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 @@
+An algorithmic theory of learning: Robust concepts and random projection
+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 @@
+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 @@
+Learning an intersection of a constant number of halfspaces over a uniform distribution
+Normal rank
@@ Property / cites work @@
+Q3002797
@@ Property / cites work: Q3002797 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4479208
@@ Property / cites work: Q4479208 / 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 @@
+Q4255576
@@ Property / cites work: Q4255576 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3549718
@@ Property / cites work: Q3549718 / rank @@
+Normal rank
@@ Property / cites work @@
+Baum’s Algorithm Learns Intersections of Halfspaces with Respect to Log-Concave Distributions
+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 @@
+Learning intersections of halfspaces with a margin
+Normal rank
@@ Property / cites work @@
+Cryptographic hardness for learning intersections of halfspaces
+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 @@
+PAC learning intersections of halfspaces with membership queries
+Normal rank
@@ Property / cites work @@
+Q5595902
@@ Property / cites work: Q5595902 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5655273
@@ Property / cites work: Q5655273 / rank @@
+Normal rank
@@ Property / cites work @@
+Rational approximation to \(|x|\)
@@ Property / cites work: Rational approximation to \(|x|\) / rank @@
+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 @@
+The Sign-Rank of AC$^0$
@@ Property / cites work: The Sign-Rank of AC$^0$ / rank @@
+Normal rank
@@ Property / cites work @@
+Q3950972
@@ Property / cites work: Q3950972 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3142416
@@ Property / cites work: Q3142416 / rank @@
+Normal rank
@@ Property / cites work @@
+The Intersection of Two Halfspaces Has High Threshold Degree
+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 @@
+The unbounded-error communication complexity of symmetric functions
+Normal rank
@@ Property / cites work @@
+On the Power of Threshold Circuits with Small Weights
+Normal rank
@@ Property / cites work @@
+Rational approximation techniques for analysis of neural networks
+Normal rank
@@ Property / cites work @@
+A theory of the learnable
@@ Property / cites work: A theory of the learnable / rank @@
+Normal rank