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