Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits (Q4568115): Difference between revisions

@@ label / en / label / en @@
+Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits
@@ Property / full work available at URL @@
+https://doi.org/10.4086/toc.2018.v014a009
+Normal rank
@@ Property / OpenAlex ID @@
+W3105381258
@@ Property / OpenAlex ID: W3105381258 / rank @@
+Normal rank
@@ Property / cites work @@
+Algebrization
@@ Property / cites work: Algebrization / rank @@
+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 protocols, pseudorandom generators for Logspace, and time- space trade-offs
+Normal rank
@@ Property / cites work @@
+Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
+Normal rank
@@ Property / cites work @@
+When do extra majority gates help? Polylog\((N)\) majority gates are equivalent to one
+Normal rank
@@ Property / cites work @@
+Mining circuit lower bound proofs for meta-algorithms
+Normal rank
@@ Property / cites work @@
+Average-case lower bounds and satisfiability algorithms for small threshold circuits
+Normal rank
@@ Property / cites work @@
+Concentration Inequalities and Martingale Inequalities: A Survey
+Normal rank
@@ Property / cites work @@
+Bounded Independence Fools Halfspaces
@@ Property / cites work: Bounded Independence Fools Halfspaces / rank @@
+Normal rank
@@ Property / cites work @@
+Average Sensitivity and Noise Sensitivity of Polynomial Threshold Functions
+Normal rank
@@ Property / cites work @@
+Concentration of Measure for the Analysis of Randomized Algorithms
+Normal rank
@@ Property / cites work @@
+Q5538132
@@ Property / cites work: Q5538132 / rank @@
+Normal rank
@@ Property / cites work @@
+Parity, circuits, and the polynomial-time hierarchy
+Normal rank
@@ Property / cites work @@
+A tail bound for read-<i>k</i>families of functions
+Normal rank
@@ Property / cites work @@
+Learning and Lower Bounds for AC 0 with Threshold Gates
+Normal rank
@@ Property / cites work @@
+Spectral properties of threshold functions
@@ Property / cites work: Spectral properties of threshold functions / rank @@
+Normal rank
@@ Property / cites work @@
+Mathematical Foundations of Computer Science 2004
@@ Property / cites work: Mathematical Foundations of Computer Science 2004 / rank @@
+Normal rank
@@ Property / cites work @@
+Size--Depth Tradeoffs for Threshold Circuits
@@ Property / cites work: Size--Depth Tradeoffs for Threshold Circuits / rank @@
+Normal rank
@@ Property / cites work @@
+Large deviations for sums of partly dependent random variables
+Normal rank
@@ Property / cites work @@
+Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits
+Normal rank
@@ Property / cites work @@
+Learning intersections and thresholds of halfspaces
+Normal rank
@@ Property / cites work @@
+Average-case lower bounds for formula size
@@ Property / cites work: Average-case lower bounds for formula size / rank @@
+Normal rank
@@ Property / cites work @@
+Constant depth circuits, Fourier transform, and learnability
+Normal rank
@@ Property / cites work @@
+Correlation Bounds for Poly-size $\mbox{\rm AC}^0$ Circuits with n 1 − o(1) Symmetric Gates
+Normal rank
@@ Property / cites work @@
+Pseudorandom Generators for Polynomial Threshold Functions
+Normal rank
@@ Property / cites work @@
+Pseudorandom bits for constant depth circuits
@@ Property / cites work: Pseudorandom bits for constant depth circuits / rank @@
+Normal rank
@@ Property / cites work @@
+Q4284623
@@ Property / cites work: Q4284623 / rank @@
+Normal rank
@@ Property / cites work @@
+Hardness vs randomness
@@ Property / cites work: Hardness vs randomness / rank @@
+Normal rank
@@ Property / cites work @@
+Hardness amplification within NP
@@ Property / cites work: Hardness amplification within NP / rank @@
+Normal rank
@@ Property / cites work @@
+Analysis of Boolean Functions
@@ Property / cites work: Analysis of Boolean Functions / rank @@
+Normal rank
@@ Property / cites work @@
+The Chow Parameters Problem
@@ Property / cites work: The Chow Parameters Problem / rank @@
+Normal rank
@@ Property / cites work @@
+The number of trees
@@ Property / cites work: The number of trees / rank @@
+Normal rank
@@ Property / cites work @@
+Approximating threshold circuits by rational functions
+Normal rank
@@ Property / cites work @@
+Exponential lower bound for bounded depth circuits with few threshold gates
+Normal rank
@@ Property / cites work @@
+Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
+Normal rank
@@ Property / cites work @@
+Natural proofs
@@ Property / cites work: Natural proofs / rank @@
+Normal rank
@@ Property / cites work @@
+\(n^{{\Omega{}}(\log{} n)}\) lower bounds on the size of depth-3 threshold circuits with AND gates at the bottom
+Normal rank
@@ Property / cites work @@
+Q4839051
@@ Property / cites work: Q4839051 / rank @@
+Normal rank
@@ Property / cites work @@
+Every linear threshold function has a low-weight approximator
+Normal rank
@@ Property / cites work @@
+Optimal bounds for sign-representing the intersection of two halfspaces by polynomials
+Normal rank
@@ Property / cites work @@
+Rational approximation techniques for analysis of neural networks
+Normal rank
@@ Property / cites work @@
+Nonuniform ACC Circuit Lower Bounds
@@ Property / cites work: Nonuniform ACC Circuit Lower Bounds / rank @@
+Normal rank
@@ Property / title @@
+Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits (English)
+Normal rank
@@ Property / Wikidata QID @@
+Q55950641
@@ Property / Wikidata QID: Q55950641 / rank @@
+Normal rank
@@ Property / DBLP publication ID @@
+journals/toc/ChenS018
@@ Property / DBLP publication ID: journals/toc/ChenS018 / rank @@
+Normal rank