FOCS 2010 Accepted Papers (with pdf files)

FOCS 2010 accepted paper list is here and list with abstracts is here. Following are PDF pointers to online versions.

1. Settling the Polynomial Learnability of Mixtures of Gaussians [arXiv]
   Authors: Ankur Moitra (MIT) and Gregory Valiant (UC Berkeley)
2. Solving linear systems through nested dissection [pdf]
   Authors: Noga Alon (Tel Aviv University) Raphael Yuster (University of Haifa)
3. Improved Bounds for Geometric Permutations [arXiv]
   Authors: Natan Rubin, Haim Kaplan and Micha Sharir (Tel Aviv University)
4. Constructive Algorithms for Discrepancy Minimization [arXiv]
   Authors: Nikhil Bansal (IBM Research)
5. An efficient test for product states, with applications to quantum Merlin-Arthur games [arXiv]
   Authors:Aram W. Harrow: Department of Mathematics, University of Bristol & Departmenty of Computer Science and Engineering, University of Washington and Ashley Montanaro: Department of Computer Science, University of Bristol and Department of Applied Mathematics and Theoretical Physics, University of Cambridge
6. Replacement Paths via Fast Matrix Multiplication [pdf]
   Authors: Oren Weimann (Weizmann Institute of Science) Raphael Yuster (University of Haifa)
7. Logspace Versions of the Theorems of Bodlaender and Courcelle [ECCC]
   Authors: Michael Elberfeld, Andreas Jakoby, Till Tantau, Institute of Theoretical Computer Science, University of Lubeck, Germany.
8. Impossibility of Differentially Private Universally Optimal Mechanisms [arXiv]
   Authors : Kobbi Nissim (Microsoft AI, Israel, and Dept. of Computer Science, Ben-Gurion University) Hai Brenner (Dept. of Mathematics, Ben-Gurion University)
9. Determinant Sums for Undirected Hamiltonicity [arXiv]
   Author: Andreas Bjorklund, Lund University, Department of Computer Science, P.O.Box 118, SE-22100 Lund, Sweden
10. A non-linear lower bound for planar epsilon-nets [pdf]
    Author: Noga Alon, Tel Aviv University and IAS, Princeton
11. Pseudorandom generators for CC_0[p] and the Fourier spectrum of low-degree polynomials over finite fields [ECCC]
    Authors: Shachar Lovett, The Weizmann Institute of Science, Partha Mukhopadhyay, Technion – Israel Institute of Technology, Amir Shpilka, Technion – Israel Institute of Technology
12. A lower bound for dynamic approximate membership data structures [ECCC]
    Authors: Shachar Lovett and Ely Porat
13. A Decidable Dichotomy Theorem on Directed Graph Homomorphisms with Non-negative Weights [pdf]
    Authors: Jin-Yi Cai: University of Wisconsin – Madison Xi Chen: University of Southern California
14. The Geometry of Manipulation – a Quantitative Proof of the Gibbard Satterthwaite Theorem [arXiv]
    Authors: Marcus Isaksson and Guy Kindler and Elchanan Mossel
15. Optimal Testing of Reed-Muller Codes [ECCC]
    Authors: Arnab Bhattacharyya (MIT) Swastik Kopparty (MIT) Grant Schoenebeck (UC Berkeley) Madhu Sudan (Microsoft Research New England) David Zuckerman (UT Austin)
16. Pseudorandom generators for regular branching programs. [ECCC]
    Authors: Mark Braverman (MSR New England and University of Toronto), Anup Rao (University of Washington), Ran Raz (Weizmann Institute of Science) and Amir Yehudayoff (IAS and Technion)
17. Local list decoding with a constant number of queries [ECCC]
    Authors: Avraham Ben-Aroya and Klim Efremenko and Amnon Ta-Shma
18. New Constructive Aspects of the Lovasz Local Lemma [arXiv]
    Authors: Bernhard Haeupler (MIT) Barna Saha (University of Maryland) and Aravind Srinivasan (University of Maryland)
19. Matching vector codes [html]
    Authors: Zeev Dvir, Princeton University Parikshit Gopalan, Microsoft Research Sergey Yekhanin, Microsoft Research
20. Approximation Algorithms for the Edge-Disjoint Paths Problem via Raecke Decompositions
    Author: Matthew Andrews, Alcatel-Lucent Bell Laboratories, 600-700 Mountain Avenue, Murray Hill, NJ 07974
21. The complexity of distributions [pdf]
    Author: Emanuele Viola, Northeastern University
22. All-Pairs Shortest Paths in $O(n^2)$ Time With High Probability [video]
    Authors: Yuval Peres, Microsoft Research, Redmond, Dmitry Sotnikov, Tel Aviv University, Benny Sudakov, UCLA, Uri Zwick, Tel Aviv University
23. Computational Transition at the Uniqueness Threshold [arXiv]
    Author: Allan Sly, Microsoft Research, Redmond
24. Strong Fault-Tolerance for Self-Assembly with Fuzzy Temperature  [arXiv]
    Authors: David Doty, University of Western Ontario, Matthew J. Patitz, University of Texas — Pan American, Dustin Reishus, University of Southern California, Robert T. Schweller, University of Texas — Pan American, Scott M. Summers, University of Wisconsin — Platteville
25. Subcubic Equivalences Between Path, Matrix, and Triangle Problems [pdf]
    Authors: Virginia Vassilevska Williams, UC Berkeley and Ryan Williams, IBM Almaden Research Center
26. Minimum-Cost Network Design with (Dis)economies of Scale
    Authors: Matthew Andrews and Spyridon Antonakopoulos and Lisa Zhang, Bell Laboratories, 600-700 Mountain Avenue, Murray Hill, NJ 07974
27. A Unified Framework for Testing Linear-Invariant Properties
    Authors: Arnab Bhattacharyya (MIT), Elena Grigorescu (MIT), Asaf Shapira (Georgia Tech)
28. Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition [arXiv]
    Authors: Amit Chakrabarti, Dartmouth College, Graham Cormode, AT&T Labs — Research, Ranganath Kondapally, Dartmouth College, Andrew McGregor, University of Massachusetts, Amherst
29. Optimal stochastic planarization [arXiv]
    Anastasios Sidiropoulos , Toyota Technological Institute at Chicago
30. Bounds on Monotone Switching Networks for Directed Connectivity [arXiv]
    Author: Aaron Potechin, MIT
31. A Fourier-analytic approach to Reed-Muller decoding [html]
    Parikshit Gopalan, Microsoft Research Silicon Valley.
32. Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP [arXiv]
    Authors: Jin-Yi Cai, University of Wisconsin-Madison and Beijing University, Pinyan Lu, Microsoft Research Asia, and Mingji Xia, Institute of Software, Chinese Academy of Sciences
33. Backyard Cuckoo Hashing: Constant Worst-Case Operations with a Succinct Representation [arXiv]
    Authors: Yuriy Arbitman and Moni Naor and Gil Segev, Weizmann Institute of Science.
34. Vertex Sparsifiers and Abstract Rounding Algorithms [arXiv]
    Moses Charikar (Princeton University), Tom Leighton (MIT and Akamai Technologies, Inc), Shi Li (Princeton University), Ankur Moitra (MIT)
35. Deciding first-order properties for sparse graphs [pdf]
    Authors: Zdenek Dvorak (Charles University, Prague), Daniel Kral (Charles University, Prague), Robin Thomas (Georgia Institute of Technology, Atlanta)
36. Clustering with Spectral Norm and the k-means Algorithm [arXiv]
    Amit Kumar (IIT Delhi) and Ravindran Kannan (Microsoft Research India Lab, Bangalore)
37. Testing Properties of Sparse Images [pdf]
    Authors: Dana Ron and Gilad Tsur, Department of Electrical Engineering – Systems, Tel-Aviv University.
38. Frugal Mechanism Design via Spectral Techniques [arXiv]
    Authors: Ning Chen and Edith Elkind and Nick Gravin and Fedor Petrov
39. A separator theorem in minor-closed classes
    Authors Ken-ichi Kawarabayashi (National Institute of Informatics, Japan) and Bruce Reed (McGill University, Canada, and Sophia Antipolis, France)
40. On the Insecurity of Parallel Repetition for Leakage Resilience [pdf]
    Allison Lewko (University of Texas at Austin) and Brent Waters (University of Texas at Austin)
41. Approaching optimality for solving SDD linear systems [pdf]
    Ioannis Koutis†, Gary L. Miller and Richard Peng, Computer Science Department, Carnegie Mellon University, Pittsburgh, PA 15213
42. The subexponential upper bound for on-line chain partitioning problem
    Authors: Bart\l{}omiej Bosek – Jagiellonian University, Theoretical Computer Science, ul. prof. Stanis\l{}awa \L{}ojasiewicza 6, Krak\'{o}w 30-348, Poland and Tomasz Krawczyk – Jagiellonian University, Theoretical Computer Science, ul. prof. Stanis\l{}awa \L{}ojasiewicza 6, Krak\'{o}w 30-348, Poland.
43. One Tree Suffices: A Simultaneous O(1)-Approximation for Single-Sink Buy-at-Bulk [arXiv]
    Authors: Ashish Goel (Stanford University) Ian Post (Stanford University)
44. On the Queue Number of Planar Graphs [pdf]
    Authors: Giuseppe Di Battista, Roma Tre University, Italy, Fabrizio Frati, Roma Tre University, Italy, J\’anos Pach, EPFL Lausanne, Switzerland
45. Cryptography Against Continuous Memory Attacks [ePrint]
    AUthors: Yevgeniy Dodis and Kristiyan Haralambiev and Adriana Lopez-Alt and Daniel Wich
46. Hardness of Finding Independent Sets in Almost 3-Colorable Graphs
    Authors: Irit Dinur and Subhash Khot and Will Perkins and Muli Safra
47. Min st-Cut Oracle for Planar Graphs with Near-Linear Preprocessing Time [arXiv]
    Authors: Glencora Borradaile: School of Electrical Engineering and Computer Science, Oregon State University; Piotr Sankowski: Institute of Informatics, University of Warsaw and Department of Computer and System Science, Sapienza University of Rome; Christian Wulff-Nilsen: Department of Computer Science, University of Copenhagen
48. Codes for Computationally Simple Channels: Explicit Constructions with Optimal Rate [arXiv]
    Authors: Venkatesan Guruswami (Carnegie Mellon University) Adam Smith (Pennsylvania State University)
49. Polynomial Learning of Distribution Families [arXiv]
    Mikhail Belkin (Ohio State University) and Kaushik Sinha (Ohio State University)
50. Overcoming the Hole in the Bucket: Public-Key Cryptography Resilient to Continual Memory Leakage [ePrint]
    Authors: Zvika Brakerski and Yael Tauman Kalai and Jonathan Katz and Vinod Vaikuntanathan
51. Sequential Rationality in Cryptographic Protocols [arXiv]
    Authors: Ronen Gradwohl, Kellogg School of Management, Northwestern University; Noam Livne, Weizmann Institute of Science; Alon Rosen, Herzliya IDC
52. Dependent Randomized Rounding via Exchange Properties of Combinatorial Structures [pdf with different title]
    Authors: Chandra Chekuri Dept. of Computer Science, Univ. of Illinois; Jan Vondrak IBM Almaden Research Center; Rico Zenklusen Dept. of Mathematics, MIT;
53. From Sylvester-Gallai Configurations to Rank Bounds: Improved Black-box Identity Test for Depth-3 Circuits [ECCC]
    Authors: Nitin Saxena, Hausdorff Center for Mathematics, Bonn; C. Seshadhri, IBM Almaden
54. The Geometry of Scheduling [arXiv]
    Authors: Nikhil Bansal (IBM Research) and Kirk Pruhs (Univ. of Pittsburgh)
55. Stability yields a PTAS for k-Median and k-Means Clustering [pdf]
    Authors: Pranjal Awasthi and Avrim Blum and Or Sheffet, Carnegie Mellon University
56. Metric Extension Operators, Vertex Sparsifiers and Lipschitz Extendability
    Authors:Konstantin Makarychev (IBM Research) and Yury Makarychev (TTIC).
57. Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity [arXiv]
    Authors: Alexandr Andoni (Princeton University & Center for Computational Intractability) Robert Krauthgamer (Weizmann Institute) Krzysztof Onak (Massachusetts Institute of Technology)
58. Fast approximation algorithms for flow and cut-based problems in undirected graphs [pdf]
    Author: Aleksander Madry, MIT
59. Efficient volume sampling for row/column subset selection [pdf]
    Amit Deshpande, Microsoft Research India and Luis Rademacher, Computer Science and Engineering, Ohio State University
60. Position-Based Quantum Cryptography [arXiv]
    Authors: Nishanth Chandran (UCLA), Serge Fehr (CWI), Ran Gelles (UCLA), Vipul Goyal (Microsoft Research, India), Rafail Ostrovsky (UCLA)
61. Estimating the longest increasing sequence in polylogarithmic time [pdf]
    Authors: Michael Saks, Rutgers University and C. Seshadhri, IBM Almaden
62. The Monotone Complexity of k-Clique on Random Graphs [pdf]
    Author: Benjamin Rossman, MIT
63. Frugal and Truthful Auctions for Vertex Covers, Flows, and Cuts [arXiv]
    Authors: David Kempe and Mahyar Salek and Cristopher Moore
64. The Coin Problem, and Pseudorandomness for Branching Programs
    Authors: Joshua Brody and Elad Verbin
65. Agnostically learning under permutation invariant distributions
    Author: Karl Wimmer (Duquesne University)
66. Approximating Maximum Weight Matching in Near-linear Time [pdf]
    Ran Duan, University of Michigan and Seth Pettie, University of Michigan
67. Bounded Independence Fools Degree-2 Threshold Functions [ECCC]
    Authors: Ilias Diakonikolas (Columbia), Daniel M. Kane (Harvard), Jelani Nelson (MIT)
68. Boosting and Differential Privacy
    Authors: Cynthia Dwork (Microsoft Research), Guy Rothblum (Princeton University), Salil Vadhan (Harvard University
69. Fighting Perebor: New and Improved Algorithms for Formula and QBF Satisfiability
    Author: Rahul Santhanam, University of Edinburgh
70. Lower Bounds for Near Neighbor Search via Metric Expansion [arXiv]
    Authors: Rina Panigrahy (Microsoft Research Silicon Valley), Kunal Talwar (Microsoft Research Silicon Valley), Udi Wieder (Microsoft Research Silicon Valley)
71. Black-Box Randomized Reductions in Algorithmic Mechanism Design [pdf]
    Authors: Shaddin Dughmi and Tim Roughgarden (Stanford University)
72. Pure and Bayes-Nash Price of Anarchy for Generalized Second Price Auction [pdf]
    Authors: Renato Paes Leme and Eva Tardos (Cornell)
73. Learning Convex Concepts from Gaussian Distributions with PCA [pdf]
    Authors: Santosh Vempala (Georgia Tech)
74. Sublinear Optimization for Machine Learning [pdf]
    Authors: Kenneth L. Clarkson and Elad Hazan and David P. Woodruff (IBM Almaden Research Center)
75. The Limits of Two-Party Differential Privacy [html]
    Authors: Andrew McGregor (University of Massachusetts, Amherst) Ilya Mironov (Microsoft Research Silicon Valley) Toniann Pitassi (University of Toronto) Omer Reingold (Microsoft Research Silicon Valley) Kunal Talwar (Microsoft Research Silicon Valley) Salil Vadhan (Harvard)
76. Distance Oracles Beyond the Thorup-Zwick Bound
    Authors: Mihai Patrascu – AT&T Labs; Liam Roditty – Bar Ilan University
77. A Multiplicative Weights Mechanism for Interactive Privacy-Preserving Data Analysis
    Authors: Moritz Hardt (Princeton University); Guy Rothblum (Princeton University)
78. Subexponential Algorithms for Unique Games and Related problems [pdf]
    Authors: Sanjeev Arora: Princeton University and Center for Computational Intractability; Boaz Barak: Microsoft Research and Princeton University; David Steurer: Princeton University and Center for Computational Intractability.
79. Budget Feasible Mechanisms [arXiv]
    Author: Yaron Singer, UC Berkeley
80. Black-Box, Round-Efficient Secure Computation via Non-Malleability Amplification
    Hoeteck Wee (Queens College, CUNY)
81. On the Computational Complexity of Coin Flipping [pdf]
    Authors: Hemanta K. Maji (UIUC) Manoj Prabhakaran (UIUC) Amit Sahai (UCLA)
82. Adaptive Hardness and Composable Security in the Plain Model from Standard Assumptions
    Authors: Ran Canetti, Huijia Lin, and Rafael Pass.