- Pierre Fraigniaud, George Giakkoupis:
On the searchability of small-world networks with arbitrary underlying structure. STOC 2010: 389-398 - Pierre Fraigniaud, Amos Korman:
An optimal ancestry scheme and small universal posets. STOC 2010: 611-620 - Pu Gao, Nicholas C. Wormald:
Load balancing and orientability thresholds for random hypergraphs. STOC 2010: 97-104 - Anna C. Gilbert, Yi Li
, Ely Porat, Martin J. Strauss:
Approximate sparse recovery: optimizing time and measurements. STOC 2010: 475-484 - Guillem Godoy, Omer Giménez, Lander Ramos, Carme Àlvarez:
The HOM problem is decidable. STOC 2010: 485-494 - Ashish Goel, Michael Kapralov, Sanjeev Khanna:
Perfect matchings in o(n log n) time in regular bipartite graphs. STOC 2010: 39-46 - Vipul Goyal, Abhishek Jain:
On the round complexity of covert computation. STOC 2010: 191-200 - Venkatesan Guruswami, Johan Håstad, Swastik Kopparty:
On the list-decodability of random linear codes. STOC 2010: 409-416 - Iftach Haitner, Omer Reingold, Salil P. Vadhan:
Efficiency improvements in constructing pseudorandom generators from one-way functions. STOC 2010: 437-446 - Elad Haramaty, Amir Shpilka:
On the structure of cubic and quartic polynomials. STOC 2010: 331-340 - Moritz Hardt, Kunal Talwar:
On the geometry of differential privacy. STOC 2010: 705-714 - Prahladh Harsha, Adam R. Klivans, Raghu Meka:
An invariance principle for polytopes. STOC 2010: 543-552 - Jason D. Hartline, Brendan Lucier:
Bayesian algorithmic mechanism design. STOC 2010: 301-310 - Hiroshi Hirai:
The maximum multiflow problems with bounded fractionality. STOC 2010: 115-120 - Pavel Hrubes, Avi Wigderson, Amir Yehudayoff:
Non-commutative circuits and the sum-of-squares problem. STOC 2010: 667-676 - Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, John Watrous:
QIP = PSPACE. STOC 2010: 573-582 - Adam Tauman Kalai, Ankur Moitra, Gregory Valiant:
Efficiently learning mixtures of two Gaussians. STOC 2010: 553-562 - Ravindran Kannan:
Spectral methods for matrices and tensors. STOC 2010: 1-12 - Zohar Shay Karnin, Partha Mukhopadhyay, Amir Shpilka, Ilya Volkovich:
Deterministic identity testing of depth-4 multilinear circuits with bounded top fan-in. STOC 2010: 649-658 - 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. STOC 2010: 775-784 - Akitoshi Kawamura, Stephen A. Cook:
Complexity theory for operators in analysis. STOC 2010: 495-502 - Ken-ichi Kawarabayashi, Bruce A. Reed:
Odd cycle packing. STOC 2010: 695-704 - Ken-ichi Kawarabayashi, Paul Wollan:
A shorter proof of the graph minor algorithm: the unique linkage theorem. STOC 2010: 687-694 - Hartmut Klauck:
A strong direct product theorem for disjointness. STOC 2010: 77-86 - Alexandra Kolla, Yury Makarychev, Amin Saberi, Shang-Hua Teng:
Subgraph sparsification and nearly optimal ultrasparsifiers. STOC 2010: 57-66 - Swastik Kopparty, Shubhangi Saraf:
Local list-decoding and testing of random linear codes from high error. STOC 2010: 417-426 - Fabian Kuhn, Nancy A. Lynch, Rotem Oshman:
Distributed computation in dynamic networks. STOC 2010: 513-522 - James R. Lee, Mohammad Moharrami:
Bilipschitz snowflakes and metrics of negative type. STOC 2010: 621-630 - Jon Lee, Maxim Sviridenko, Jan Vondrák:
Matroid matching: the power of local search. STOC 2010: 369-378 - Frank Thomson Leighton, Ankur Moitra:
Extensions and limits to vertex sparsification. STOC 2010: 47-56
