default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID49th FOCS 2008: Philadelphia, Pennsylvania, USA
- 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, Philadelphia, PA, USA, October 25-28, 2008. IEEE Computer Society 2008, ISBN 978-0-7695-3436-7
Tutorials
- Scott Aaronson:
The Polynomial Method in Quantum and Classical Computing. 3 - Gagan Aggarwal, S. Muthukrishnan:
Theory of Sponsored Search Auctions. 7 - Luca Trevisan
:
Average-case Complexity. 11
Regular Papers
- Peerapong Dhangwatnotai, Shahar Dobzinski, Shaddin Dughmi, Tim Roughgarden:
Truthful Approximation Schemes for Single-Parameter Agents. 15-24 - Constantinos Daskalakis, Christos H. Papadimitriou:
Discretized Multinomial Distributions and Nash Equilibria in Anonymous Games. 25-34 - Maurice Cheung, Chaitanya Swamy:
Approximation Algorithms for Single-minded Envy-free Profit-maximization Problems with Limited Supply. 35-44 - Nikhil R. Devanur, Ravi Kannan:
Market Equilibria in Polynomial Time for Fixed Number of Goods or Agents. 45-53 - Alexander A. Razborov, Alexander A. Sherstov:
The Sign-Rank of AC^O. 57-66 - Manindra Agrawal, V. Vinay:
Arithmetic Circuits: A Chasm at Depth Four. 67-75 - Omer Reingold, Luca Trevisan, Madhur Tulsiani, Salil P. Vadhan:
Dense Subsets of Pseudorandom Sets. 76-85 - Timothy Y. Chow:
Almost-Natural Proofs. 86-91 - Timothy M. Chan, Mihai Patrascu, Liam Roditty:
Dynamic Connectivity: Connecting to Networks and Geometry. 95-104 - Julia Chuzhoy, Sanjeev Khanna:
Algorithms for Single-Source Vertex Connectivity. 105-114 - Glencora Borradaile, Philip N. Klein, Claire Mathieu:
A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest. 115-124 - Yuk Hei Chan, Wai Shing Fung, Lap Chi Lau, Chun Kong Yung:
Degree Bounded Network Design with Metric Costs. 125-134 - Raphael Yuster:
Matrix Sparsification for Rank and Determinant Computations via Nested Dissection. 137-145 - Kiran S. Kedlaya, Christopher Umans:
Fast Modular Composition in any Characteristic. 146-155 - Elchanan Mossel:
Gaussian Bounds for Noise Correlation of Functions and Tight Analysis of Long Codes. 156-165 - Tali Kaufman, Shachar Lovett:
Worst Case to Average Case Reductions for Polynomials. 166-175 - Esther Ezra:
On the Union of Cylinders in Three Dimensions. 179-188 - Guy Kindler, Ryan O'Donnell, Anup Rao, Avi Wigderson:
Spherical Cubes and Rounding in High Dimensions. 189-198 - Piotr Indyk, Milan Ruzic:
Near-Optimal Sparse Recovery in the L1 Norm. 199-207 - Benny Applebaum, Boaz Barak, David Xiao:
On Basing Lower-Bounds for Learning on Worst-Case Assumptions. 211-220 - Michael Ben-Or, Avinatan Hassidim:
The Bayesian Learner is Optimal for Noisy Binary Search (and Pretty Good for Quantum as Well). 221-230 - Subhash Khot, Rishi Saket:
Hardness of Minimizing and Learning DNF Expressions. 231-240 - Ehud Friedgut, Gil Kalai, Noam Nisan:
Elections Can be Manipulated Often. 243-249 - Christos H. Papadimitriou, Michael Schapira, Yaron Singer:
On the Hardness of Being Truthful. 250-259 - Shahar Dobzinski, Ron Lavi, Noam Nisan:
Multi-unit Auctions with Budget Limits. 260-269 - Ran Raz, Amir Yehudayoff:
Multilinear Formulas, Maximal-Partition Discrepancy and Mixed-Sources Extractors. 273-282 - Dan Boneh, Periklis A. Papakonstantinou, Charles Rackoff, Yevgeniy Vahlis, Brent Waters:
On the Impossibility of Basing Identity Based Encryption on Trapdoor Permutations. 283-292 - Stefan Dziembowski, Krzysztof Pietrzak:
Leakage-Resilient Cryptography. 293-302 - Mihai Patrascu:
Succincter. 305-313 - Dana Moshkovitz, Ran Raz:
Two Query PCP with Sub-Constant Error. 314-323 - Huy N. Nguyen, Krzysztof Onak:
Constant-Time Approximation Algorithms via Local Improvements. 327-336 - Ankur Moitra, Tom Leighton:
Some Results on Greedy Embeddings in Metric Spaces. 337-346 - Fabrizio Grandoni, Anupam Gupta, Stefano Leonardi, Pauli Miettinen, Piotr Sankowski, Mohit Singh:
Set Covering with our Eyes Closed. 347-356 - Zachary Friggstad, Mohammad R. Salavatipour:
Minimizing Movement in Mobile Facility Location Problems. 357-366 - Ran Raz:
A Counterexample to Strong Parallel Repetition. 369-373 - Boaz Barak, Moritz Hardt, Ishay Haviv, Anup Rao, Oded Regev, David Steurer:
Rounding Parallel Repetitions of Unique Games. 374-383 - Alexander A. Sherstov:
The Unbounded-Error Communication Complexity of Symmetric Functions. 384-393 - Chinmoy Dutta, Jaikumar Radhakrishnan:
Lower Bounds for Noisy Wireless Networks using Sampling Algorithms. 394-402 - Jirí Matousek, Anastasios Sidiropoulos:
Inapproximability for Metric Embeddings into R^d. 405-413 - Rina Panigrahy, Kunal Talwar, Udi Wieder:
A Geometric Approach to Lower Bounds for Approximate Near-Neighbor Search and Partial Match. 414-423 - Alexandr Andoni, Dorian Croitoru, Mihai Patrascu:
Hardness of Nearest Neighbor under L-infinity. 424-433 - Mihai Patrascu:
(Data) STRUCTURES. 434-443 - Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Ben Toner, Thomas Vidick:
Entangled Games are Hard to Approximate. 447-456 - Julia Kempe, Oded Regev, Ben Toner:
Unique Games with Entangled Provers are Easy. 457-466 - Michael Ben-Or, Avinatan Hassidim, Haran Pilpel:
Quantum Multi Prover Interactive Proofs with Communicating Provers. 467-476 - Avraham Ben-Aroya, Oded Regev, Ronald de Wolf:
A Hypercontractive Inequality for Matrix-Valued Functions with Applications to Quantum Computing and LDCs. 477-486 - Nicholas J. A. Harvey, Jelani Nelson, Krzysztof Onak:
Sketching and Streaming Entropy via Approximation Theory. 489-498 - Paul Beame, Dang-Trinh Huynh-Ngoc:
On the Value of Multiple Read/Write Streams for Approximating Frequency Moments. 499-508 - Christoph Lenzen, Thomas Locher, Roger Wattenhofer:
Clock Synchronization with Bounded Global and Local Skew. 509-518 - Yefim Dinitz, Michael Elkin, Shay Solomon:
Shallow-Low-Light Trees, and Tight Lower Bounds for Euclidean Spanners. 519-528 - Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, Adam D. Smith:
What Can We Learn Privately? 531-540 - Adam R. Klivans, Ryan O'Donnell, Rocco A. Servedio:
Learning Geometric Concepts via Gaussian Surface Area. 541-550 - S. Charles Brubaker, Santosh S. Vempala:
Isotropic PCA and Affine-Invariant Clustering. 551-560 - Subhash Khot, Assaf Naor:
Approximate Kernel Clustering. 561-570 - Venkatesan Guruswami, Rajsekar Manokaran, Prasad Raghavendra:
Beating the Random Ordering is Hard: Inapproximability of Maximum Acyclic Subgraph. 573-582 - Monaldo Mastrolilli, Ola Svensson:
(Acyclic) JobShops are Hard to Approximate. 583-592 - Grant Schoenebeck:
Linear Level Lasserre Lower Bounds for Certain k-CSPs. 593-602 - Matthias Englert, Deniz Özmen, Matthias Westermann:
The Power of Reordering for Online Minimum Makespan Scheduling. 603-612 - Irit Dinur, Elazar Goldenberg:
Locally Testing Direct Product in the Low Error Range. 613-622 - Zeev Dvir, Avi Wigderson:
Kakeya Sets, New Mergers and Old Extractors. 625-633 - Siu On Chan, Michael Molloy:
A Dichotomy Theorem for the Resolution Complexity of Random Constraint Satisfaction Problems. 634-643 - Jin-yi Cai, Pinyan Lu, Mingji Xia:
Holographic Algorithms by Fibonacci Gates and Holographic Reductions for Hardness. 644-653 - Yael Tauman Kalai, Xin Li, Anup Rao, David Zuckerman:
Network Extractor Protocols. 654-663 - László Babai, Paolo Codenotti:
Isomorhism of Hypergraphs of Low Rank in Moderately Exponential Time. 667-676 - Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto:
Computing the Tutte Polynomial in Vertex-Exponential Time. 677-686 - Deeparnab Chakrabarty, Gagan Goel:
On the Approximability of Budgeted Allocations and Improved Lower Bounds for Submodular Welfare Maximization and GAP. 687-696 - Zoya Svitkina, Lisa Fleischer:
Submodular Approximation: Sampling-based Algorithms and Lower Bounds. 697-706 - Eli Ben-Sasson, Jakob Nordström:
Short Proofs May Be Spacious: An Optimal Separation of Space and Length in Resolution. 709-718 - Satyen Kale, Yuval Peres, C. Seshadhri:
Noise Tolerance of Expanders and Sublinear Expander Reconstruction. 719-728 - Sébastien Roch:
Sequence Length Requirement of Distance-Based Phylogeny Reconstruction: Breaking the Polynomial Barrier. 729-738 - Albert Atserias, Martin Grohe, Dániel Marx:
Size Bounds and Query Plans for Relational Joins. 739-748 - Punyashloka Biswal, James R. Lee, Satish Rao:
Eigenvalue Bounds, Spectral Partitioning, and Metrical Deformations via Flows. 751-760 - Amit Chakrabarti, Alexander Jaffe, James R. Lee, Justin Vincent:
Embeddings of Topological Graphs: Lossy Invariants, Linearization, and 2-Sums. 761-770 - Ken-ichi Kawarabayashi, Bojan Mohar, Bruce A. Reed:
A Simpler Linear Time Algorithm for Embedding Graphs into an Arbitrary Surface and the Genus of Graphs of Bounded Tree-Width. 771-780 - Ittai Abraham, Yair Bartal, Ofer Neiman:
Nearly Tight Low Stretch Spanning Trees. 781-790 - Dimitris Achlioptas, Amin Coja-Oghlan:
Algorithmic Barriers from Phase Transitions. 793-802 - Shankar Bhamidi, Guy Bresler, Allan Sly:
Mixing Time of Exponential Random Graphs. 803-812 - Noga Alon, Asaf Nussboim:
k-Wise Independent Random Graphs. 813-822 - Noga Alon, Eyal Lubetzky, Uri Stav, Amit Weinstein, Avinatan Hassidim:
Broadcasting with Side Information. 823-832
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-12-04 22:23 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:
