47. FOCS 2006: Berkeley, CA, USA

• Minh-Huyen Nguyen, Shien Jin Ong, Salil P. Vadhan:
  Statistical Zero-Knowledge Arguments for NP from Any One-Way Function. 3-14
  
• Shafi Goldwasser, Elan Pavlov, Vinod Vaikuntanathan:
  Fault-Tolerant Distributed Computing in Full-Information Networks. 15-26
  
• Craig Gentry, Zulfikar Ramzan, David P. Woodruff:
  Explicit Exclusive Set Systems with Applications to Broadcast Encryption. 27-38
  
• Thomas P. Hayes:
  A simple condition implying rapid mixing of single-site dynamics on spin systems. 39-46
  
• Mikhail Belkin, Hariharan Narayanan, Partha Niyogi:
  Heat Flow and a Faster Algorithm to Compute the Surface Area of a Convex Body. 47-56
  
• László Lovász, Santosh Vempala:
  Fast Algorithms for Logconcave Functions: Sampling, Rounding, Integration and Optimization. 57-68
  
• Tomás Feder, Adam Guetz, Milena Mihail, Amin Saberi:
  A Local Switch Markov Chain on Given Degree Graphs with Application in Connectivity of Peer-to-Peer Networks. 69-76
  
• Elliot Anshelevich, F. Bruce Shepherd, Gordon T. Wilfong:
  Strategic Network Formation through Peering and Service Agreements. 77-86
  
• Valerie King, Jared Saia, Vishal Sanwalani, Erik Vee:
  Towards Secure and Scalable Computation in Peer-to-Peer Networks. 87-98
  
• James R. Lee, Assaf Naor:
  Lp metrics on the Heisenberg group and the Goemans-Linial conjecture. 99-108
  
• Manor Mendel, Assaf Naor:
  Ramsey partitions and proximity data structures. 109-118
  
• Robert Krauthgamer, James R. Lee:
  Algorithms on negatively curved spaces. 119-132
  
• Roman Vershynin:
  Beyond Hirsch Conjecture: Walks on Random Polytopes and Smoothed Complexity of the Simplex Method. 133-142
  
• Tamás Sarlós:
  Improved Approximation Algorithms for Large Matrices via Random Projections. 143-152
  
• David Arthur, Sergei Vassilvitskii:
  Worst-case and Smoothed Analysis of the ICP Algorithm, with an Application to the k-means Method. 153-164
  
• Rafail Ostrovsky, Yuval Rabani, Leonard J. Schulman, Chaitanya Swamy:
  The Effectiveness of Lloyd-Type Methods for the k-Means Problem. 165-176
  
• Amnon Ta-Shma, Christopher Umans:
  Better lossless condensers through derandomized curve samplers. 177-186
  
• Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets:
  Approximately List-Decoding Direct Product Codes and Uniform Hardness Amplification. 187-196
  
• Ziv Bar-Yossef, Yitzhak Birk, T. S. Jayram, Tomer Kol:
  Index Coding with Side Information. 197-206
  
• Eli Ben-Sasson, Swastik Kopparty, Jaikumar Radhakrishnan:
  Subspace Polynomials and List Decoding of Reed-Solomon Codes. 207-216
  
• Subhash Khot, Ryan O'Donnell:
  SDP gaps and UGC-hardness for MAXCUTGAIN. 217-226
  
• Venkatesan Guruswami, Anindya C. Patthak:
  Correlated Algebraic-Geometric Codes: Improved List Decoding over Bounded Alphabets. 227-238
  
• Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai:
  Cryptography from Anonymity. 239-248
  
• Michael Ben-Or, Claude Crépeau, Daniel Gottesman, Avinatan Hassidim, Adam Smith:
  Secure Multiparty Quantum Computation with (Only) a Strict Honest Majority. 249-260
  
• Xi Chen, Xiaotie Deng:
  Settling the Complexity of Two-Player Nash Equilibrium. 261-272
  
• Michel X. Goemans:
  Minimum Bounded Degree Spanning Trees. 273-282
  
• Tamás Király, Lap Chi Lau:
  Approximate Min-Max Theorems of Steiner Rooted-Orientations of Hypergraphs. 283-292
  
• Niv Buchbinder, Joseph Naor:
  Improved Bounds for Online Routing and Packing Via a Primal-Dual Approach. 293-304
  
• Lars Arge, Gerth Stølting Brodal, Loukas Georgiadis:
  Improved Dynamic Planar Point Location. 305-314
  
• Dan Feldman, Amos Fiat, Micha Sharir:
  Coresets forWeighted Facilities and Their Applications. 315-324
  
• Mihai Patrascu:
  Planar Point Location in Sublogarithmic Time. 325-332
  
• Timothy M. Chan:
  Point Location in o(log n) Time, Voronoi Diagrams in o(n log n) Time, and Other Transdichotomous Results in Computational Geometry. 333-344
  
• Boaz Barak, Manoj Prabhakaran, Amit Sahai:
  Concurrent Non-Malleable Zero Knowledge. 345-354
  
• Yael Tauman Kalai, Ran Raz:
  Succinct Non-Interactive Zero-Knowledge Proofs with Preprocessing for LOGSNP. 355-366
  
• Silvio Micali, Rafael Pass, Alon Rosen:
  Input-Indistinguishable Computation. 367-378
  
• Krzysztof Onak, Pawel Parys:
  Generalization of Binary Search: Searching in Trees and Forest-Like Partial Orders. 379-388
  
• David P. Woodruff:
  Lower Bounds for Additive Spanners, Emulators, and More. 389-398
  
• Nadine Baumann, Martin Skutella:
  Solving Evacuation Problems Efficiently--Earliest Arrival Flows with Multiple Sources. 399-410
  
• Harry Buhrman, Richard Cleve, Monique Laurent, Noah Linden, Alexander Schrijver, Falk Unger:
  New Limits on Fault-Tolerant Quantum Computation. 411-419
  
• Ben Reichardt:
  Postselection threshold against biased noise. 420-428
  
• Xiaoming Sun, Andrew Chi-Chih Yao:
  On the Quantum Query Complexity of Local Search in Two and Three Dimensions. 429-438
  
• Damien Woods, Turlough Neary:
  On the time complexity of 2-tag systems and small universal Turing machines. 439-448
  
• Alexandr Andoni, Piotr Indyk, Mihai Patrascu:
  On the Optimality of the Dimensionality Reduction Method. 449-458
  
• Alexandr Andoni, Piotr Indyk:
  Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions. 459-468
  
• Xiaoyang Gu, Jack H. Lutz, Elvira Mayordomo:
  Points on Computable Curves. 469-474
  
• Reid Andersen, Fan R. K. Chung, Kevin J. Lang:
  Local Graph Partitioning using PageRank Vectors. 475-486
  
• Mark Rudelson:
  Norm of the inverse of a random matrix. 487-496
  
• Uriel Feige, Jeong Han Kim, Eran Ofek:
  Witnesses for non-satisfiability of dense random 3CNF formulas. 497-508
  
• Leslie G. Valiant:
  Accidental Algorthims. 509-517
  
• Christian Borgs, Jennifer T. Chayes, Elchanan Mossel, Sébastien Roch:
  The Kesten-Stigum Reconstruction Bound Is Tight for Roughly Symmetric Binary Channels. 518-530
  
• Nicholas J. A. Harvey:
  Algebraic Structures and Algorithms for Matching and Matroid Problems. 531-542
  
• Venkatesan Guruswami, Prasad Raghavendra:
  Hardness of Learning Halfspaces with Noise. 543-552
  
• Adam R. Klivans, Alexander A. Sherstov:
  Cryptographic Hardness for Learning Intersections of Halfspaces. 553-562
  
• Vitaly Feldman, Parikshit Gopalan, Subhash Khot, Ashok Kumar Ponnuswami:
  New Results for Learning Noisy Parities and Halfspaces. 563-574
  
• Andreas Björklund, Thore Husfeldt:
  Inclusion--Exclusion Algorithms for Counting Set Partitions. 575-582
  
• Mikko Koivisto:
  An O*(2^n ) Algorithm for Graph Coloring and Other Partitioning Problems via Inclusion--Exclusion. 583-590
  
• Surender Baswana, Telikepalli Kavitha:
  Faster Algorithms for Approximate Distance Oracles and All-Pairs Small Stretch Paths. 591-602
  
• Xi Chen, Xiaotie Deng, Shang-Hua Teng:
  Computing Nash Equilibria: Approximation and Smoothed Complexity. 603-612
  
• Heiner Ackermann, Heiko Röglin, Berthold Vöcking:
  On the Impact of Combinatorial Structure on Congestion Games. 613-622
  
• Jeff Edmonds, Kirk Pruhs:
  Balanced Allocations of Cake. 623-634
  
• Uli Wagner:
  On a Geometric Generalization of the Upper Bound Theorem. 635-645
  
• Mihai Patrascu, Mikkel Thorup:
  Higher Lower Bounds for Near-Neighbor and Further Rich Problems. 646-654
  
• Assaf Naor, Gideon Schechtman:
  Planar Earthmover is not in L_1. 655-666
  
• Uriel Feige, Jan Vondrák:
  Approximation algorithms for allocation problems: Improving the factor of 1 - 1/e. 667-676
  
• Chandra Chekuri, Mohammad Taghi Hajiaghayi, Guy Kortsarz, Mohammad R. Salavatipour:
  Approximation Algorithms for Non-Uniform Buy-at-Bulk Network Design. 677-686
  
• Eden Chlamtac, Konstantin Makarychev, Yury Makarychev:
  How to Play Unique Games Using Embeddings. 687-696
  
• Nikhil Bansal, Alberto Caprara, Maxim Sviridenko:
  Improved approximation algorithms for multidimensional bin packing problems. 697-708
  
• Arkadev Chattopadhyay, Navin Goyal, Pavel Pudlák, Denis Thérien:
  Lower bounds for circuits with MOD_m gates. 709-718
  
• Danny Harnik, Moni Naor:
  On the Compressibility of NP Instances and Cryptographic Applications. 719-728
  
• Luis Rademacher, Santosh Vempala:
  Dispersion of Mass and the Complexity of Randomized Geometric Algorithms. 729-738
  
• Alexander A. Razborov, Sergey Yekhanin:
  An Omega(n^1/3) Lower Bound for Bilinear Group Based Private Information Retrieval. 739-748