A small decrease in the degree of a polynomial with a given sign function can exponentially increase its weight and length (Q368235): Difference between revisions

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / cites work @@
+Q3142416
@@ Property / cites work: Q3142416 / rank @@
+Normal rank
@@ Property / cites work @@
+Complexity measures and decision tree complexity: a survey.
+Normal rank
@@ Property / cites work @@
+Q3396635
@@ Property / cites work: Q3396635 / rank @@
+Normal rank
@@ Property / cites work @@
+Approximating threshold circuits by rational functions
+Normal rank
@@ Property / cites work @@
+Rational approximation techniques for analysis of neural networks
+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 @@
+PP is closed under intersection
@@ Property / cites work: PP is closed under intersection / rank @@
+Normal rank
@@ Property / cites work @@
+On the computational power of depth-2 circuits with threshold and modulo gates
+Normal rank
@@ Property / cites work @@
+Q3549625
@@ Property / cites work: Q3549625 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3549688
@@ Property / cites work: Q3549688 / rank @@
+Normal rank
@@ Property / cites work @@
+Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
+Normal rank
@@ Property / cites work @@
+New degree bounds for polynomial threshold functions
+Normal rank
@@ Property / cites work @@
+Unconditional lower bounds for learning intersections of halfspaces
+Normal rank
@@ Property / cites work @@
+Learning intersections and thresholds of halfspaces
+Normal rank
@@ Property / cites work @@
+Q3093360
@@ Property / cites work: Q3093360 / 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 @@
+Harmonic Analysis of Polynomial Threshold Functions
+Normal rank
@@ Property / cites work @@
+On the Power of Threshold Circuits with Small Weights
+Normal rank
@@ Property / cites work @@
+Polynomial Threshold Functions, $AC^0 $ Functions, and Spectral Norms
+Normal rank
@@ Property / cites work @@
+Majority gates vs. general weighted threshold gates
+Normal rank
@@ Property / cites work @@
+Computing Boolean functions by polynomials and threshold circuits
+Normal rank
@@ Property / cites work @@
+On the computational power of Boolean decision lists
+Normal rank
@@ Property / cites work @@
+On the power of a threshold gate at the top
@@ Property / cites work: On the power of a threshold gate at the top / 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 @@
+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 @@
+Threshold circuits of bounded depth
@@ Property / cites work: Threshold circuits of bounded depth / rank @@
+Normal rank