49. FOCS 2008: Philadelphia, Pennsylvania, USA

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 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 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