48. FOCS 2007: Providence, RI, USA

Tutorials

• Terence Tao:
  Structure and Randomness in Combinatorics. 3-15
  
• Dan Boneh:
  A Brief Look at Pairings Based Cryptography. 19-26
  
• Daniel A. Spielman:
  Spectral Graph Theory and its Applications. 29-38
  

Regular Papers

• Andrej Bogdanov, Emanuele Viola:
  Pseudorandom Bits for Polynomials. 41-51
  
• Zeev Dvir, Ariel Gabizon, Avi Wigderson:
  Extractors and Rank Extractors for Polynomial Sources. 52-62
  
• Louay Bazzi:
  Polylogarithmic Independence Can Fool DNF Formulas. 63-73
  
• Qi Cheng:
  Derandomization of Sparse Cyclotomic Integer Zero Testing. 74-80
  
• Constantinos Daskalakis, Christos H. Papadimitriou:
  Computing Equilibria in Anonymous Games. 83-93
  
• Frank McSherry, Kunal Talwar:
  Mechanism Design via Differential Privacy. 94-103
  
• Nicole Immorlica, Anna R. Karlin, Mohammad Mahdian, Kunal Talwar:
  Balloon Popping With Applications to Ascending Auctions. 104-112
  
• Kousha Etessami, Mihalis Yannakakis:
  On the Complexity of Nash Equilibria and Other Fixed Points (Extended Abstract). 113-123
  
• Xi Chen, Shang-Hua Teng:
  Paths Beyond Local Search: A Tight Bound for Randomized Fixed-Point Computation. 124-134
  
• Philipp Hertel, Toniann Pitassi:
  Exponential Time/Space Speedups for Resolution and the PSPACE-completeness of Black-White Pebbling. 137-149
  
• Stefan S. Dantchev, Barnaby Martin, Stefan Szeider:
  Parameterized Proof Complexity. 150-160
  
• Eyal Lubetzky, Uri Stav:
  Non-Linear Index Coding Outperforming the Linear Optimum. 161-168
  
• Dániel Marx:
  Can you beat treewidth? 169-179
  
• Daniel Stefankovic, Santosh Vempala, Eric Vigoda:
  Adaptive Simulated Annealing: A Near-optimal Connection between Sampling and Counting. 183-193
  
• Antoine Gerschenfeld, Andrea Montanari:
  Reconstruction for Models on Random Graphs. 194-204
  
• Yun Long, Asaf Nachmias, Yuval Peres:
  Mixing Time Power Laws at Criticality. 205-214
  
• Jeong Han Kim, Ravi Montenegro, Prasad Tetali:
  Near Optimal Bounds for Collision in Pollard Rho for Discrete Log. 215-223
  
• Stefan Dziembowski, Krzysztof Pietrzak:
  Intrusion-Resilient Secret Sharing. 227-237
  
• Nishanth Chandran, Vipul Goyal, Rafail Ostrovsky, Amit Sahai:
  Covert Multi-Party Computation. 238-248
  
• Ran Canetti, Rafael Pass, Abhi Shelat:
  Cryptography from Sunspots: How to Use an Imperfect Reference String. 249-259
  
• Mihai Patrascu, Mikkel Thorup:
  Planning for Fast Connectivity Updates. 263-271
  
• Guy E. Blelloch, Daniel Golovin:
  Strongly History-Independent Hashing with Applications. 272-282
  
• Vladimir Braverman, Rafail Ostrovsky:
  Smooth Histograms for Sliding Windows. 283-293
  
• Anna Gál, Parikshit Gopalan:
  Lower Bounds on Streaming Algorithms for Approximating the Length of the Longest Increasing Subsequence. 294-304
  
• Per Austrin:
  Towards Sharp Inapproximability For Any 2-CSP. 307-317
  
• Subhash Khot, Assaf Naor:
  Linear Equations Modulo 2 and the L1 Diameter of Convex Bodies. 318-328
  
• Christoph Ambühl, Monaldo Mastrolilli, Ola Svensson:
  Inapproximability Results for Sparsest Cut, Optimal Linear Arrangement, and Precedence Constrained Scheduling. 329-337
  
• Dániel Marx:
  On the Optimality of Planar and Geometric Approximation Schemes. 338-348
  
• Parikshit Gopalan, Subhash Khot, Rishi Saket:
  Hardness of Reconstructing Multivariate Polynomials over Finite Fields. 349-359
  
• Andris Ambainis, Andrew M. Childs, Ben Reichardt, Robert Spalek, Shengyu Zhang:
  Any AND-OR Formula of Size N can be Evaluated in time N^1/2+o(1) on a Quantum Computer. 363-372
  
• Dorit Aharonov, Daniel Gottesman, Sandy Irani, Julia Kempe:
  The Power of Quantum Systems on a Line. 373-383
  
• Oded Regev, Ben Toner:
  Simulating Quantum Correlations with Finite Communication. 384-394
  
