default search action
41st STOC 2009: Bethesda, MD, USA
- Michael Mitzenmacher:
Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009. ACM 2009, ISBN 978-1-60558-506-2 - Avi Wigderson:
The work of Leslie Valiant. 1-2
Codes
- Sanjeev Arora, Constantinos Daskalakis, David Steurer
:
Message passing algorithms and improved LP decoding. 3-12 - Parikshit Gopalan, Venkatesan Guruswami, Prasad Raghavendra:
List decoding tensor products and interleaved codes. 13-22 - Venkatesan Guruswami:
Artin automorphisms, cyclotomic function fields, and folded list-decodable codes. 23-32 - Qi Cheng
A deterministic reduction for the gap minimum distance problem: [extended abstract]. 33-38 - Klim Efremenko
3-query locally decodable codes of subexponential length. 39-44
Complexity I
- Linda Sellie:
Exact learning of random DNF over the uniform distribution. 45-54 - László Babai
Polynomial-time theory of matrix groups. 55-64 - Eli Ben-Sasson, Swastik Kopparty:
Affine dispersers from subspace polynomials. 65-74 - Constantinos Daskalakis, Christos H. Papadimitriou:
On oblivious PTAS's for nash equilibrium. 75-84 - Eli Gafni:
The extended BG-simulation and the characterization of t-resiliency. 85-92
Algorithms and data structures
- Jean Cardinal, Samuel Fiorini, Gwenaël Joret, Raphaël M. Jungers, J. Ian Munro:
An efficient algorithm for partial order production. 93-100 - Aaron Bernstein, David R. Karger
A nearly optimal oracle for avoiding failed vertices and edges. 101-110 - Leonid Barenboim, Michael Elkin:
Distributed (delta+1)-coloring in linear (in delta) time. 111-120 - Tobias Friedrich, Thomas Sauerwald:
Near-perfect load balancing by randomized rounding. 121-130
Property testing
- Russell Impagliazzo
New direct-product testers and 2-query PCPs. 131-140 - Oded Goldreich, Dana Ron
On proximity oblivious testing. 141-150 - Eric Blais:
Testing juntas nearly optimally. 151-158 - Asaf Shapira:
Green's conjecture and testing linear-invariant properties. 159-166 - Shafi Goldwasser:
Athena lecture: Controlling Access to Programs? 167-168
Crypto I
- Craig Gentry:
Fully homomorphic encryption using ideal lattices. 169-178 - Huijia Lin, Rafael Pass
A unified framework for concurrent security: universal composability from stand-alone non-malleability. 179-188 - Huijia Lin, Rafael Pass
Non-malleability amplification. 189-198
Approx algorithms I
- Alexandr Andoni, Krzysztof Onak:
Approximating edit distance in near-linear time. 199-204 - Kenneth L. Clarkson, David P. Woodruff:
Numerical linear algebra in the streaming model. 205-214 - Nam H. Nguyen, Thong T. Do, Trac D. Tran:
A fast and efficient algorithm for low-rank approximation of a matrix. 215-224 - Yuichi Yoshida, Masaki Yamamoto, Hiro Ito:
An improved constant-time approximation algorithm for maximum matchings. 225-234
Graphs cuts and flows
- Reid Andersen, Yuval Peres:
Finding sparse cuts locally using evolving sets. 235-244 - James R. Lee, Anastasios Sidiropoulos:
On the geometry of graphs with a forbidden minor. 245-254 - Joshua D. Batson, Daniel A. Spielman
Twice-ramanujan sparsifiers. 255-262 - Luca Trevisan
Max cut and the smallest eigenvalue. 263-272 - Erin W. Chambers
Homology flows, cohomology cuts. 273-282
Optimization
- Moses Charikar
Integrality gaps for Sherali-Adams relaxations. 283-292 - Claire Mathieu, Alistair Sinclair:
Sherali-adams relaxations of the matching polytope. 293-302 - Madhur Tulsiani:
CSP gaps and reductions in the lasserre hierarchy. 303-312 - Marek Karpinski, Warren Schudy:
Linear time approximation schemes for the Gale-Berlekamp game and related minimization problems. 313-322 - Jon Lee
Non-monotone submodular maximization under matroid and knapsack constraints. 323-332
Award papers
- Chris Peikert:
Public-key cryptosystems from the worst-case shortest vector problem: extended abstract. 333-342 - Robin A. Moser:
A constructive proof of the Lovász local lemma. 343-350
Privacy
- Arpita Ghosh, Tim Roughgarden, Mukund Sundararajan:
Universally utility-maximizing privacy mechanisms. 351-360 - Dan Feldman, Amos Fiat, Haim Kaplan, Kobbi Nissim:
Private coresets. 361-370 - Cynthia Dwork, Jing Lei:
Differential privacy and robust statistics. 371-380 - 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. 381-390
Quantum
- Yi-Kai Liu:
Quantum algorithms using the curvelet transform. 391-400 - Amnon Ta-Shma
Short seed extractors against quantum storage. 401-408 - Richard Cleve, Daniel Gottesman
Efficient discrete-time simulations of continuous-time quantum query algorithms. 409-416 - Dorit Aharonov, Itai Arad, Zeph Landau, Umesh V. Vazirani:
The detectability lemma and quantum gap amplification. 417-426
Graphs
- Silvio Lattanzi, D. Sivakumar:
Affiliation networks. 427-434 - Shiri Chechik, Michael Langberg, David Peleg, Liam Roditty:
Fault-tolerant spanners for general graphs. 435-444 - Ken-ichi Kawarabayashi, Bruce A. Reed:
Hadwiger's conjecture is decidable. 445-454 - Virginia Vassilevska, Ryan Williams
Finding, minimizing, and counting weighted subgraphs. 455-464
Complexity II
- Eyal Kushilevitz, Enav Weinreb:
On the complexity of communication complexity. 465-474 - Emanuele Viola:
Bit-probe lower bounds for succinct data structures. 475-482 - Per Austrin, Johan Håstad
Randomly supported independence and resistance. 483-492 - Ryan O'Donnell, Yi Wu:
Conditional hardness for satisfiable 3-CSPs. 493-502
Economics
- Jing Chen, Silvio Micali:
A new approach to auctions and resilient mechanism design. 503-512 - Tim Roughgarden:
Intrinsic robustness of the price of anarchy. 513-522 - Eyal Even-Dar, Yishay Mansour, Uri Nadav:
On the convergence of regret minimization dynamics in concave games. 523-532 - Robert Kleinberg, Georgios Piliouras, Éva Tardos:
Multiplicative updates outperform generic no-regret learning in congestion games: extended abstract. 533-542 - MohammadHossein Bateni, Moses Charikar
MaxMin allocation via degree lower-bounded arborescences. 543-552
Markov chains
- Ravi Montenegro, Prasad Tetali:
How long does it take to catch a wild kangaroo? 553-560 - Ravi Kannan, Hariharan Narayanan
Random walks on polytopes and an affine interior point method for linear programming. 561-570 - Fabio Martinelli
Mixing time for the solid-on-solid model. 571-580 - Allan Sly:
Reconstruction for the Potts model. 581-590 - Martin Dietzfelbinger
Tight lower bounds for greedy routing in uniform small world rings. 591-600
Crypto II
- Yevgeniy Dodis, Daniel Wichs:
Non-malleable extractors and symmetric key cryptography from weak secrets. 601-610 - Iftach Haitner, Omer Reingold, Salil P. Vadhan, Hoeteck Wee:
Inaccessible entropy. 611-620 - Yevgeniy Dodis, Yael Tauman Kalai, Shachar Lovett
On cryptography with auxiliary input. 621-630
Geometry
- Jérémie Chalopin, Daniel Gonçalves:
Every planar graph is the intersection graph of segments in the plane: extended abstract. 631-638 - Boris Aronov
Small-size epsilon-nets for axis-parallel rectangles and boxes. 639-648 - Yuval Rabani
Explicit construction of a small epsilon-net for linear threshold functions. 649-658
Approximation algorithms II
- Anupam Gupta, Amit Kumar
A constant-factor approximation for stochastic Steiner forest. 659-668 - Yossi Azar, Iftah Gamzu, Xiaoxin Yin:
Multiple intents re-ranking. 669-678 - Jivitej S. Chadha, Naveen Garg
A competitive algorithm for minimizing weighted flow time on unrelatedmachines with speed augmentation. 679-684 - Anupam Gupta, Ravishankar Krishnaswamy, R. Ravi:
Online and stochastic survivable network design. 685-694
Complexity III
- Russell Impagliazzo
An axiomatic approach to algebrization. 695-704 - Phokion G. Kolaitis, Swastik Kopparty:
Random graphs and the parity quantifier. 705-714 - Jin-yi Cai, Pinyan Lu
Holant problems and counting CSP. 715-724 - Gábor Kun, Mario Szegedy:
A new line of attack on the dichotomy conjecture. 725-734
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-27 20:17 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: