FOCS 2010 accepted paper list is here and list with abstracts is here. Following are PDF pointers to online versions.
- Settling the Polynomial Learnability of Mixtures of Gaussians [arXiv]
Authors: Ankur Moitra (MIT) and Gregory Valiant (UC Berkeley) - Solving linear systems through nested dissection [pdf]
Authors: Noga Alon (Tel Aviv University) Raphael Yuster (University of Haifa) - Improved Bounds for Geometric Permutations [arXiv]
Authors: Natan Rubin, Haim Kaplan and Micha Sharir (Tel Aviv University) - Constructive Algorithms for Discrepancy Minimization [arXiv]
Authors: Nikhil Bansal (IBM Research) - 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 - Replacement Paths via Fast Matrix Multiplication [pdf]
Authors: Oren Weimann (Weizmann Institute of Science) Raphael Yuster (University of Haifa) - 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. - 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) - Determinant Sums for Undirected Hamiltonicity [arXiv]
Author: Andreas Bjorklund, Lund University, Department of Computer Science, P.O.Box 118, SE-22100 Lund, Sweden - A non-linear lower bound for planar epsilon-nets [pdf]
Author: Noga Alon, Tel Aviv University and IAS, Princeton - 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 - A lower bound for dynamic approximate membership data structures [ECCC]
Authors: Shachar Lovett and Ely Porat - 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 - The Geometry of Manipulation – a Quantitative Proof of the Gibbard Satterthwaite Theorem [arXiv]
Authors: Marcus Isaksson and Guy Kindler and Elchanan Mossel - 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) - 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) - Local list decoding with a constant number of queries [ECCC]
Authors: Avraham Ben-Aroya and Klim Efremenko and Amnon Ta-Shma - New Constructive Aspects of the Lovasz Local Lemma [arXiv]
Authors: Bernhard Haeupler (MIT) Barna Saha (University of Maryland) and Aravind Srinivasan (University of Maryland) - Matching vector codes [html]
Authors: Zeev Dvir, Princeton University Parikshit Gopalan, Microsoft Research Sergey Yekhanin, Microsoft Research - 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 - The complexity of distributions [pdf]
Author: Emanuele Viola, Northeastern University - 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 - Computational Transition at the Uniqueness Threshold [arXiv]
Author: Allan Sly, Microsoft Research, Redmond - 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 - Subcubic Equivalences Between Path, Matrix, and Triangle Problems [pdf]
Authors: Virginia Vassilevska Williams, UC Berkeley and Ryan Williams, IBM Almaden Research Center - 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 - A Unified Framework for Testing Linear-Invariant Properties
Authors: Arnab Bhattacharyya (MIT), Elena Grigorescu (MIT), Asaf Shapira (Georgia Tech) - 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 - Optimal stochastic planarization [arXiv]
Anastasios Sidiropoulos , Toyota Technological Institute at Chicago - Bounds on Monotone Switching Networks for Directed Connectivity [arXiv]
Author: Aaron Potechin, MIT - A Fourier-analytic approach to Reed-Muller decoding [html]
Parikshit Gopalan, Microsoft Research Silicon Valley. - 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 - 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. - 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) - 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) - Clustering with Spectral Norm and the k-means Algorithm [arXiv]
Amit Kumar (IIT Delhi) and Ravindran Kannan (Microsoft Research India Lab, Bangalore) - Testing Properties of Sparse Images [pdf]
Authors: Dana Ron and Gilad Tsur, Department of Electrical Engineering – Systems, Tel-Aviv University. - Frugal Mechanism Design via Spectral Techniques [arXiv]
Authors: Ning Chen and Edith Elkind and Nick Gravin and Fedor Petrov - 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) - 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) - 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 - 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. - One Tree Suffices: A Simultaneous O(1)-Approximation for Single-Sink Buy-at-Bulk [arXiv]
Authors: Ashish Goel (Stanford University) Ian Post (Stanford University) - 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 - Cryptography Against Continuous Memory Attacks [ePrint]
AUthors: Yevgeniy Dodis and Kristiyan Haralambiev and Adriana Lopez-Alt and Daniel Wich - Hardness of Finding Independent Sets in Almost 3-Colorable Graphs
Authors: Irit Dinur and Subhash Khot and Will Perkins and Muli Safra - 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 - Codes for Computationally Simple Channels: Explicit Constructions with Optimal Rate [arXiv]
Authors: Venkatesan Guruswami (Carnegie Mellon University) Adam Smith (Pennsylvania State University) - Polynomial Learning of Distribution Families [arXiv]
Mikhail Belkin (Ohio State University) and Kaushik Sinha (Ohio State University) - 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 - 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 - 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; - 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 - The Geometry of Scheduling [arXiv]
Authors: Nikhil Bansal (IBM Research) and Kirk Pruhs (Univ. of Pittsburgh) - Stability yields a PTAS for k-Median and k-Means Clustering [pdf]
Authors: Pranjal Awasthi and Avrim Blum and Or Sheffet, Carnegie Mellon University - Metric Extension Operators, Vertex Sparsifiers and Lipschitz Extendability
Authors:Konstantin Makarychev (IBM Research) and Yury Makarychev (TTIC). - 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) - Fast approximation algorithms for flow and cut-based problems in undirected graphs [pdf]
Author: Aleksander Madry, MIT - Efficient volume sampling for row/column subset selection [pdf]
Amit Deshpande, Microsoft Research India and Luis Rademacher, Computer Science and Engineering, Ohio State University - Position-Based Quantum Cryptography [arXiv]
Authors: Nishanth Chandran (UCLA), Serge Fehr (CWI), Ran Gelles (UCLA), Vipul Goyal (Microsoft Research, India), Rafail Ostrovsky (UCLA) - Estimating the longest increasing sequence in polylogarithmic time [pdf]
Authors: Michael Saks, Rutgers University and C. Seshadhri, IBM Almaden - The Monotone Complexity of k-Clique on Random Graphs [pdf]
Author: Benjamin Rossman, MIT - Frugal and Truthful Auctions for Vertex Covers, Flows, and Cuts [arXiv]
Authors: David Kempe and Mahyar Salek and Cristopher Moore - The Coin Problem, and Pseudorandomness for Branching Programs
Authors: Joshua Brody and Elad Verbin - Agnostically learning under permutation invariant distributions
Author: Karl Wimmer (Duquesne University) - Approximating Maximum Weight Matching in Near-linear Time [pdf]
Ran Duan, University of Michigan and Seth Pettie, University of Michigan - Bounded Independence Fools Degree-2 Threshold Functions [ECCC]
Authors: Ilias Diakonikolas (Columbia), Daniel M. Kane (Harvard), Jelani Nelson (MIT) - Boosting and Differential Privacy
Authors: Cynthia Dwork (Microsoft Research), Guy Rothblum (Princeton University), Salil Vadhan (Harvard University - Fighting Perebor: New and Improved Algorithms for Formula and QBF Satisfiability
Author: Rahul Santhanam, University of Edinburgh - 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) - Black-Box Randomized Reductions in Algorithmic Mechanism Design [pdf]
Authors: Shaddin Dughmi and Tim Roughgarden (Stanford University) - Pure and Bayes-Nash Price of Anarchy for Generalized Second Price Auction [pdf]
Authors: Renato Paes Leme and Eva Tardos (Cornell) - Learning Convex Concepts from Gaussian Distributions with PCA [pdf]
Authors: Santosh Vempala (Georgia Tech) - Sublinear Optimization for Machine Learning [pdf]
Authors: Kenneth L. Clarkson and Elad Hazan and David P. Woodruff (IBM Almaden Research Center) - 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) - Distance Oracles Beyond the Thorup-Zwick Bound
Authors: Mihai Patrascu – AT&T Labs; Liam Roditty – Bar Ilan University - A Multiplicative Weights Mechanism for Interactive Privacy-Preserving Data Analysis
Authors: Moritz Hardt (Princeton University); Guy Rothblum (Princeton University) - 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. - Budget Feasible Mechanisms [arXiv]
Author: Yaron Singer, UC Berkeley - Black-Box, Round-Efficient Secure Computation via Non-Malleability Amplification
Hoeteck Wee (Queens College, CUNY) - On the Computational Complexity of Coin Flipping [pdf]
Authors: Hemanta K. Maji (UIUC) Manoj Prabhakaran (UIUC) Amit Sahai (UCLA) - Adaptive Hardness and Composable Security in the Plain Model from Standard Assumptions
Authors: Ran Canetti, Huijia Lin, and Rafael Pass.
My Brain is Open 