A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$ (Q5117375): Difference between revisions

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / arXiv ID @@
+.05784
@@ Property / arXiv ID: 1703.05784 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3166192
@@ Property / cites work: Q3166192 / rank @@
+Normal rank
@@ Property / cites work @@
+Separations in query complexity using cheat sheets
+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 @@
+Separations in Query Complexity Based on Pointer Functions
+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 @@
+Q5111154
@@ Property / cites work: Q5111154 / rank @@
+Normal rank
@@ Property / cites work @@
+Quantum lower bounds by polynomials
@@ Property / cites work: Quantum lower bounds by polynomials / rank @@
+Normal rank
@@ Property / cites work @@
+Multiparty Communication Complexity and Threshold Circuit Size of $\ensuremath{\sfAC}^0$
+Normal rank
@@ Property / cites work @@
+Q2906797
@@ Property / cites work: Q2906797 / 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 @@
+Bounded Indistinguishability and the Complexity of Recovering Secrets
+Normal rank
@@ Property / cites work @@
+The polynomial method strikes back: tight quantum query bounds via dual polynomials
+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 @@
+Q2830865
@@ Property / cites work: Q2830865 / rank @@
+Normal rank
@@ Property / cites work @@
+Improved Bounds on the Sign-Rank of AC^0
@@ Property / cites work: Improved Bounds on the Sign-Rank of AC^0 / rank @@
+Normal rank
@@ Property / cites work @@
+Faster private release of marginals on small databases
+Normal rank
@@ Property / cites work @@
+The log-approximate-rank conjecture is false
@@ Property / cites work: The log-approximate-rank conjecture is false / rank @@
+Normal rank
@@ Property / cites work @@
+Adaptivity vs. Postselection, and Hardness Amplification for Polynomial Approximation
+Normal rank
@@ Property / cites work @@
+The Quantum Query Complexity of Read-Many Formulas
+Normal rank
@@ Property / cites work @@
+Improved Separations between Nondeterministic and Randomized Multiparty Communication
+Normal rank
@@ Property / cites work @@
+Q3002823
@@ Property / cites work: Q3002823 / rank @@
+Normal rank
@@ Property / cites work @@
+Deterministic Communication vs. Partition Number
@@ Property / cites work: Deterministic Communication vs. Partition Number / rank @@
+Normal rank
@@ Property / cites work @@
+One-way functions and the nonisomorphism of NP-complete sets
+Normal rank
@@ Property / cites work @@
+Q4449183
@@ Property / cites work: Q4449183 / rank @@
+Normal rank
@@ Property / cites work @@
+Inclusion-exclusion: exact and approximate
@@ Property / cites work: Inclusion-exclusion: exact and approximate / rank @@
+Normal rank
@@ Property / cites work @@
+Agnostically Learning Halfspaces
@@ Property / cites work: Agnostically Learning Halfspaces / rank @@
+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 @@
+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 @@
+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 @@
+Q4601824
@@ Property / cites work: Q4601824 / 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 @@
+Q3396635
@@ Property / cites work: Q3396635 / rank @@
+Normal rank
@@ Property / cites work @@
+Approximate inclusion-exclusion for arbitrary symmetric functions
+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 multiparty communication complexity of set disjointness
+Normal rank
@@ Property / cites work @@
+Q3191590
@@ Property / cites work: Q3191590 / rank @@
+Normal rank
@@ Property / cites work @@
+Communication lower bounds using directional derivatives
+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 @@
+Breaking the minsky-papert barrier for constant-depth circuits
+Normal rank
@@ Property / cites work @@
+Algorithmic polynomials
@@ Property / cites work: Algorithmic polynomials / rank @@
+Normal rank
@@ Property / cites work @@
+Q3633949
@@ Property / cites work: Q3633949 / rank @@
+Normal rank
@@ Property / cites work @@
+Formula lower bounds via the quantum method
@@ Property / cites work: Formula lower bounds via the quantum method / rank @@
+Normal rank
@@ Property / cites work @@
+Query complexity, or why is it difficult to separate \(NP^ A\cap coNP^ A\) from \(P^ A\) by random oracles A?
+Normal rank
@@ Property / cites work @@
+Q4598150
@@ Property / cites work: Q4598150 / rank @@
+Normal rank
@@ Property / cites work @@
+Faster Algorithms for Privately Releasing Marginals
+Normal rank
@@ Property / OpenAlex ID @@
+W2981639918
@@ Property / OpenAlex ID: W2981639918 / rank @@
+Normal rank