• Andrew M. Childs, Leonard J. Schulman, Umesh V. Vazirani:
  Quantum Algorithms for Hidden Nonlinear Structures. 395-404
  
• Uriel Feige:
  Refuting Smoothed 3CNF Formulas. 407-417
  
• Andrej Bogdanov, Muli Safra:
  Hardness Amplification for Errorless Heuristics. 418-426
  
• Emanuele Viola, Avi Wigderson:
  One-Way Multi-Party Communication Lower Bound for Pointer Jumping with Applications. 427-437
  
• Ran Raz, Amir Shpilka, Amir Yehudayoff:
  A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits. 438-448
  
• Arkadev Chattopadhyay:
  Discrepancy and the Power of Bottom Fan-in in Depth-three Circuits. 449-458
  
• Uriel Feige, Vahab S. Mirrokni, Jan Vondrák:
  Maximizing Non-Monotone Submodular Functions. 461-471
  
• Jonathan A. Kelner, Evdokia Nikolova:
  On the Hardness and Smoothed Complexity of Quasi-Concave Minimization. 472-482
  
• Sudipto Guha, Kamesh Munagala:
  Approximation Algorithms for Partial-Information Based Stochastic Control with Markovian Rewards. 483-493
  
• Christos Koufogiannakis, Neal E. Young:
  Beating Simplex for Fractional Packing and Covering Linear Programs. 494-504
  
• Nikhil Bansal, Niv Buchbinder, Joseph Naor:
  A Primal-Dual Randomized Algorithm for Weighted Paging. 507-517
  
• Noga Alon, Michael R. Capalbo:
  Finding Disjoint Paths in Expanders Deterministically and Online. 518-524
  
• Esther Ezra, Micha Sharir:
  Almost Tight Bound for the Union of Fat Tetrahedra in Three Dimensions. 525-535
  
• Paul Bendich, David Cohen-Steiner, Herbert Edelsbrunner, John Harer, Dmitriy Morozov:
  Inferring Local Homology from Sampled Stratified Spaces. 536-546
  
• Ilias Diakonikolas, Homin K. Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco A. Servedio, Andrew Wan:
  Testing for Concise Representations. 549-558
  
• Sofya Raskhodnikova, Dana Ron, Amir Shpilka, Adam Smith:
  Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem. 559-569
  
• Artur Czumaj, Christian Sohler:
  Testing Expansion in Bounded-Degree Graphs. 570-578
  
• Eldar Fischer, Arie Matsliah, Asaf Shapira:
  Approximate Hypergraph Partitioning and Applications. 579-589
  
• Tali Kaufman, Madhu Sudan:
  Sparse Random Linear Codes are Locally Decodable and Testable. 590-600
  
• Naveen Garg, Amit Kumar:
  Minimizing Average Flow-time : Upper and Lower Bounds. 603-613
  
• Nikhil Bansal, Ho-Leung Chan, Rohit Khandekar, Kirk Pruhs, Clifford Stein, Baruch Schieber:
  Non-Preemptive Min-Sum Scheduling with Resource Augmentation. 614-624
  
• Moses Charikar, Konstantin Makarychev, Yury Makarychev:
  On the Advantage over Random for Maximum Acyclic Subgraph. 625-633
  
• Spyridon Antonakopoulos, Chandra Chekuri, F. Bruce Shepherd, Lisa Zhang:
  Buy-at-Bulk Network Design with Protection. 634-644
  
• Dan Boneh, Craig Gentry, Michael Hamburg:
  Space-Efficient Identity Based Encryption Without Pairings. 647-657
  
• Juan A. Garay, Jonathan Katz, Chiu-Yuen Koo, Rafail Ostrovsky:
  Round Complexity of Authenticated Broadcast with a Dishonest Majority. 658-668
  
• Iftach Haitner, Jonathan J. Hoch, Omer Reingold, Gil Segev:
  Finding Collisions in Interactive Protocols - A Tight Lower Bound on the Round Complexity of Statistically-Hiding Commitments. 669-679
  
• Boaz Barak, Mohammad Mahmoody-Ghidary:
  Lower Bounds on Signatures From Symmetric Primitives. 680-688
  
• Eden Chlamtac:
  Approximation Algorithms Using Hierarchies of Semidefinite Programming Relaxations. 691-701
  
• Konstantinos Georgiou, Avner Magen, Toniann Pitassi, Iannis Tourlakis:
  Integrality gaps of 2 - o(1) for Vertex Cover SDPs in the Lovész-Schrijver Hierarchy. 702-712
  
• Moses Charikar, Konstantin Makarychev, Yury Makarychev:
  Local Global Tradeoffs in Metric Embeddings. 713-723
  
• Alexandr Andoni, Robert Krauthgamer:
  The Computational Hardness of Estimating Edit Distance [Extended Abstract]. 724-734