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
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 - Omer Reingold, Luca Trevisan, Madhur Tulsiani, Salil P. Vadhan:
Dense Subsets of Pseudorandom Sets. 76-85 - Timothy M. Chan, Mihai Patrascu, Liam Roditty:
Dynamic Connectivity: Connecting to Networks and Geometry. 95-104 - 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 - Elchanan Mossel:
Gaussian Bounds for Noise Correlation of Functions and Tight Analysis of Long Codes. 156-165 - Guy Kindler, Ryan O'Donnell, Anup Rao, Avi Wigderson:
Spherical Cubes and Rounding in High Dimensions. 189-198 - 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 - Christos H. Papadimitriou, Michael Schapira, Yaron Singer:
On the Hardness of Being Truthful. 250-259 - 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 - Huy N. Nguyen, Krzysztof Onak:
Constant-Time Approximation Algorithms via Local Improvements. 327-336 - 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 - Boaz Barak, Moritz Hardt, Ishay Haviv, Anup Rao, Oded Regev, David Steurer:
Rounding Parallel Repetitions of Unique Games. 374-383 - Chinmoy Dutta, Jaikumar Radhakrishnan:
Lower Bounds for Noisy Wireless Networks using Sampling Algorithms. 394-402 - 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 - Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Ben Toner, Thomas Vidick:
Entangled Games are Hard to Approximate. 447-456 - 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 - Venkatesan Guruswami, Rajsekar Manokaran, Prasad Raghavendra:
Beating the Random Ordering is Hard: Inapproximability of Maximum Acyclic Subgraph. 573-582 - Matthias Englert, Deniz Özmen, Matthias Westermann:
The Power of Reordering for Online Minimum Makespan Scheduling. 603-612 - 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 - 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 - Noga Alon, Eyal Lubetzky, Uri Stav, Amit Weinstein, Avinatan Hassidim:
Broadcasting with Side Information. 823-832
maintained by 
at 
at 
last updated on 2018-12-17 22:39 CET by the dblp team
data released under the ODC-BY 1.0 license
see also: Terms of Use | Privacy Policy | Imprint