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