- 2010
- Scott Aaronson:
BQP and the polynomial hierarchy. STOC 2010: 141-150 - Scott Aaronson, Andrew Drucker:
A full characterization of quantum advice. STOC 2010: 131-140 - Miklós Ajtai:
Oblivious RAMs without cryptogrpahic assumptions. STOC 2010: 181-190 - Adi Akavia, Oded Goldreich
, Shafi Goldwasser, Dana Moshkovitz:
Erratum for: on basing one-way functions on NP-hardness. STOC 2010: 795-796 - Andris Ambainis, Julia Kempe, Or Sattath:
A quantum lovász local lemma. STOC 2010: 151-160 - Benny Applebaum, Boaz Barak, Avi Wigderson:
Public-key cryptography from different assumptions. STOC 2010: 171-180 - Vikraman Arvind, Srikanth Srinivasan:
On the hardness of the noncommutative determinant. STOC 2010: 677-686 - Boaz Barak, Mark Braverman, Xi Chen, Anup Rao:
How to compress interactive communication. STOC 2010: 67-76 - MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Dániel Marx:
Approximation schemes for steiner forest on planar graphs and graphs of bounded treewidth. STOC 2010: 211-220 - Mohsen Bayati, David Gamarnik, Prasad Tetali:
Combinatorial approach to the interpolation method and scaling limits in sparse random graphs. STOC 2010: 105-114 - Paul Beame, Trinh Huynh, Toniann Pitassi:
Hardness amplification in proof complexity. STOC 2010: 87-96 - Aditya Bhaskara, Moses Charikar, Eden Chlamtac, Uriel Feige, Aravindan Vijayaraghavan:
Detecting high log-densities: an O(n1/4) approximation for densest k-subgraph. STOC 2010: 201-210 - Sayan Bhattacharya, Gagan Goel, Sreenivas Gollapudi, Kamesh Munagala:
Budget constrained auctions with heterogeneous items. STOC 2010: 379-388 - Vladimir Braverman, Rafail Ostrovsky:
Measuring independence of datasets. STOC 2010: 271-280 - Vladimir Braverman, Rafail Ostrovsky:
Zero-one frequency laws. STOC 2010: 281-290 - Peter Bürgisser, Felipe Cucker:
Solving polynomial equations in smoothed polynomial time and a near solution to smale's 17th problem. STOC 2010: 503-512 - Jaroslaw Byrka, Fabrizio Grandoni, Thomas Rothvoß, Laura Sanità:
An improved LP-based approximation for steiner tree. STOC 2010: 583-592 - Jean Cardinal, Samuel Fiorini, Gwenaël Joret, Raphaël M. Jungers, J. Ian Munro:
Sorting under partial information (without the ellipsoid algorithm). STOC 2010: 359-368 - Nishanth Chandran, Bhavana Kanukurthi, Rafail Ostrovsky, Leonid Reyzin:
Privacy amplification with asymptotically optimal entropy loss. STOC 2010: 785-794 - Shuchi Chawla, Jason D. Hartline, David L. Malec, Balasubramanian Sivan:
Multi-parameter mechanism design and sequential posted pricing. STOC 2010: 311-320 - Flavio Chierichetti, Silvio Lattanzi, Alessandro Panconesi:
Almost tight bounds for rumour spreading with conductance. STOC 2010: 399-408 - Anirban Dasgupta, Ravi Kumar, Tamás Sarlós:
A sparse Johnson: Lindenstrauss transform. STOC 2010: 341-350 - Anindya De, Thomas Vidick:
Near-optimal extractors against quantum storage. STOC 2010: 161-170 - Holger Dell, Dieter van Melkebeek:
Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. STOC 2010: 251-260 - Tamal K. Dey, Anil N. Hirani, Bala Krishnamoorthy:
Optimal homologous cycles, total unimodularity, and linear programming. STOC 2010: 221-230 - Ilias Diakonikolas, Prahladh Harsha, Adam R. Klivans, Raghu Meka, Prasad Raghavendra, Rocco A. Servedio, Li-Yang Tan:
Bounding the average sensitivity and noise sensitivity of polynomial threshold functions. STOC 2010: 533-542 - Yevgeniy Dodis, Mihai Patrascu, Mikkel Thorup:
Changing base without losing space. STOC 2010: 593-602 - Ran Duan, Seth Pettie:
Connectivity oracles for failure prone graphs. STOC 2010: 465-474 - Cynthia Dwork, Moni Naor, Toniann Pitassi, Guy N. Rothblum:
Differential privacy under continual observation. STOC 2010: 715-724 - Martin E. Dyer, David Richerby:
On the complexity of #CSP. STOC 2010: 725-734
