- 2009
- Dorit Aharonov, Itai Arad, Zeph Landau, Umesh V. Vazirani:
The detectability lemma and quantum gap amplification. STOC 2009: 417-426 - Reid Andersen, Yuval Peres:
Finding sparse cuts locally using evolving sets. STOC 2009: 235-244 - Alexandr Andoni, Krzysztof Onak:
Approximating edit distance in near-linear time. STOC 2009: 199-204 - Boris Aronov, Esther Ezra, Micha Sharir:
Small-size epsilon-nets for axis-parallel rectangles and boxes. STOC 2009: 639-648 - Sanjeev Arora, Constantinos Daskalakis, David Steurer:
Message passing algorithms and improved LP decoding. STOC 2009: 3-12 - Per Austrin, Johan Håstad:
Randomly supported independence and resistance. STOC 2009: 483-492 - Yossi Azar, Iftah Gamzu, Xiaoxin Yin:
Multiple intents re-ranking. STOC 2009: 669-678 - László Babai, Robert Beals, Ákos Seress:
Polynomial-time theory of matrix groups. STOC 2009: 55-64 - Leonid Barenboim, Michael Elkin:
Distributed (delta+1)-coloring in linear (in delta) time. STOC 2009: 111-120 - MohammadHossein Bateni, Moses Charikar, Venkatesan Guruswami:
MaxMin allocation via degree lower-bounded arborescences. STOC 2009: 543-552 - Joshua D. Batson, Daniel A. Spielman, Nikhil Srivastava:
Twice-ramanujan sparsifiers. STOC 2009: 255-262 - Eli Ben-Sasson, Swastik Kopparty:
Affine dispersers from subspace polynomials. STOC 2009: 65-74 - Aaron Bernstein, David R. Karger:
A nearly optimal oracle for avoiding failed vertices and edges. STOC 2009: 101-110 - Eric Blais:
Testing juntas nearly optimally. STOC 2009: 151-158 - Jin-yi Cai, Pinyan Lu, Mingji Xia:
Holant problems and counting CSP. STOC 2009: 715-724 - Jean Cardinal, Samuel Fiorini, Gwenaël Joret, Raphaël M. Jungers, J. Ian Munro:
An efficient algorithm for partial order production. STOC 2009: 93-100 - Jivitej S. Chadha, Naveen Garg, Amit Kumar, V. N. Muralidhara:
A competitive algorithm for minimizing weighted flow time on unrelatedmachines with speed augmentation. STOC 2009: 679-684 - Jérémie Chalopin, Daniel Gonçalves:
Every planar graph is the intersection graph of segments in the plane: extended abstract. STOC 2009: 631-638 - Erin W. Chambers, Jeff Erickson, Amir Nayyeri:
Homology flows, cohomology cuts. STOC 2009: 273-282 - Moses Charikar, Konstantin Makarychev, Yury Makarychev:
Integrality gaps for Sherali-Adams relaxations. STOC 2009: 283-292 - Shiri Chechik, Michael Langberg, David Peleg, Liam Roditty:
Fault-tolerant spanners for general graphs. STOC 2009: 435-444 - Jing Chen, Silvio Micali:
A new approach to auctions and resilient mechanism design. STOC 2009: 503-512 - Qi Cheng, Daqing Wan:
A deterministic reduction for the gap minimum distance problem: [extended abstract]. STOC 2009: 33-38 - Kenneth L. Clarkson, David P. Woodruff:
Numerical linear algebra in the streaming model. STOC 2009: 205-214 - Richard Cleve, Daniel Gottesman, Michele Mosca, Rolando D. Somma, David L. Yonge-Mallo:
Efficient discrete-time simulations of continuous-time quantum query algorithms. STOC 2009: 409-416 - Constantinos Daskalakis, Christos H. Papadimitriou:
On oblivious PTAS's for nash equilibrium. STOC 2009: 75-84 - Martin Dietzfelbinger, Philipp Woelfel:
Tight lower bounds for greedy routing in uniform small world rings. STOC 2009: 591-600 - Yevgeniy Dodis, Yael Tauman Kalai, Shachar Lovett:
On cryptography with auxiliary input. STOC 2009: 621-630 - Yevgeniy Dodis, Daniel Wichs:
Non-malleable extractors and symmetric key cryptography from weak secrets. STOC 2009: 601-610 - Cynthia Dwork, Jing Lei:
Differential privacy and robust statistics. STOC 2009: 371-380