Algorithmic Polynomials (Q5138783): Difference between revisions

@@ Property / author @@
-Alexander A. Sherstov
@@ Property / author: Alexander A. Sherstov / rank @@
-Normal rank
@@ 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 @@
+Limitations of Quantum Advice and One-Way Communication
+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 @@
+Polynomial degree vs. quantum query complexity
@@ Property / cites work: Polynomial degree vs. quantum query complexity / rank @@
+Normal rank
@@ Property / cites work @@
+Quantum Walk Algorithm for Element Distinctness
@@ Property / cites work: Quantum Walk Algorithm for Element Distinctness / 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 @@
+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 @@
+PP is closed under intersection
@@ Property / cites work: PP is closed under intersection / rank @@
+Normal rank
@@ Property / cites work @@
+Adversary lower bound for the k-sum problem
@@ Property / cites work: Adversary lower bound for the k-sum problem / rank @@
+Normal rank
@@ Property / cites work @@
+Quantum Algorithms for Element Distinctness
@@ Property / cites work: Quantum Algorithms for Element Distinctness / rank @@
+Normal rank
@@ Property / cites work @@
+Robust polynomials and quantum algorithms
@@ Property / cites work: Robust polynomials and quantum algorithms / rank @@
+Normal rank
@@ Property / cites work @@
+The polynomial method strikes back: tight quantum query bounds via dual polynomials
+Normal rank
@@ Property / cites work @@
+Quantum algorithms and approximating polynomials for composed functions with shared inputs
+Normal rank
@@ Property / cites work @@
+A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$
+Normal rank
@@ Property / cites work @@
+Faster private release of marginals on small databases
+Normal rank
@@ Property / cites work @@
+Q3319163
@@ Property / cites work: Q3319163 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3522560
@@ Property / cites work: Q3522560 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3171708
@@ Property / cites work: Q3171708 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3002797
@@ Property / cites work: Q3002797 / rank @@
+Normal rank
@@ Property / cites work @@
+Extremal Combinatorics
@@ Property / cites work: Extremal Combinatorics / 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 @@
+Quantum and Classical Strong Direct Product Theorems and Optimal Time‐Space Tradeoffs
+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 @@
+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 @@
+Q3002755
@@ Property / cites work: Q3002755 / rank @@
+Normal rank
@@ Property / cites work @@
+Disjointness is hard in the multiparty number-on-the-forehead model
+Normal rank
@@ Property / cites work @@
+Approximate inclusion-exclusion
@@ Property / cites work: Approximate inclusion-exclusion / rank @@
+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 @@
+Quantum communication complexity of symmetric predicates
+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 @@
+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 @@
+Q3191588
@@ Property / cites work: Q3191588 / rank @@
+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 @@
+Rational approximation techniques for analysis of neural networks
+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 @@
+Q4505382
@@ Property / cites work: Q4505382 / rank @@
+Normal rank
@@ Property / cites work @@
+Faster Algorithms for Privately Releasing Marginals
+Normal rank
@@ Property / cites work @@
+Q3604066
@@ Property / cites work: Q3604066 / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1137/19m1278831
+Normal rank
@@ Property / OpenAlex ID @@
+W3037165238
@@ Property / OpenAlex ID: W3037165238 / rank @@
+Normal rank