default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID37th STOC 2005: Baltimore, MD, USA
- Harold N. Gabow, Ronald Fagin:
Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22-24, 2005. ACM 2005, ISBN 1-58113-960-8
Session 1A
- Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, Avi Wigderson:
Simulating independence: new constructions of condensers, ramsey graphs, dispersers, and extractors. 1-10 - Ran Raz
:
Extractors with weak random seeds. 11-20 - Andrej Bogdanov:
Pseudorandom generators for low degree polynomials. 21-30 - Luca Trevisan:
On uniform amplification of hardness in NP. 31-38
Session 1B
- Patrick Briest, Piotr Krysta, Berthold Vöcking:
Approximation techniques for utilitarian mechanism design. 39-48 - Christos H. Papadimitriou:
Computing correlated equilibria in multi-player games. 49-56 - Baruch Awerbuch, Yossi Azar, Amir Epstein:
The Price of Routing Unsplittable Flow. 57-66 - George Christodoulou, Elias Koutsoupias:
The price of anarchy of finite congestion games. 67-73 - Bruno Codenotti, Benton McCune, Kasturi R. Varadarajan:
Market equilibrium via the excess demand function. 74-83
Session 2A
- Oded Regev:
On lattices, learning with errors, random linear codes, and cryptography. 84-93 - Miklós Ajtai:
Representing hard lattices with O(n log n) bits. 94-103
Session 2B
- Christian Worm Mortensen, Rasmus Pagh, Mihai Patrascu:
On dynamic range reporting in one dimension. 104-111 - Mikkel Thorup:
Worst-case update times for fully-dynamic all-pairs shortest paths. 112-119
Keynote
- Lance Fortnow:
Beyond NP: the work and legacy of Larry Stockmeyer. 120-127
Session 4A
- Noga Alon, Asaf Shapira:
Every monotone graph property is testable. 128-137 - Eldar Fischer, Ilan Newman:
Testing versus estimation of graph properties. 138-146 - Ronitt Rubinfeld, Rocco A. Servedio:
Testing monotone high-dimensional distributions. 147-156 - Katalin Friedl, Gábor Ivanyos, Miklos Santha:
Efficient testing of groups. 157-166
Session 4B
- Joseph Cheriyan, Adrian Vetta:
Approximation algorithms for network design with metric costs. 167-175 - Moses Charikar, Adriana Karagiozova:
On non-uniform multicommodity buy-at-bulk network design. 176-182 - Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd:
Multicommodity flow, well-linked terminals, and routing problems. 183-192 - Mohammad Taghi Hajiaghayi, Jeong Han Kim, Tom Leighton, Harald Räcke:
Oblivious routing in directed graphs with random demands. 193-201
Session 5A
- Piotr Indyk, David P. Woodruff:
Optimal approximations of the frequency moments of data streams. 202-208 - Gereon Frahling, Christian Sohler:
Coresets in dynamic geometric data streams. 209-217 - Rafail Ostrovsky, Yuval Rabani:
Low distortion embeddings for edit distance. 218-224 - Mihai Badoiu, Julia Chuzhoy, Piotr Indyk, Anastasios Sidiropoulos:
Low-distortion embeddings of general metrics into the line. 225-233
Session 5B
- Mikolaj Bojanczyk, Thomas Colcombet:
Tree-walking automata do not recognize all regular languages. 234-243 - Itai Benjamini, Oded Schramm, David Bruce Wilson:
Balanced boolean functions that can be evaluated so that every input bit is unlikely to be read. 244-250 - Michael Alekhnovich:
Lower bounds for k-DNF resolution on random 3-CNFs. 251-256 - Michal Koucký, Pavel Pudlák, Denis Thérien:
Bounded-depth circuits: separating wires from gates. 257-265
Session 6A
- Eli Ben-Sasson, Madhu Sudan:
Simple PCPs with poly-log rate and query complexity. 266-275 - Matthew Andrews, Lisa Zhang:
Hardness of the undirected edge-disjoint paths problem. 276-283 - Matthew Andrews, Lisa Zhang:
Hardness of the undirected congestion minimization problem. 284-293 - Michael Alekhnovich, Sanjeev Arora, Iannis Tourlakis:
Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy. 294-303
Session 6B
- Saugata Basu, Richard Pollack, Marie-Françoise Roy:
Computing the first Betti number and the connected components of semi-algebraic sets. 304-312 - Saugata Basu:
Polynomial time algorithm for computing the top Betti numbers of semi-algebraic sets defined by quadratic inequalities. 313-322 - Xi Chen, Xiaotie Deng:
On algorithms for discrete and approximate brouwer fixed points. 323-330 - Yossi Azar, Amir Epstein:
Convex programming for scheduling unrelated parallel machines. 331-337
Session 7A
- Saurabh Sanghvi, Salil P. Vadhan:
The round complexity of two-party random selection. 338-347 - Lance Fortnow, Rahul Santhanam, Luca Trevisan:
Hierarchies for semantic classes. 348-355
Session 7B
- Haim Kaplan, Eyal Kushilevitz, Yishay Mansour:
Learning with attribute costs. 356-365 - Elchanan Mossel, Sébastien Roch:
Learning nonsingular phylogenies and hidden Markov models. 366-375
Best Paper
- Omer Reingold:
Undirected ST-connectivity in log-space. 376-385
Session 9A
- Lujun Jia, Guolong Lin, Guevara Noubir, Rajmohan Rajaraman, Ravi Sundaram:
Universal approximations for TSP, Steiner tree, and set cover. 386-395 - Naveen Garg:
Saving an epsilon: a 2-approximation for the k-MST problem in graphs. 396-402 - Ben Morris:
The mixing time of the Thorp shuffle. 403-412 - Mary Cryan, Martin E. Dyer, Dana Randall:
Approximately counting integral flows and cell-bounded contingency tables. 413-422
Session 9B
- Van H. Vu:
Spectral norm of random matrices. 423-430 - Terence Tao, Van H. Vu:
On random pm 1 matrices: singularity and determinant. 431-440 - Abraham Flaxman, Alan M. Frieze, Juan Carlos Vera:
On the average case performance of some greedy approximation algorithms for the uncapacitated facility location problem. 441-449 - Micah Adler, Jeff Edmonds, Jirí Matousek:
Towards asymptotic optimality in probabilistic packet marking. 450-459
Session 10A
- Yaoyun Shi:
Tensor norms and the classical communication complexity of nonlocal quantum measurement. 460-467 - Sean Hallgren:
Fast quantum algorithms for computing the unit group and class group of a number field. 468-474 - Arthur Schmidt, Ulrich Vollmer:
Polynomial time quantum algorithm for the computation of the unit group of a number field. 475-480 - Michael Ben-Or, Avinatan Hassidim:
Fast quantum byzantine agreement. 481-485
Session 10B
- Noga Alon, Konstantin Makarychev, Yury Makarychev, Assaf Naor:
Quadratic forms on graphs. 486-493 - Michael Elkin, Yuval Emek, Daniel A. Spielman, Shang-Hua Teng:
Lower-stretch spanning trees. 494-503 - Daniel Gonçalves:
Edge partition of planar sraphs into two outerplanar graphs. 504-512
Session 11A
- Luis von Ahn, Nicholas J. Hopper, John Langford:
Covert two-party computation. 513-522 - Hoeteck Wee:
On obfuscating point functions. 523-532 - Rafael Pass, Alon Rosen:
New and improved constructions of non-malleable cryptographic protocols. 533-542 - Matt Lepinski, Silvio Micali, Abhi Shelat:
Collusion-free protocols. 543-552
Session 11B
- Sanjeev Arora, James R. Lee, Assaf Naor:
Euclidean distortion and the sparsest cut. 553-562 - Uriel Feige, Mohammad Taghi Hajiaghayi, James R. Lee:
Improved approximation algorithms for minimum-weight vertex separators. 563-572 - Amit Agarwal, Moses Charikar, Konstantin Makarychev, Yury Makarychev:
O(sqrt(log n)) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems. 573-581 - Joseph Naor, Roy Schwartz:
Balanced metric labeling. 582-591
Session 12A
- Zeev Dvir, Amir Shpilka:
Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits. 592-601 - Venkatesan Guruswami, Atri Rudra:
Limits to list decoding Reed-Solomon codes. 602-609
Session 12B
- Shahar Dobzinski, Noam Nisan, Michael Schapira:
Approximation algorithms for combinatorial auctions with complement-free bidders. 610-618 - Gagan Aggarwal, Amos Fiat, Andrew V. Goldberg, Jason D. Hartline, Nicole Immorlica, Madhu Sudan:
Derandomization of auctions. 619-625
Best Student Paper
- Vladimir Trifonov:
An O(log n log log n) space algorithm for undirected st-connectivity. 626-633
Session 14A
- Scott Aaronson:
The complexity of agreement. 634-643 - Yael Tauman Kalai, Yehuda Lindell, Manoj Prabhakaran:
Concurrent general composition of secure protocols in the timing model. 644-653 - Yevgeniy Dodis, Adam D. Smith:
Correcting errors without leaking partial information. 654-663 - Thomas Holenstein:
Key agreement from weak bit agreement. 664-673
Session 14B
- Ferdinando Cicalese, Eduardo Sany Laber:
A new strategy for querying priced information. 674-683 - Nir Ailon, Moses Charikar, Alantha Newman:
Aggregating inconsistent information: ranking and clustering. 684-693 - Dimitris Achlioptas, Aaron Clauset, David Kempe, Cristopher Moore:
On the bias of traceroute sampling: or, power-law degree distributions in regular graphs. 694-703 - Christian Scheideler:
How to spread adversarial nodes?: rotate! 704-713
Session 15A
- Eli Gafni, Rachid Guerraoui, Bastian Pochon:
From a static impossibility to an adaptive lower bound: the complexity of early deciding set agreement. 714-722 - Prasad Jayanti:
An optimal multi-writer snapshot algorithm. 723-732 - Bogdan S. Chlebus, Dariusz R. Kowalski:
Cooperative asynchronous update of shared memory. 733-739
Session 15B
- Johan Håstad:
Every 2-CSP allows nontrivial approximation. 740-746 - Wenceslas Fernandez de la Vega, Marek Karpinski, Ravi Kannan, Santosh S. Vempala:
Tensor decomposition and approximation schemes for constraint satisfaction problems. 747-754 - Klaus Jansen, Rob van Stee:
On strip packing With rotations. 755-761
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 2025-11-28 01:47 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:
