default search action
Theory of Computing, Volume 10
Volume 10, 2014
- Prahladh Harsha
, Adam R. Klivans, Raghu Meka:
Bounding the Sensitivity of Polynomial Threshold Functions. 1-26 - Ilias Diakonikolas, Rocco A. Servedio
A Regularity Lemma and Low-Weight Approximators for Low-Degree Polynomial Threshold Functions. 27-53 - Aram W. Harrow
Dimension-Free L2 Maximal Inequality for Spherical Means in the Hypercube. 55-75 - Jop Briët, Fernando Mário de Oliveira Filho, Frank Vallentin:
Grothendieck Inequalities for Semidefinite Programs with Rank Constraint. 77-105 - Gillat Kol, Ran Raz
Competing-Provers Protocols for Circuit Evaluation. 107-131 - Scott Aaronson, Andris Ambainis:
The Need for Structure in Quantum Speedups. 133-166 - Jin-Yi Cai, Aaron Gorenstein:
Matchgates Revisited. 167-197 - Eric Allender
Symmetry Coincides with Nondeterminism for Time-Bounded Auxiliary Pushdown Automata. 199-215 - Michael Lampis:
Improved Inapproximability for TSP. 217-236 - Tobias Brunsch, Navin Goyal, Luis Rademacher
Lower Bounds for the Average and Smoothed Number of Pareto-Optima. 237-256 - Assaf Naor, Oded Regev, Thomas Vidick
Efficient Rounding for the Noncommutative Grothendieck Inequality. 257-295 - Eric Allender
Width-Parametrized SAT: Time--Space Tradeoffs. 297-339 - Konstantin Makarychev, Yury Makarychev:
Approximation Algorithm for Non-Boolean Max-k-CSP. 341-358 - Sangxia Huang:
Approximation Resistance on Satisfiable Instances for Sparse Predicates. 359-388 - Siu Man Chan, Aaron Potechin
Tight Bounds for Monotone Switching Networks via Fourier Analysis. 389-419 - Bernard Chazelle:
How Many Bits Can a Flock of Birds Compute? 421-451 - Deeparnab Chakrabarty, C. Seshadhri:
An Optimal Lower Bound for Monotonicity Testing over Hypergrids. 453-464 - Amir Shpilka
On Reconstruction and Testing of Read-Once Formulas. 465-514 - Sourav Chakraborty, Eldar Fischer, Arie Matsliah:
Query Complexity Lower Bounds for Reconstruction of Codes. 515-533 - Constantinos Daskalakis, Ilias Diakonikolas, Rocco A. Servedio
Learning k-Modal Distributions via Testing. 535-570
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-12-31 21:33 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: