default search action
42nd STOC 2010: Cambridge, Massachusetts, USA
- Leonard J. Schulman:
Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010. ACM 2010, ISBN 978-1-4503-0050-6 - Ravindran Kannan:
Spectral methods for matrices and tensors. 1-12 - Michel Talagrand:
Are many small sets explicitly small? 13-36 - Andrea Montanari:
Message passing algorithms: a success looking for theoreticians. 37-38 - Ashish Goel, Michael Kapralov
, Sanjeev Khanna:
Perfect matchings in o(n log n) time in regular bipartite graphs. 39-46 - Frank Thomson Leighton, Ankur Moitra:
Extensions and limits to vertex sparsification. 47-56 - Alexandra Kolla, Yury Makarychev, Amin Saberi, Shang-Hua Teng:
Subgraph sparsification and nearly optimal ultrasparsifiers. 57-66 - Boaz Barak, Mark Braverman, Xi Chen
How to compress interactive communication. 67-76 - Hartmut Klauck
A strong direct product theorem for disjointness. 77-86 - Paul Beame, Trinh Huynh, Toniann Pitassi:
Hardness amplification in proof complexity. 87-96 - Pu Gao, Nicholas C. Wormald:
Load balancing and orientability thresholds for random hypergraphs. 97-104 - Mohsen Bayati, David Gamarnik, Prasad Tetali:
Combinatorial approach to the interpolation method and scaling limits in sparse random graphs. 105-114 - Hiroshi Hirai:
The maximum multiflow problems with bounded fractionality. 115-120 - Aleksander Madry:
Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms. 121-130 - Scott Aaronson, Andrew Drucker:
A full characterization of quantum advice. 131-140 - Scott Aaronson:
BQP and the polynomial hierarchy. 141-150 - Andris Ambainis, Julia Kempe
A quantum lovász local lemma. 151-160 - Anindya De, Thomas Vidick
Near-optimal extractors against quantum storage. 161-170 - Benny Applebaum, Boaz Barak, Avi Wigderson:
Public-key cryptography from different assumptions. 171-180 - Miklós Ajtai:
Oblivious RAMs without cryptogrpahic assumptions. 181-190 - Vipul Goyal, Abhishek Jain
On the round complexity of covert computation. 191-200 - Aditya Bhaskara, Moses Charikar
Detecting high log-densities: an O(n1/4) approximation for densest k-subgraph. 201-210 - MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Dániel Marx:
Approximation schemes for steiner forest on planar graphs and graphs of bounded treewidth. 211-220 - Tamal K. Dey, Anil N. Hirani, Bala Krishnamoorthy:
Optimal homologous cycles, total unimodularity, and linear programming. 221-230 - Ryan Williams
Improving exhaustive search implies superpolynomial lower bounds. 231-240 - Ramamohan Paturi, Pavel Pudlák:
On the complexity of circuit satisfiability. 241-250 - Holger Dell
Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. 251-260 - Frédéric Magniez, Claire Mathieu, Ashwin Nayak:
Recognizing well-parenthesized expressions in the streaming model. 261-270 - Vladimir Braverman, Rafail Ostrovsky:
Measuring independence of datasets. 271-280 - Vladimir Braverman, Rafail Ostrovsky:
Zero-one frequency laws. 281-290 - James B. Orlin
Improved algorithms for computing fisher's market clearing prices: computing fisher's market clearing prices. 291-300 - Jason D. Hartline, Brendan Lucier:
Bayesian algorithmic mechanism design. 301-310 - Shuchi Chawla, Jason D. Hartline, David L. Malec, Balasubramanian Sivan:
Multi-parameter mechanism design and sequential posted pricing. 311-320 - Daniel Lokshtanov, Jesper Nederlof:
Saving space by algebraization. 321-330 - Elad Haramaty, Amir Shpilka
On the structure of cubic and quartic polynomials. 331-340 - Anirban Dasgupta
A sparse Johnson: Lindenstrauss transform. 341-350 - Daniele Micciancio
A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations. 351-358 - Jean Cardinal, Samuel Fiorini, Gwenaël Joret, Raphaël M. Jungers, J. Ian Munro:
Sorting under partial information (without the ellipsoid algorithm). 359-368 - Jon Lee
Matroid matching: the power of local search. 369-378 - Sayan Bhattacharya, Gagan Goel, Sreenivas Gollapudi, Kamesh Munagala:
Budget constrained auctions with heterogeneous items. 379-388 - Pierre Fraigniaud, George Giakkoupis:
On the searchability of small-world networks with arbitrary underlying structure. 389-398 - Flavio Chierichetti, Silvio Lattanzi, Alessandro Panconesi:
Almost tight bounds for rumour spreading with conductance. 399-408 - Venkatesan Guruswami, Johan Håstad
On the list-decodability of random linear codes. 409-416 - Swastik Kopparty, Shubhangi Saraf:
Local list-decoding and testing of random linear codes from high error. 417-426 - Raghu Meka, David Zuckerman:
Pseudorandom generators for polynomial threshold functions. 427-436 - Iftach Haitner, Omer Reingold, Salil P. Vadhan:
Efficiency improvements in constructing pseudorandom generators from one-way functions. 437-446 - Elad Verbin, Qin Zhang
The limits of buffering: a tight lower bound for dynamic membership in the external memory model. 447-456 - Krzysztof Onak
Maintaining a large matching and a small vertex cover. 457-464 - Ran Duan, Seth Pettie:
Connectivity oracles for failure prone graphs. 465-474 - Anna C. Gilbert, Yi Li
Approximate sparse recovery: optimizing time and measurements. 475-484 - Guillem Godoy, Omer Giménez, Lander Ramos, Carme Àlvarez:
The HOM problem is decidable. 485-494 - Akitoshi Kawamura, Stephen A. Cook:
Complexity theory for operators in analysis. 495-502 - Peter Bürgisser, Felipe Cucker
Solving polynomial equations in smoothed polynomial time and a near solution to smale's 17th problem. 503-512 - Fabian Kuhn, Nancy A. Lynch, Rotem Oshman:
Distributed computation in dynamic networks. 513-522 - Alexander A. Sherstov:
Optimal bounds for sign-representing the intersection of two halfspaces by polynomials. 523-532 - Ilias Diakonikolas, Prahladh Harsha
Bounding the average sensitivity and noise sensitivity of polynomial threshold functions. 533-542 - Prahladh Harsha
An invariance principle for polytopes. 543-552 - Adam Tauman Kalai, Ankur Moitra, Gregory Valiant:
Efficiently learning mixtures of two Gaussians. 553-562 - László A. Végh
Augmenting undirected node-connectivity by one. 563-572 - Rahul Jain
QIP = PSPACE. 573-582 - Jaroslaw Byrka, Fabrizio Grandoni
An improved LP-based approximation for steiner tree. 583-592 - Yevgeniy Dodis, Mihai Patrascu, Mikkel Thorup:
Changing base without losing space. 593-602 - Mihai Patrascu:
Towards polynomial lower bounds for dynamic problems. 603-610 - Pierre Fraigniaud, Amos Korman:
An optimal ancestry scheme and small universal posets. 611-620 - James R. Lee, Mohammad Moharrami:
Bilipschitz snowflakes and metrics of negative type. 621-630 - Prasad Raghavendra, David Steurer
Approximations for the isoperimetric and spectral profile of graphs and related parameters. 631-640 - Kasturi R. Varadarajan:
Weighted geometric set cover via quasi-uniform sampling. 641-648 - Zohar Shay Karnin, Partha Mukhopadhyay, Amir Shpilka
Deterministic identity testing of depth-4 multilinear circuits with bounded top fan-in. 649-658 - Ran Raz
Tensor-rank and lower bounds for arithmetic formulas. 659-666 - Pavel Hrubes, Avi Wigderson, Amir Yehudayoff:
Non-commutative circuits and the sum-of-squares problem. 667-676 - Vikraman Arvind, Srikanth Srinivasan
On the hardness of the noncommutative determinant. 677-686 - Ken-ichi Kawarabayashi, Paul Wollan:
A shorter proof of the graph minor algorithm: the unique linkage theorem. 687-694 - Ken-ichi Kawarabayashi, Bruce A. Reed:
Odd cycle packing. 695-704 - Moritz Hardt, Kunal Talwar:
On the geometry of differential privacy. 705-714 - Cynthia Dwork, Moni Naor, Toniann Pitassi, Guy N. Rothblum:
Differential privacy under continual observation. 715-724 - Martin E. Dyer
On the complexity of #CSP. 725-734 - Dániel Marx:
Tractable hypergraph properties for constraint satisfaction and conjunctive queries. 735-744 - Ola Svensson:
Conditional hardness of precedence constrained scheduling on identical machines. 745-754 - Prasad Raghavendra, David Steurer
Graph expansion and the unique games conjecture. 755-764 - Aaron Roth
Interactive privacy via the median mechanism. 765-774 - Shiva Prasad Kasiviswanathan, Mark Rudelson, Adam D. Smith, Jonathan R. Ullman:
The price of privately releasing contingency tables and the spectra of random matrices with correlated rows. 775-784 - Nishanth Chandran, Bhavana Kanukurthi, Rafail Ostrovsky, Leonid Reyzin:
Privacy amplification with asymptotically optimal entropy loss. 785-794 - Adi Akavia, Oded Goldreich
Erratum for: on basing one-way functions on NP-hardness. 795-796
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-11-11 21:16 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: