- Cynthia Dwork, Moni Naor, Omer Reingold, Guy N. Rothblum, Salil P. Vadhan:
On the complexity of differentially private data release: efficient algorithms and hardness results. STOC 2009: 381-390 - Klim Efremenko:
3-query locally decodable codes of subexponential length. STOC 2009: 39-44 - Eyal Even-Dar, Yishay Mansour, Uri Nadav:
On the convergence of regret minimization dynamics in concave games. STOC 2009: 523-532 - Dan Feldman, Amos Fiat, Haim Kaplan, Kobbi Nissim:
Private coresets. STOC 2009: 361-370 - Tobias Friedrich, Thomas Sauerwald:
Near-perfect load balancing by randomized rounding. STOC 2009: 121-130 - Eli Gafni:
The extended BG-simulation and the characterization of t-resiliency. STOC 2009: 85-92 - Craig Gentry:
Fully homomorphic encryption using ideal lattices. STOC 2009: 169-178 - Arpita Ghosh, Tim Roughgarden, Mukund Sundararajan:
Universally utility-maximizing privacy mechanisms. STOC 2009: 351-360 - Oded Goldreich, Dana Ron:
On proximity oblivious testing. STOC 2009: 141-150 - Shafi Goldwasser:
Athena lecture: Controlling Access to Programs? STOC 2009: 167-168 - Parikshit Gopalan, Venkatesan Guruswami, Prasad Raghavendra:
List decoding tensor products and interleaved codes. STOC 2009: 13-22 - Anupam Gupta, Amit Kumar:
A constant-factor approximation for stochastic Steiner forest. STOC 2009: 659-668 - Anupam Gupta, Ravishankar Krishnaswamy, R. Ravi:
Online and stochastic survivable network design. STOC 2009: 685-694 - Venkatesan Guruswami:
Artin automorphisms, cyclotomic function fields, and folded list-decodable codes. STOC 2009: 23-32 - Iftach Haitner, Omer Reingold, Salil P. Vadhan, Hoeteck Wee:
Inaccessible entropy. STOC 2009: 611-620 - Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova:
An axiomatic approach to algebrization. STOC 2009: 695-704 - Russell Impagliazzo, Valentine Kabanets, Avi Wigderson:
New direct-product testers and 2-query PCPs. STOC 2009: 131-140 - Ravi Kannan, Hariharan Narayanan:
Random walks on polytopes and an affine interior point method for linear programming. STOC 2009: 561-570 - Marek Karpinski, Warren Schudy:
Linear time approximation schemes for the Gale-Berlekamp game and related minimization problems. STOC 2009: 313-322 - Ken-ichi Kawarabayashi, Bruce A. Reed:
Hadwiger's conjecture is decidable. STOC 2009: 445-454 - Robert Kleinberg, Georgios Piliouras, Éva Tardos:
Multiplicative updates outperform generic no-regret learning in congestion games: extended abstract. STOC 2009: 533-542 - Phokion G. Kolaitis, Swastik Kopparty:
Random graphs and the parity quantifier. STOC 2009: 705-714 - Gábor Kun, Mario Szegedy:
A new line of attack on the dichotomy conjecture. STOC 2009: 725-734 - Eyal Kushilevitz, Enav Weinreb:
On the complexity of communication complexity. STOC 2009: 465-474 - Silvio Lattanzi, D. Sivakumar:
Affiliation networks. STOC 2009: 427-434 - Jon Lee, Vahab S. Mirrokni, Viswanath Nagarajan, Maxim Sviridenko:
Non-monotone submodular maximization under matroid and knapsack constraints. STOC 2009: 323-332 - James R. Lee, Anastasios Sidiropoulos:
On the geometry of graphs with a forbidden minor. STOC 2009: 245-254 - Huijia Lin, Rafael Pass:
Non-malleability amplification. STOC 2009: 189-198 - Huijia Lin, Rafael Pass, Muthuramakrishnan Venkitasubramaniam:
A unified framework for concurrent security: universal composability from stand-alone non-malleability. STOC 2009: 179-188 - Yi-Kai Liu:
Quantum algorithms using the curvelet transform. STOC 2009: 391-400