FOCS 2013 Accepted Papers (with pdf files)

FOCS 2013 accepted paper list is here. Following are PDF pointers to online versions.

  • OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings, by Jelani Nelson and Huy L. Nguyen [arXiv]
  • A Polynomial Time Algorithm for Lossy Population Recovery, by Ankur Moitra and Michael Saks [arXiv]
  • Direct products in communication complexity, by Mark Braverman, Anup Rao, Omri Weinstein and Amir Yehudayoff [ECCC]
  • Arithmetic circuits: A chasm at depth three, by Ankit Gupta, Pritish Kamath, Neeraj Kayal and Ramprasad Saptharishi [ECCC]
  • Approximating Minimum-Cost k-Node Connected Subgraphs via Independence-Free Graphs, by Joseph Cheriyan and Laszlo A. Vegh [arXiv]
  • The Parity of Directed Hamiltonian Cycles, by Andreas Björklund and Thore Husfeldt [arXiv]
  • Approximating Minimization Diagrams and Generalized Proximity Search, by Sariel Har-Peled and Nirman Kumar [arXiv]
  • Quantum 3-SAT is QMA1-complete, by David Gosset and Daniel Nagaj [arXiv]
  • The Price of Stability for Undirected Broadcast Network Design with Fair Cost Allocation is Constant, by Vittorio Bilò, Michele Flammini and Luca Moscardelli
  • Strong LTCs with inverse poly-log rate and constant soundness, by Michael Viderman [ECCC]
  • All-or-nothing multicommodity flow problem with bounded fractionality in planar graphs, by Ken-ichi Kawarabayashi and Yusuke Kobayashi
  • Approximating Bin Packing within O(log OPT * log log OPT) bins, by Thomas Rothvoss [arXiv]
  • Common information and unique disjointness, by Gábor Braun, and Sebastian Pokutta [ECCC]
  • Chasing the k-colorability threshold, by Amin Coja-Oghlan and Dan Vilenchik [arXiv]
  • Three-player entangled XOR games are NP-hard to approximate, by Thomas Vidick [arXiv]
  • Fully Dynamic $(1+\epsilon)$-Approximate Matchings, by Manoj Gupta, and Richard Peng [arXiv]
  • Estimating the distance from testable affine-invariant properties, by Hamed Hatami and Shachar Lovett [arXiv]
  • Approximation algorithms for Euler genus and related problems, by Chandra Chekuri and Anastasios Sidiropoulos [arXiv]
  • Polar Codes: Speed of polarization and polynomial gap to capacity, by Venkatesan Guruswami and Patrick Xia [arXiv]
  • An Optimal Randomized Online Algorithm for Reordering Buffer Management, by Noa Avigdor-Elgrabli and Yuval Rabani [arXiv]
  • Approximation Schemes for Maximum Weight Independent Set of Rectangles, by Anna Adamaszek and Andreas Wiese
  • Playing Non-linear Games with Linear Oracles, by Dan Garber, and Elad Hazan
  • Faster Canonical Forms for Strongly Regular Graphs, by Laszlo Babai, Xi Chen, Xiaorui Sun, Shang-Hua Teng and John Wilmes
  • Constant rate PCPs for circuit-SAT with sublinear query complexity, by Eli Ben-Sasson, Yohay Kaplan, Swastik Kopparty, Or Meir and Henning Stichtenoth [pdf] [video]
  • How to Approximate A Set Without Knowing Its Size In Advance, by Rasmus Pagh, Gil Segev and Udi Wieder [arXiv]
  • Quasipolynomial-time Identity Testing of Non-Commutative and Read-Once Oblivious Algebraic Branching Programs, by Michael A. Forbes, and Amir Shpilka [arXiv]
  • On Kinetic Delaunay Triangulations: A Near Quadratic Bound for Unit Speed Motions, by Natan Rubin
  • Element Distinctness, Frequency Moments, and Sliding Windows, by Paul Beame, Raphael Clifford and Widad Machmouchi
  • Spatial mixing and approximation algorithms for graphs with bounded connective constant, by Alistair Sinclair, Piyush Srivastava and Yitong Yin
  • Algebraic Algorithms for b-Matching, Shortest Undirected Paths, and f-Factors, by Harold N. Gabow and Piotr Sankowski [arXiv]
  • A linear time approximation scheme for Euclidean TSP, by Yair Bartal and Lee-Ad Gottlieb
  • Interactive Coding, Revisited, by Kai-Min Chung, Rafael Pass and Sidharth Telang [ePrint]
  • Improved approximation for 3-dimensional matching via bounded pathwidth local search, by Marek Cygan [arXiv]
  • Strong Backdoors to Bounded Treewidth SAT, by Serge Gaspers and Stefan Szeider [arXiv]
  • Explicit Subspace Designs, by Venkatesan Guruswami and Swastik Kopparty [ECCC]
  • Dynamic Approximate All-Pairs Shortest Paths: Breaking the $ \tilde O(mn) $ Barrier and Derandomization, Monika Henzinger, Sebastian Krinninger and Danupon Nanongkai
  • On Randomized Memoryless Algorithms for the Weighted $k$-server Problem, by Ashish Chiplunkar and Sundar Vishwanathan [arXiv]
  • Constant-Round Concurrent Zero Knowledge From P-Certificates, by Kai-Min Chung, Huijia Lin and Rafael Pass [ePrint]
  • Learning Sums of Independent Integer Random Variables, by Constantinos Daskalakis, Ilias Diakonikolas, Ryan O’Donnell, Rocco A. Servedio and Li-Yang Tan [pdf]
  • Independent Set, Induced Matching, and Pricing: Connections and Tight (Subexponential Time) Approximation Hardnesses, by Parinya Chalermsook, Bundit Laekhanukit, and Danupon Nanongkai
  • Online Node-weighted Steiner Forest and Extensions via Disk Paintings, by Mohammad Taghi Hajiaghayi, Vahid Liaghat, and Debmalya Panigrahi
  • Klee’s Measure Problem Made Easy, by Timothy M. Chan
  • Extractors for a Constant Number of Independent Sources with Polylogarithmic Min-Entropy, by Xin Li [arXiv]
  • Navigating Central Path with Electrical Flows: from Flows to Matchings, and Back, by Aleksander Madry
  • Fourier sparsity, spectral norm, and the Log-rank conjecture, Hing Yin Tsang, Chung Hoi Wong, Ning Xie and Shengyu Zhang [arXiv]
  • Layered Separators for Queue Layouts, 3D Graph Drawing and Nonrepetitive Coloring, by Vida Dujmović, Pat Morin, and David R. Wood
  • Average Case Lower Bounds for Monotone Switching Networks, by Yuval Filmus, Toniann Pitassi, Robert Robere and Stephen A. Cook [arXiv]
  • PCPs via low-degree long code and hardness for constrained hypergraph coloring, by Irit Dinur and Venkatesan Guruswami
  • The planar directed k-Vertex-Disjoint Paths problem is fixed-parameter tractable, by Marek Cygan, Dániel Marx, Marcin Pilipczuk and Michał Pilipczuk [arXiv]
  • On the communication complexity of sparse set disjointness and exists-equal problems, Mert Sağlam and Gábor Tardos [arXiv]
  • The Simple Economics of Approximately Optimal Auctions, Saeed Alaei, Hu Fu, Nima Haghpanah and Jason Hartline [arXiv]
  • Efficient Accelerated Coordinate Descent Methods and Faster Algorithms for Solving Linear Systems, by Yin Tat Lee and Aaron Sidford [arXiv]
  • Nearly Maximum Flows in Nearly Linear Time, by Jonah Sherman [arXiv]
  • Improved Average-Case Lower Bounds for DeMorgan Formula Size, by Ilan Komargodski, Ran Raz and Avishay Tal [ECCC]
  • Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas, by Vitaly Feldman and Jan Vondrak
  • Towards a better approximation for Sparsest Cut?, by Sanjeev Arora, Rong Ge and Ali Kemal Sinop [arXiv]
  • Bandits with Knapsacks, Ashwinkumar Badanidiyuru, Robert Kleinberg and Aleksandrs Slivkins [arXiv]
  • Approximate Constraint Satisfaction Requires Large LP Relaxations, by Siu On Chan, James R. Lee, Prasad Raghavendra and David Steurer
  • Simple Tabulation, Fast Expanders, Double Tabulation, and High Independence, by Mikkel Thorup
  • An LMP O(log n)-Approximation Algorithm for Node Weighted Prize Collecting Steiner Tree, by Jochen Koenemann, Sina Sadeghian and Laura Sanità [arXiv]
  • A Satisfiability Algorithm for Sparse Depth Two Threshold Circuits, by Russell Impagliazzo, Ramamohan Paturi, and Stefan Schneider [arXiv]
  • The Complexity of Approximating Vertex Expansion, by Anand Louis, Prasad Raghavendra and Santosh Vempala [arXiv]
  • Tight Bounds for Set Disjointness in the Message Passing Model, by Mark Braverman, Faith Ellen, Rotem Oshman, Toni Pitassi and Vinod Vaikuntanathan [arXiv]
  • Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees, Adam Marcus, Daniel A. Spielman and Nikhil Srivastava [arXiv]
  • Candidate Indistinguishability Obfuscation and Functional Encryption for all circuits, by Sanjam Garg, Craig Gentry, Shai Halevi, Mariana Raykova, Amit Sahai, and Brent Waters
  • Iterative Row Sampling, by Mu Li, Gary L. Miller, and Richard Peng [arXiv]
  • Simultaneous Resettability from One-Way Functions, Kai-Min Chung, Rafail Ostrovsky, Rafael Pass and Ivan Visconti
  • Rational Protocol Design: Cryptography Against Incentive-driven Adversaries, by Juan Garay , Jonathan Katz, Ueli Maurer, Bjoern Tackmann and Vassilis Zikas
  • Non-positive curvature, and the planar embedding conjecture, by Anastasios Sidiropoulos [arXiv]
  • Local Privacy and Statistical Minimax Rates, by John C. Duchi, Michael I. Jordan, and Martin J. Wainwright [arXiv]
  • The Moser-Tardos Framework with Partial Resampling, by David G. Harris and Aravind Srinivasan
  • On Clustering Induced Voronoi Diagrams, Danny Z. Chen, Ziyun Huang, Yangwei Liu, and Jinhui Xu
  • A forward-backward single-source shortest paths algorithm, by David Wilson and Uri Zwick
  • An O(c^k) n 5-Approximation Algorithm for Treewidth, by Hans L. Bodlaender, Paal G. Drange, Markus S. Dregi, Fedor V. Fomin, Daniel Lokshtanov and Michal Pulipczuk [arXiv]
  • Understanding Incentives: Mechanism Design becomes Algorithm Design, by Yang Cai, Constantinos Daskalakis, and S. Matthew Weinberg [arXiv]
  • Nondeterministic Direct Product Reductions and the Success Probability of SAT Solvers, by Andrew Drucker
  • From Unprovability to Environementally Friendly Protocols, by Ran Canetti, Huijia Lin and Rafael Pass
  • Adaptive Seeding in Social Networks, by Lior Seeman and Yaron Singer
  • Coupled-Worlds Privacy: Exploiting Adversarial Uncertainty in Statistical Data Privacy, by Raef Bassily, Adam Groce, Jonathan Katz and Adam Smith


STOC 2013 Accepted Papers (with pdf files)

STOC 2013 accepted paper list is here. Following are PDF pointers to online versions.


Max flows in O(nm) time or less [pdf]
James Orlin (MIT)

Multidimensional Approximate Agreement in Byzantine Asynchronous Systems
Hammurabi Mendes (Brown University) and Maurice Herlihy (Brown University)

Non-Black-Box Simulation in the Fully Concurrent Setting
Vipul Goyal (Microsoft Research, India)

Approximation Resistance from Pairwise Independent Subgroups [ECCC]
Siu On Chan (UC Berkeley)

Average-Case Lower Bounds for Formula Size [ECCC]
Ilan Komargodski (Weizmann Institute of Science) and Ran Raz (Weizmann Institute of Science)

New Independent Source Extractors with Exponential Improvement [ECCC]
Xin Li (University of Washington)

Random Lattice Triangulations: Structure and Algorithms [arXiv]
Pietro Caputo (University of Rome III), Fabio Martinelli (University of Rome III), Alistair Sinclair (UC Berkeley), and Alexandre Stauffer (University of Rome III)

The Complexity of Non-Monotone Markets [arXiv]
Xi Chen (Columbia University), Dimitris Paparas (Columbia University), and Mihalis Yannakakis (Columbia University)

Optimal Euclidean spanners: really short, thin and lanky [arXiv]
Michael Elkin (Ben-Gurion University) and Shay Solomon (Weizmann Institute of Science)

Low-distortion Subspace Embeddings in Input-sparsity Time and Applications to Robust Linear Regression [arXiv]
Xiangrui Meng (Stanford University) and Michael W. Mahoney (Stanford University)

Recursive Composition and Bootstrapping for SNARKs and Proof-Carrying Data [ePrint]
Nir Bitansky (Tel Aviv University), Ran Canetti (Boston University and Tel Aviv University), Alessandro Chiesa (MIT), and Eran Tromer (Tel Aviv University)

Sparsity lower bounds for dimensionality reducing maps [arXiv]
Jelani Nelson (Institute for Advanced Study) and Huy L. Nguyen (Princeton University)

Approximating k-Median via Pseudo-Approximation [arXiv]
Shi Li (Princeton University) and Ola Svensson (EPFL)

Byzantine Agreement in Polynomial Expected Time
Valerie King (University of Victoria) and Jared Saia (University of New Mexico)

Equivalence of Deterministic One-Counter Automata is NL-complete [arXiv]
Stanislav Bohm (Technical University of Ostrava), Stefan Goller (University of Bremen), and Petr Jancar (Technical University of Ostrava)

Answering n^{2+o(1)} Counting Queries with Differential Privacy is Hard [arXiv]
Jonathan Ullman (Harvard University)

Succinct Functional Encryption and Applications: Reusable Garbled Circuits and Beyond [ePrint]
Shafi Goldwasser (MIT), Yael Kalai (Microsoft Research, New England), Raluca Ada Popa (MIT), Vinod Vaikuntanathan (University of Toronto), and Nickolai Zeldovich (MIT)

Lower bounds for RAMs and quantifier elimination
Miklos Ajtai (IBM Almaden Research Center)

New Bounds on Matching Vector Families [arXiv]
Abhishek Bhowmick (University of Texas at Austin), Zeev Dvir (Princeton University), and Shachar Lovett (UC San Diego)

The complexity of finite-valued CSPs [arXiv]
Johan Thapper (Universite Paris-Sud 11) and Stanislav Zivny (University of Warwick)

Structured Recursive Separator Decompositions for Planar Graphs in Linear Time [arXiv]
Philip N. Klein (Brown University), Shay Mozes (MIT), and Christian Sommer (MIT)

Inverting well-conditioned matrices in Quantum Logspace
Amnon Ta-Shma (Tel-Aviv University)

List decoding Reed-Solomon, Algebraic-Geometric, and Gabidulin subcodes up to the Singleton bound [ECCC]
Venkatesan Guruswami (Carnegie Mellon University) and Chaoping Xing (Nanyang Technological University)

Quasipolynomial-time Canonical Form for Steiner Designs
Laszlo Babai (University of Chicago) and John Wilmes (University of Chicago)

Constraint Satisfaction, Packet Routing, and the Lovasz Local Lemma [pdf]
David G. Harris (University of Maryland) and Aravind Srinivasan (University of Maryland)

Low Rank Approximation and Regression in Input Sparsity Time [arXiv]
Kenneth L. Clarkson (IBM Almaden Research) and David P. Woodruff (IBM Almaden Research)

Maintaining Shortest Paths Under Deletions in Weighted Directed Graphs
Aaron Bernstein (Columbia University)

A o(n) monotonicity tester for boolean functions over the hypercube
Deeparnab Chakrabarty (Microsoft Research, India) and C. Seshadhri (Sandia National Laboratories, Livermore)

On the list decodability of random linear codes with large error rates
Mary Wootters (University of Michigan)

Simple Deterministic Algorithms for Fully Dynamic Maximal Matching [arXiv]
Ofer Neiman (Ben-Gurion University) and Shay Solomon (Weizmann Institute of Science)

Net and Prune: A Linear Time Algorithm for Euclidean Distance Problems [HTML]
Sariel Har-Peled (University of Illinois at Urbana Champaign) and Benjamin Raichel (University of Illinois at Urbana Champaign)

Every locally characterized affine-invariant property is testable [arXiv]
Arnab Bhattacharyya (DIMACS), Eldar Fischer (Technion), Hamed Hatami (McGill), Pooya Hatami (University of Chicago), and Shachar Lovett (UC San Diego)

Superlinear advantage for exact quantum algorithms [arXiv]
Andris Ambainis (University of Latvia)

Efficient rounding for the noncommutative Grothendieck inequality [arXiv]
Assaf Naor (New York University), Oded Regev (New York University), and Thomas Vidick (MIT)

A node-capacitated Okamura-Seymour theorem [arXiv]
James R. Lee (University of Washington), Manor Mendel (Open University), and Mohammad Moharrami (University of Washington)

Lee-Yang Theorems and the Complexity of Computing Averages [arXiv]
Alistair Sinclair (UC Berkeley) and Piyush Srivastava (UC Berkeley)

Beyond Worst-Case Analysis in Private Singular Vector Computation [arXiv]
Moritz Hardt (IBM Almaden Research) and Aaron Roth (University of Pennsylvania)

Classical Hardness of Learning with Errors
Zvika Brakerski (Stanford University), Adeline Langlois (ENS de Lyon), Chris Peikert (Georgia Tech), Oded Regev (New York University), and Damien Stehle (ENS de Lyon)

Coevolutionary Opinion Formation Games
Kshipra Bhawalkar (Stanford University), Sreenivas Gollapudi (Microsoft Research, Silicon Valley), and Kamesh Munagala (Duke University)

Predicate Encryption for Circuits
Sergey Gorbunov (University of Toronto), Vinod Vaikuntanathan (University of Toronto), and Hoeteck Wee (George Washington University)

On the complexity of Trial and Error [arXiv]
Xiaohui Bei (Nanyang Technological University), Ning Chen (Nanyang Technological University), and Shengyu Zhang (The Chinese University of Hong Kong)

Fast Routing Table Construction Using Small Messages [arXiv]
Christoph Lenzen (Weizmann Institute of Science) and Boaz Patt-Shamir (Tel Aviv University)

Quasi-polynomial Hitting-set for Set-depth-$\Delta$ Formulas [arXiv]
Manindra Agrawal (Indian Institute of Technology, Kanpur), Chandan Saha (Indian Institute of Science), and Nitin Saxena (Hausdorff Center for Mathematics)

Explicit Lower Bounds via Geometric Complexity Theory [arXiv]
Peter Burgisser (University of Paderborn) and Christian Ikenmeyer (University of Paderborn)

Shielding circuits with groups [ePrint]
Eric Miles (Northeastern University) and Emanuele Viola (Northeastern University)

Extending continuous maps: polynomiality and undecidability [pdf]
Martin Cadek (Masaryk University Brno), Marek Krcal (Charles University Prague), Jiri Matousek (Charles University Prague and ETH Zurich), Lukas Vokrinek (Masaryk University Brno), and Uli Wagner (EPFL)

Testing Subdivision-Freeness: Property Testing Meets Structural Graph Theory
Ken-ichi Kawarabayashi (National Institute of Informatics and JST ERATO Kawarabayashi Project) and Yuichi Yoshida (National Institute of Informatics and Preferred Infrastructure, Inc.)

Some Trade-off Results for Polynomial Calculus
Chris Beck (Princeton University), Jakob Nordstrom (KTH Royal Institute of Technology), and Bangsheng Tang (Tsinghua University)

Going After the k-SAT Threshold [arXiv]
Amin Coja-Oghlan (Goethe University) and Konstantinos Panagiotou (University of Munich)

Composable and Efficient Mechanisms [arXiv]
Vasilis Syrgkanis (Cornell University) and Eva Tardos (Cornell University)

Tatonnement Beyond Gross Substitutes? Gradient Descent to the Rescue
Yun Kuen Cheung (New York University), Richard Cole (New York University), and Nikhil Devanur (Microsoft Research, Redmond)

Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight planar graphs
David Eisenstat (Brown University) and Philip N. Klein (Brown University)

The Power of Deferral: Maintaining a Constant-Competitive Steiner Tree Online
Albert Gu (Carnegie Mellon University), Anupam Gupta (Carnegie Mellon University), and Amit Kumar (Indian Institute of Technology, Delhi)

On the Non-Uniform Sparsest Cut Problem on Bounded Treewidth Graphs
Anupam Gupta (Carnegie Mellon University), Kunal Talwar (Microsoft Research, Silicon Valley), and David Witmer (Carnegie Mellon University)

Optimal bounds for monotonicity and Lipschitz testing over hypercubes and hypergrids [arXiv]
Deeparnab Chakrabarty (Microsoft Research, India), C. Seshadhri (Sandia National Labs, Livermore), and Deeparnab Chakrabarty (Microsoft Research, India)

On the Concrete Efficiency of Probabilistically Checkable Proofs [ECCC]
Eli Ben-Sasson (Technion and MIT), Alessandro Chiesa (MIT), Daniel Genkin (Technion), and Eran Tromer (Tel Aviv University)

Polynomial-time perfect matchings in dense hypergraphs
Peter Keevash (Queen Mary, University of London), Fiachra Knox (Queen Mary, University of London), and Richard Mycroft (University of Birmingham)

Large-Treewidth Graph Decompositions and Applications
Chandra Chekuri (University of Illinois at Urbana-Champaign) and Julia Chuzhoy (Toyota Technological Institute, Chicago)

Differential Privacy for the Analyst via Private Equilibrium Computation [arXiv]
Justin Hsu (University of Pennsylvania), Aaron Roth (University of Pennsylvania), and Jonathan Ullman (Harvard University)

Succinct Sampling from Discrete Distributions [pdf]
Karl Bringmann (Max Planck Institute for Informatics) and Kasper Green Larsen (MADALGO, Aarhus University)

The Orbit Problem in Higher Dimensions [pdf]
Ventsislav Chonev (Oxford University), Joel Ouaknine (Oxford University), and James Worrell (Oxford University)

Homomorphic Fingerprints under Misalignments
Alexandr Andoni (Microsoft Research, Silicon Valley), Assaf Goldberger (Tel Aviv University), Andrew McGregor (University of Massachusetts), and Ely Porat (Bar-Ilan University)

Approximation Resistance on Satisfiable Instances for Predicates with Few Accepting Inputs
Sangxia Huang (KTH Royal Institute of Technology)

An Information Complexity Approach to Extended Formulations [ECCC]
Mark Braverman (Princeton University) and Ankur Moitra (Institute for Advanced Study)

Simplex Partitioning via Exponential Clocks and the Multiway-Cut Problem
Niv Buchbinder (Tel Aviv University), Joseph (Seffi) Naor (Technion), and Roy Schwartz (Microsoft Research, Redmond)

A PRG for Lipschitz Functions of Polynomials with Applications to Sparsest Cut [arXiv]
Daniel Kane (Stanford University) and Raghu Meka (Institute for Advanced Study and DIMACS)

Analysis of Spectral Partitioning through Higher Order Spectral Gap [arXiv]
Tsz Chiu Kwok (The Chinese University of Hong Kong), Lap Chi Lau (The Chinese University of Hong Kong), Yin Tat Lee (The Chinese University of Hong Kong), Shayan Oveis Gharan (Stanford University), and Luca Trevisan (Stanford University)

Quantum de Finetti Theorems under Local Measurements with Applications [arXiv]
Fernando G.S.L. Brandao (ETH Zurich) and Aram W. Harrow (University of Washington)

Stochastic Combinatorial Optimization via Poisson Approximation [arXiv]
Jian Li (IIIS, Tsinghua University) and Wen Yuan (IIIS, Tsinghua University)

Natural Proofs, Derandomization, and Lower Bounds [arXiv]
Ryan Williams (Stanford University)

Majority is Stablest : Discrete and SoS [arXiv]
Anindya De (UC Berkeley), Elchanan Mossel (UC Berkeley), and Joe Neeman (UC Berkeley)

Combinatorial Walrasian Equilibrium
Michal Feldman (The Hebrew University of Jerusalem and Harvard University), Nikolai Gravin (Nanyang Technological University), and Brendan Lucier (Microsoft Research, New England)

Simultaneous Auctions are (almost) Efficient [arXiv]
Michal Feldman (The Hebrew University of Jerusalem and Harvard University), Hu Fu (Cornell University), Nikolai Gravin (Nanyang Technological University), and Brendan Lucier (Microsoft Research, New England)

The Geometry of Differential Privacy: The Sparse and Approximate Cases [arXiv]
Aleksandar Nikolov (Rutgers University), Kunal Talwar (Microsoft Research, Silicon Valley), and Li Zhang (Microsoft Research, Silicon Valley)

Fully device-independent quantum key distribution [arXiv]
Umesh Vazirani (UC Berkeley) and Thomas Vidick (MIT)

Delegation for Bounded Space
Yael Tauman Kalai (Microsoft Research, New England), Ran Raz (Weizmann Institute of Science), and Ron D. Rothblum (Weizmann Institute of Science)

A new family of locally correctable codes based on degree-lifted algebraic geometry codes [ECCC]
Eli Ben Sasson (Technion and MIT), Ariel Gabizon (Technion), Yohay Kaplan (Technion), Swatik Kopparty (Rutgers University), and Shubangi Saraf (Rutgers University)

Interactive Proofs of Proximity: Delegating Computation in Sublinear Time
Guy Rothblum (Microsoft Research, Silicon Valley), Salil Vadhan (Harvard University), and Avi Wigderson (Institute for Advanced Studies)

How Robust are Linear Sketches to Adaptive Inputs? [arXiv]
Moritz Hardt (IBM Almaden Research) and David P. Woodruff (IBM Almaden Research)

The Approximate Rank of a Matrix and its Algorithmic Applications [ECCC]
Noga Alon (Tel Aviv University) and Santosh Vempala (Georgia Tech)

Communication Lower Bounds Using Directional Derivatives [ECCC]
Alexander A. Sherstov (UC Los Angelos)

Fast approximation algorithms for the diameter and radius of sparse graphs [pdf]
Liam Roditty (Bar Ilan University) and Virginia Vassilevska Williams (UC Berkeley and Stanford University)

Approximation Guarantees for the Quantum Local Hamiltonian Problem and Limitations for Quantum PCPs
Fernando G.S.L. Brandao (ETH Zurich) and Aram W. Harrow (University of Washington)

On the Impossibility of Approximate Obfuscation and Applications to Resettable Cryptography [ePrint]
Omer Paneth (Boston University) and Nir Bitansky (Tel Aviv University)

Yossi Azar (Tel Aviv University), Ilan Cohen (Tel Aviv University), and Iftah Gamzu (Tel Aviv University)

Tight Bounds for Online Vector Bin Packing
Yossi Azar (Tel Aviv University), Ilan Cohen (Tel Aviv University), Seny Kamara (Microsoft Research, Redmond), and Bruce Shepherd (McGill University)

A Complete Dichotomy Rises from the Capture of Vanishing Signatures [arXiv]
Jin-Yi Cai (University of Wisconsin at Madison), Heng Guo (University of Wisconsin at Madison), and Tyson Williams (University of Wisconsin at Madison)

A Simple, Combinatorial Algorithm for Solving SDD Systems in Nearly-Linear Time [arXiv]
Jonathan A. Kelner (MIT), Lorenzo Orecchia (MIT), Aaron Sidford (MIT), and Zeyuan Allen Zhu (MIT)

Low-rank Matrix Completion using Alternating Minimization [arXiv]
Prateek Jain (Microsoft Research, India), Praneeth Netrapalli (The University of Texas at Austin), and Sujay Sanghavi (The University of Texas at Austin)

Multi-Stage Propagation and Quasipolynomial-Time Isomorphism Testing of Steiner 2-Systems
Xi Chen (Columbia University), Xiaorui Sun (Columbia University), and Shang-Hua Teng (University of Southern California)

Strong ETH Holds For Regular Resolution
Chris Beck (Princeton University) and Russell Impagliazzo (UC San Diego)

Statistical Algorithms and a Lower Bound for Detecting Planted Cliques [arXiv]
Vitaly Feldman (IBM Research Almaden), Elena Grigorescu (Purdue University), Lev Reyzin (University of Illinois at Chicago), Santosh Vempala (Georgia Tech), and Ying Xiao (Georgia Tech)

Bottom-k and Priority Sampling, Set Similarity and Subset Sums with Minimal Independence
Mikkel Thorup (AT&T Labs-Research and University of Copenhagen)

Prior-Independent Mechanisms for Scheduling
Shuchi Chawla (University of Wisconsin at Madison), Jason D. Hartline (Northwestern University), David Malec (University of Wisconsin at Madison), and Balasubramanian Sivan (University of Wisconsin at Madison)

From information to exact communication [ECCC]
Mark Braverman (Princeton University), Ankit Garg (Princeton Unviersity), Denis Pankratov (University of Chicago), and Omri Weinstein (Princeton University)

Interactive Channel Capacity [ECCC]
Gillat Kol (Weizmann Institute of Science) and Ran Raz (Weizmann Institute of Science)

Fast Hamiltonicity checking via bases of perfect matchings [arXiv]
Marek Cygan (University of Warsaw), Stefan Kratsch (Max Planck Institute), and Jesper Nederlof (Utrecht University)

Witness Encryption and its Applications
Sanjam Garg (UC Los Angelos), Craig Gentry (IBM Watson Research Lab), Amit Sahai (UC Los Angelos), and Brent Waters (The University of Texas at Austin)

Non-Black-Box Simulation from One-Way Functions And Applications to Resettable Security [ePrint]
Kai-Min Chung (Cornell University), Rafael Pass (Cornell University), and Karn Seth (Cornell University)

A New Approach to Computing Maximum Flows using Electrical Flows
Satish Rao (UC Berkeley) and Nikhil Srivastava (Microsoft Research, India)


FOCS 2012 Accepted Papers (with pdf files)

FOCS 2012 accepted paper list is here. Following are PDF pointers to online versions.

Tight Bounds for Randomized Load Balancing on Arbitrary Network Topologies [arXiv]
Thomas Sauerwald and He Sun 

Population Recovery and Partial Identification [pdf]
Avi Wigderson and Amir Yehudayoff 

A direct product theorem for the two-party bounded-round public-coin communication 
complexity [pdf]
Rahul Jain and Attila Pereszlenyi and Penghui Yao 

Positive Results for Concurrently Secure Computation in the Plain Model [pdf]
Vipul Goyal 

Constructive Discrepancy Minimization by Walking on The Edges [arXiv]
Shachar Lovett and Raghu Meka 

Making the Long Code Shorter [pdf]
Boaz Barak and Parikshit Gopalan and Johan Hastad and Raghu Meka and Prasad 
Raghavendra and David Steurer 

On the homotopy test on surfaces [arXiv]
Francis Lazarus and Julien Rivaud 

Constructing a Pseudorandom Generator Requires an Almost Linear Number of Calls [arXiv]
Thomas Holenstein and Makrand Sinha 

Partially Symmetric Functions are Efficiently Isomorphism-Testable [arXiv]
Eric Blais and Amit Weinstein and Yuichi Yoshida 

The computational hardness of counting in two-spin models on d-regular graphs [arXiv]
Allan Sly and Nike Sun 

A PTAS for Computing the Supremum of Gaussian Processes	[arXiv]
Raghu Meka 

The tile assembly model is intrinsically universal [arXiv]
David Doty and Jack H. Lutz and Matthew J. Patitz and Robert T. Schweller and 
Scott M. Summers and Damien Woods 

Hardness of Finding Independent Sets in Almost q-Colorable Graphs
Subhash Khot and Rishi Saket 

The Privacy of the Analyst and The Power of the State
Cynthia Dwork and Moni Naor and Salil Vadhan 

Higher Cell Probe Lower Bounds for Evaluating Polynomials
Kasper Green Larsen 

Faster Algorithms for Rectangular Matrix Multiplication	[arXiv]
Francois Le Gall 

A Polylogarithimic Approximation Algorithm for Edge-Disjoint Paths 
with Congestion 2
Julia Chuzhoy and Shi Li 

Iterative rounding approximation algorithms for degree-bounded node-connectivity 
network design	[arXiv]
Takuro Fukunaga and R. Ravi 

Pseudorandomness from Shrinkage	[ECCC]
Russell Impagliazzo and Raghu Meka and David Zuckerman 

An additive combinatorics approach relating rank to communication complexity [ECCC]
Eli Ben-Sasson and Shachar Lovett and Noga Ron-Zewi 

Designing FPT algorithms for cut problems using randomized contractions	
Rajesh Chitnis and Marek Cygan and MohammadTaghi Hajiaghayi and Marcin Pilipczuk and 
Micha� Pilipczuk 

Sparse affine-invariant linear codes are locally testable [ECCC]
Eli Ben-Sasson and Noga Ron-Zewi and Madhu Sudan 

A Structure Theorem for Poorly Anticoncentrated Gaussian Chaoses and Applications 
to the Study of Polynomial Threshold Functions [arXiv]
Daniel M. Kane 

How to Construct Quantum Random Functions [ePrint]
Mark Zhandry 

A weight-scaling algorithm for min-cost imperfect matchings in bipartite graphs	[pdf]
Lyle Ramshaw and Robert E. Tarjan 

Matching with our Eyes Closed	
Gagan Goel and Pushkar Tripathi 

A New Infinity of Distance Oracles for Sparse Graphs
Mihai Patrascu and Liam Roditty and Mikkel Thorup 

A Permanent Approach to the Traveling Salesman Problem
Nisheeth K. Vishnoi 

Everywhere-Sparse Spanners via Dense Subgraphs [arXiv]
Eden Chlamtac and Michael Dinitz and Robert Krauthgamer 

Learning-graph-based Quantum Algorithm for k-distinctness [arXiv]
Aleksandrs Belovs 

Beck's three permutations conjecture: A counterexample and some consequences
Alantha Newman and Ofer Neiman and Aleksandar Nikolov 

Down the Rabbit Hole: Robust Proximity Search and Density Estimation in 
Sublinear Space	[pdf]
Sariel Har-Peled and Nirman Kumar 

On the complexity of finding narrow proofs [arXiv]
Christoph Berkholz 

Improved Distance Sensitivity Oracles via Fast Single-Source Replacement Paths
Fabrizio Grandoni and Virginia Vassilevska Williams 

LP Rounding for k-Centers with Non-uniform Hard Capacities
Marek Cygan and MohammadTaghi Hajiaghayi and Samir Khuller 

A Tight Combinatorial Algorithm for Submodular Maximization Subject to a 
Matroid Constraint [arXiv]
Yuval Filmus and Justin Ward 

Faster SDP hierarchy solvers for local rounding algorithms
Venkatesan Guruswami and Ali Kemal Sinop 

Combinatorial coloring of 3-colorable graphs [arXiv]
Ken-ichi Kawarabayashi and Mikkel Thorup 

Approximation Limits of Linear Programs (Beyond Hierarchies) [arXiv]
Gábor Braun and Samuel Fiorini and Sebastian Pokutta and David Steurer 

A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular 
Niv Buchbinder and Moran Feldman and Joseph (Seffi) Naor and Roy Schwartz 

Lower bounds on Information Complexity via zero-communication protocols 
and applications [arXiv]
Iordanis Kerenidis and Sophie Laplante and Virginie Lerays and Jeremie Roland 
and David Xiao 

Better Pseudorandom Generators from Milder Pseudorandom Restrictions
Parikshit Gopalan and Raghu Meka and Omer Reingold and Luca Trevisan and Salil Vadhan 

Almost Optimal Canonical Property Testers for Satisfiability
Christian Sohler 

On Range Searching with Semialgebraic Sets II
Pankaj K. Agarwal and Jiri Matousek and Micha Sharir 

MIP* contains NEXP
Tsuyoshi Ito and Thomas Vidick 

Geometric Complexity Theory V: Equivalence between blackbox derandomization 
of polynomial identity testing and derandomization of Noether's normalization lemma
Ketan D. Mulmuley 

Single Source - All Sinks Max Flows in Planar Digraphs 
Jakub Lacki and Yahav Nussbaum and Piotr Sankowski and Christian Wulff-Nilsen 

The Johnson-Lindenstrauss Transform Itself Preserves Differential Privacy [arXiv] 
Jeremiah Blocki and Avrim Blum and Anupam Datta and Or Sheffet 

Formulas Resilient to Short-Circuit Errors
Yael Kalai and Allison Lewko and Anup Rao 

Efficient Interactive Coding Against Adversarial Noise [ECCC]
Zvika Brakerski and Yael Tauman Kalai 

How to Allocate Tasks Asynchronously
Dan Alistarh and Michael A. Bender and Seth Gilbert and Rachid Guerraoui 

New Limits to Classical and Quantum Instance Compression [pdf]
Andrew Drucker 

Large Deviation Bounds for Decision Trees and Sampling Lower Bounds 
for AC0-circuits [ECCC]
Chris Beck and Russell Impagliazzo and Shachar Lovett 

The Locality of Distributed Symmetry Breaking [arXiv]
Leonid Barenboim and Michael Elkin and Seth Pettie and Johannes Schneider 

Representative sets and irrelevant vertices: New tools for kernelization [arXiv]
Stefan Kratsch and Magnus Wahlström 

Approximating the Expansion Profile and Almost Optimal Local 
Graph Clustering [arXiv]
Shayan Oveis Gharan and Luca Trevisan 

Algorithmic Applications of Baur-Strassen's Theorem: Shortest Cycles, 
Diameter and Matchings [arXiv]
Marek Cygan and Harold N. Gabow and Piotr Sankowski 

Learning Topic Models --- Going beyond SVD [arXiv]	  
Sanjeev Arora and Rong Ge and Ankur Moitra 

Non-Malleable Extractors, Two-Source Extractors and Privacy Amplification
Xin Li 

The power of linear programming for valued CSPs	[arXiv]
Johan Thapper and Stanislav Zivny 

Constructing Non-Malleable Commitments: A Black-Box Approach
Vipul Goyal and Chen-Kuei Lee and Rafail Ostrovsky and Ivan Visconti 

Active Property Testing [pdf]
Maria-Florina Balcan and Eric Blais and Avrim Blum and Liu Yang 

The Dynamics of Influence Systems [arXiv]
Bernard Chazelle 

Online Matching with Stochastic Rewards	
Aranyak Mehta and Debmalya Panigrahi 

Finding Correlations in Subquadratic Time, with Applications to 
Learning Parities and Juntas [ECCC]
Gregory Valiant 

The Exponential Mechanism for Social Welfare: Private, Truthful, 
and Nearly Optimal [arXiv]
Zhiyi Huang and Sampath Kannan 

How to Compute in the Presence of Leakage [ECCC]
Shafi Goldwasser and Guy Rothblum 

On-line Indexing for General Alphabets
Tsvi Kopelowitz 

Optimal Multi-Dimensional Mechanism Design: Reducing Revenue to 
Welfare Maximization
Yang Cai and Constantinos Daskalakis and S. Matthew Weinberg 

Split and Join: Strong Partitions and Universal Steiner Trees for Graphs [arXiv]
Costas Busch and Chinmoy Dutta and Jaikumar Radhakrishnan and 
Rajmohan Rajaraman and Srivathsan Srinivasagopalan 

From the Impossibility of Obfuscation to a New Non-Black-Box 
Simulation Technique  
Nir Bitansky and Omer Paneth 

Quasi-optimal multiplication of linear differential operators
Alexandre Benoit and Alin Bostan and Joris van der Hoeven 

Randomized Greedy Algorithms for the Maximum Matching Problem 
with New Analysis	
Matthias Poloczek and Mario Szegedy 

Concave Generalized Flows with Applications to Market Equilibria [arXiv]
Laszlo A. Vegh 

The Cutting Plane Method is Polynomial for Perfect Matchings
Karthekeyan Chandrasekaran and Laszlo A. Vegh and Santosh S. Vempala 

Computing Multiplicities of Lie Group Representations [arXiv]
Matthias Christandl and Brent Doran and Michael Walter 

A New Direction for Counting Perfect Matchings
Taisuke Izumi and Tadashi Wadayama 

Planar F-Deletion: Approximation, Kernelization and Optimal FPT Algorithms [pdf]
Fedor Fomin and Daniel Lokshtanov and Neeldhara Misra and Saket Saurabh 

Lower Bounds for Interactive Compression by Constant-Depth Circuits
Arkadev Chattopadhyay and Rahul Santhanam

Turing Centennial Celebration – Day 3

Welcome to Day 3 proceedings of Turing Centennial Celebration. See also Day 1 and Day 2.

  • David Harel’s talk titled “Standing on the Shoulders of a Giant”

  • An entertaining musical video about Turing test

  • Avi Wigderson’s tak titled “The Hardness of Proving Computational Hardness”. It is always exciting to watch Avi’s talks.

  • Avi says “Easiness and Hardness are two sides of the same Mobius strip”.

  • Shafi Goldwasser’s talk titled “Pseudo Deterministic Algorithms”

  • Bob Tarjan’s talk titled “Search Tree Mysteries”.

  • Dick Lipton’s talk titled “What Would Turing Be Doing Today?”. As usual Dick’s talk is very entertaining. So I took more pictures.

  • “Making Projectors work” is a grand challenge :)

  • Birds vs Frogs
  • End of Dick’s talk

  • Christos Papadimitriou’s talk titled “The Origin of Computable Numbers”. Amazing talk comparing Turing and Darwin.


The three day Turing Centennial celebration comes to an end :(


Turing Centennial Celebration – Day 2

Welcome to Day 2 proceedings of Turing Centennial Celebration. Click here for yesterday’s events. Thanks to a comment of Noman, live VIDEO is also  available.

  • Martin Davis talks about “Universality is Ubiquitous”. The following slide is from Turing’s 1947 Lecture to the London Mathematical Society.

  • James Murray starts his talk titled “Mathematical Biology, Past, Present and Future: from animal coat patterns to brain tumors to saving marriages”

  • Now I understand “How the leopard gets its spots ?”

  • Barbara Liskov’s talk titled “Programming the Turing Machine”.

  • Tom Mitchell’s talk titled “Never-Ending Language Learning”. The following slide has a quote of Alan Turing, “What we want is a machine that can learn from experience”.

  • Andrew Odlyzko’s talk titled “Turing and the Riemann zeta function”.

  • Ron Rivest’s talk titled “The Growth of Cryptography”

  • Getting ready for dinner

  • Books about Alan Turing

  • Andrew Appel talking about “Turing, Gödel, and Church at Princeton in the 1930s”. This is an inspiring talk about the history of the origins of computing and programming languages at Princeton in 1930s.

  • Jack Emery, producer of the movie talking about his inspiration behind making “Breaking the Code

  • I expected this movie to be a slow documentary. But it exceeded all my expectations. It has sharp dialogues, slick editing and top-notch performances.
  • Here is a sample of a mathematical conversation


  • Here is another sample
  • That’s all for today. Tune in tomorrow for Day 3 proceedings.

Turing Centennial Celebration – Day 1

Let me start this post with a couple of Turing Machine jokes I made up.

How many Turing machines does it take to change a lightbulb ? Just one. Turing machines can simulate each other.

A Turing machine walks into a bar. The bartender asks “what would you like to order”. Turing machine says “I am still deciding”.

As you already know, 2012 is the Year of Turing. Here at Princeton University we are celebrating this occasion from May 10 to 12. For a quick overview of the role of Princeton in the origins of computing watch the following video :

This post is a live blog of the events.

  • Les Valiant’s talk titled “Computer Science as a Natural Science”. I like the following slide saying “Darwin was a computer Scientist. Turing was a natural scientist

  • Andy Yao’s talk titled “Quantum Computing: A Great Science in the Making”. He says “Quantum Computers are coming sooner than you think. Coming soon to a store near you“.

  • Robert Kahn is starting his talk titled “A Systems Approach to Managing Distributed Information”. Among the Turing Award winners invited to this celebration, he is the only one from industry.

  • Richard Karp is starting his talk titled “Theory of Computation as an Enabling Tool for the Sciences”.

  • Richard Karp answering questions.

  • Eric Schmidt’s talk.


That’s all for today. Tune in tomorrow for Day 2 proceedings.


STOC 2012 Accepted Papers (with pdf files)

STOC 2012 accepted paper list is here. Following are PDF pointers to online versions.

    • Separating multilinear branching programs and formulas [ECCC]
      Zeev Dvir, Guillaume Malod, Sylvain Perifel, Amir Yehudayoff
    • $2^{log^{1-\epsilon} n}$ Hardness for Closest Vector Problem with Preprocessing [ECCC]
      Subhash Khot, Preyas Popat, Nisheeth Vishnoi
    • Determinism versus Nondeterminism with Arithmetic Tests and Computation [ECCC]
      Miklos Ajtai
    • Short Proofs for the Determinant Identities [arXiv]
      Pavel Hrubes, Iddo Tzameret
    • The Cell Probe Complexity of Dynamic Range Counting [arXiv]
      Kasper Green Larsen
    • Subspace Evasive Sets [arXiv]
      Zeev Dvir, Shachar Lovett
    • Monotone expansion [arXiv]
      Jean Bourgain, Amir Yehudayoff
    • Solution of the propeller conjecture in $R^3$ [arXiv]
      Steven Heilman, Aukosh Jagannath, Assaf Naor
    • Linear vs. Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds [arXiv]
      Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary, Ronald deWolf
    • On Vertex Sparsifiers with Steiner Nodes 
      Julia Chuzhoy
    • Strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives [arXiv]
      Laszlo A. Vegh
    • Routing in Undirected Graphs with Constant Congestion [arXiv]
      Julia Chuzoy
    • Pseudorandom Generators with Long Stretch and Low Locality from Random Local One-Way Functions [ECCC]
      Benny Applebaum
    • Catching the k-NAESAT threshold [arXiv]
      Amin Coja-Oghlan, Konstantinos Panagiotou
    • Edge Transitive Ramanujan Graphs and Highly Symmetric LDPC Good Codes [arXiv]
      Tali Kaufman, Alexander Lubotzky
    • A quantitative Gibbard-Satterthwaite theorem without neutrality [arXiv]
      Elchanan Mossel, Miklos Z. Racz
    • From Irreducible Representations to Locally Decodable Codes [arXiv]
      Kim Efremenko
    • Reconstruction of Depth-4 Multlinear circuits with Top Fan-in 2 [arXiv]
      Ankit Gupta, Neeraj Kayal, Satya Lokam
    • Approximation Algorithms and Hardness of Integral Concurrent Flow 
      Parinya Chalermsook, Julia Chuzoy, Alina Ene, Shi Li
    • Interactive Information Complexity [ECCC]
      Mark Braverman
    • Finding red balloons with split contracts: robustness to individuals’ selfishness [pdf]
      Manuel Cebrian, Lorenzo Coviello, Andrea Vattani, Panagiotis Voulgaris
    • Span Programs for Functions with Constant-Sized 1-certificates [arXiv]
      Aleksandrs Belovs
    • Time-Space Tradeoffs in Resolution: Superpolynomial Lower Bounds for Superlinear Space [ECCC]
      Paul Beame, Chris Beck, Russell Impagliazzo
    • Fast Matrix Rank Algorithms and Applications 
      Ho Yee Cheung, Tsz Chiu Kwok, Lap Chi Lau
    • Nearly Complete Graphs Decomposable into Large Induced Matchings and their Applications [arXiv]
      Noga Alon, Ankur Moitra, Benny Sudakov
    • When the Cut Condition is Enough; A Complete Characterization for Multiflow Problems in Series-Parallel Networks 
      Amit Chakrabarti, Lisa Fleisher, Christophe Weibel
    • Approximating the Exponential, the Lancoz Method and an $\tilde{O}(m)$-Time Spectral Algorithm for Balanced Separator [arXiv]
      Lorenzo Orecchia, Sushant Sachdeva, Nisheeth Vishnoi
    • Tight Bounds for Monotone Switching Networks via Fourier Analysis
      Siu Man Chan, Aaron Potechin
    • Tight Bounds for Distributed Functional Monitoring [arXiv]
      David P. Woodruff, Qin Zhang
    • Global Computation in a Poorly Connected World: Fast Rumor Spreading with No Dependence on Conductance [arXiv]
      Keren Censor-Hillel, Bernhard Haeupler, Jonathan A. Kelner, Petar Maymounkov
    • Folded Codes from Function Field Towers and Improved List Decoding 
      Venkatesan Guruswami, Chaoping Xing
    • Improved Smoothed Analysis of Multiobjective Optimization [arXiv]
      Tobias Brunsch, Heiko Roglin
    • Improving Chrisofides’ Algorithm for the s-t Path TSP [arXiv]
      Hyung-Chan An, Robert Kleinberg, David B. Shmoys
    • Probabilistic existence of rigid combinatorial structures [arXiv]
      Greg Kuperberg, Shachar Lovett, Ron Peled
    • Quantum Money from Hidden Subspaces 
      Scott Aaronson, Paul Christiano
    • A Complementary Pivot Algorithm for Market Equilibrium under Separable, Piecewise-Linear Concave Utilities 
      Jugal Garg, Ruta Mehta, Milind Sohoni, Vijay V. Vazirani
    • Making Polynomials Robust to Noise 
      Alexander A. Sherstov
    • Online matching with concave returns 
      Nikhil R. Devanur, Kamal Jain
    • Learning Poisson Binomial Distributions [arXiv]
      Constantinos Daskalakis, Ilias Diakonikolas, Rocco Servedio
    • Homomorphic encryption from codes [pdf]
      Andrej Bogdanov, Chin Ho Lee
    • Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates [pdf]
      Anna Gal, Kristoffer Arnsfelt Hansen, Michal Koucky, Pavel Pudlak, Emanuele Viola
    • Polyhedral Clinching Auctions and the Adwords Polytope [arXiv]
      Gagan Goel, Vahab Mirrokni, Renato Paes Leme
    • Complexity of Counting CSP with Complex Weights [arXiv]
      Jin-Yi Cai, Xi Chen
    • Beating Randomized Response on Incoherent Matrices [arXiv]
      Moritz Hardt, Aaron Roth
    • The Multiparty Communication Complexity of Set Disjointness [arXiv]
      Alexander A. Sherstov
    • Nearly Optimal Sparse Fourier Transform [arXiv]
      Haitham Hassanieh, Piotr Indyk, Dina Katabi, Eric Price
    • Certifiable Quantum Dice — Or, testable exponential randomness expansion [arXiv]
      Umesh Vazirani, Thomas Vidick
    • Prior-Free Auctions with Ordered Bidders 
      Stefano Leonardi, Tim Roughgarden
    • Using Petal-Decompositions to Build a Low Stretch Spanning Tree 
      Ittai Abraham, Ofer Neiman
    • On Identity Testing of Tensors, Low-rank Recovery and Compressed Sensing [arXiv]
      Michael A. Forbes, Amir Shpilka
    • The traveling salesman problem: low dimensionality implies a polynomial time approximation scheme [arXiv]
      Yair Bartal, Lee-Ad Gottlieb, Robert Krauthgamer
    • Competitive Contagion in Networks [arXiv]
      Sanjeev Goyal, Michael Kearns
    • Jacobian hit circuits: Hitting sets, lower bounds for depth-D occur-k formulas and depth-3 transcendence degree-k circuits [arXiv]
      Manindra Agrawal, Chandan Saha, Ramprasad Saptharishi, Nitin Saxena
    • A new point of NP-hardness for Unique Games [pdf]
      Ryan O’Donnell, John Wright
    • Approximation Algorithms for Semi-random Graph Partitioning Problems 
      Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
    • Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs [arXiv]
      Martin Grohe, Daniel Marx
    • On the limits of black-box reductions in mechanism design 
      Shuchi Chawla, Nicole Immorlica, Brendan Lucier
    • Fully Dynamic Approximate Distance Oracles for Planar Graphs via Forbidden-Set Distance labels
      Ittai Abraham, Shiri Chechik, Cyril Gavoille
    • Affine Projections of Polynomials [ECCC]
      Neeraj Kayal
    • From Query Complexity to Computational Complexity [pdf]
      Shahar Dobzinski, Jan Vondrak
    • Multiparty Computation Secure Against Continual Memory Leakage 
      Elette Boyle, Shafi Goldwasser, Abhishek Jain, Yael Tauman Kalai
    • Multiway spectral partitioning and higher-order Cheeger inequalities [arXiv]
      Shayan Oveis Gharan, James R. Lee, Luca Trevisan
    • Budget Feasible Mechanism Design: From Prior-Free to Bayesian 
      Xiaohui Bei, Ning Chen, Nick Gravin, Pinyan Lu
    • Nearly optimal solutions for the Chow Parameters Problem and low- weight approximation of halfspaces 
      Anindya De, Ilias Diakonikolas, Vitaly Feldman, Rocco Servedio
    • The freezing threshold for k-colourings of a random graph 
      Michael Molloy
    • Tight lower bounds for the online labelling problem [arXiv]
      Jan Bulanek, Michal Koucky, Michael Saks
    • Computing a Nonnegative Matrix Factorization – Provably [arXiv]
      Sanjeev Arora, Rong Ge, Ravi Kannan, Ankur Moitra
    • Many Sparse Cuts via Higher Eigenvalues [arXiv]
      Anand Louis, Prasad Raghavendra, Prasad Tetali, Santosh Vempala
    • A Rigorous Analyis of One-Dimensional Schelling Segregation 
      Christina Brandt, Nicole Immorlica, Gautam Kamath, Robert Kleinberg
    • A Near-Linear Time $\eps$-Approximation Algorithm for Geometric Bipartite Matching [pdf]
      R. Sharathkumar, Pankaj K. Agarwal
    • Matroid Prophet Inequalities [arXiv]
      Robert Kleinberg, Matthew Weinberg
    • Rational Proofs 
      Pablo Azar, Silvio Micali
    • Robust satisfiability of constraint satisfaction problems [ECCC]
      Libor Barto, Marcin Kozik
    • On-the-Fly Multiparty Computation on the Cloud via Multikey Fully Homomorphic Encryption 
      Adriana Lopez-Alt, Eran Tromer, Vinod Vaikuntanathan
    • Polynomial Time Algorithms for Multi-Type Branching Processes and Stochastic Context-Free Grammars [arXiv]
      Kousha Etessami, Alistair Stewart, Mihalis Yannakakis
    • Unconditionally Differentially Private Mechanisms for Linear Queries 
      Aditya Bhaskara, Daniel Dadush, Ravishankar Krishnaswamy, Kunal Talwar
    • Multiplying Matrices Faster Than Coppersmith-Winograd [pdf]
      Virginia Vassilevska Williams
    • Matroids and Integrality Gaps for Hypergraphic Steiner Tree Relaxations [arXiv]
      Michel X. Goemans, Neil Olver, Thomas Rothvoss, Rico Zenklusen
    • Minimax Option Pricing Meets Black-Scholes in the Limit [arXiv]
      Jacob Abernethy, Rafael Frongillo, Andre Wibisono
    • Characterizing Pseudoentropy and Simplifying Pseudorandom Generator Constructions [ECCC]
      Salil Vadhan, Colin Jia Zheng
    • Optmal Online Buffer Scheduling for Block Devices 
      Anna Adamaszek, Artur Czumaj, Matthias Englert, Harald Raecke
    • On the Virtue of Succinct Proofs: Amplifying Communication Complexity Hardness to Time-Space Trade-offs in Proof Complexity 
      Trinh Huynh, Jacob Nordstrom
    • Strict Fibonacci Heaps 
      Gerth Stolting Brodal, George Lagogiannis, Robert E. Tarjan
    • Design Extractors, Non-Malleable Condensers and Privacy Amplification [ECCC]
      Xin Li
    • Optimal Private Halfspace Counting via Discrepancy 
      S. Muthukrishnan, Aleksandar Nikolov
    • Beyond Laplacians: Faster Approximations of Multicommodity Flow in Undirected Graphs Using Quadratically Coupled Electrical Flows 
      Jonathan A. Kelner, Gary L. Miller, Richard Peng
    • An Algorithmic Characerization of Multi-Dimensional Mechanisms [arXiv]
      Yang Cai, Constantinos Deskalakis, S. Matthew Weinberg
    • Tight Time-Space Tradeoff for Mutual Exclusion 
      Nikhil Bansal, Vibhor Bhatt, Prasad Jayanti, Ranganath Kondapally
    • Hypercontractivity, Sum-of-Squares Proofs, and their Applications 
      Boaz Barak, Aram W. Harrow, Jonathan Kelner, David Steurer, Yuan Zhou
    • Tight RMR Lower Bounds for Randomized Mutual Exclusion George Giakkoupis, Philipp Woelfel

FOCS 2011 Accepted Papers (with pdf files)

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

1. The Grothendieck constant is strictly smaller than Krivine’s bound [arXiv]

Mark Braverman, Konstantin Makarychev, Yury Makarychev, Assaf Naor

2. The minimum k-way cut of bounded size is fixed-parameter tractable [arXiv]

Mikkel Thorup and Ken-ichi Kawarabayashi

3. Randomness buys depth for approximate counting [ECCC]

Emanuele Viola

4. Local Distributed Decision [arXiv]

Pierre Fraigniaud and Amos Korman and David Peleg

5. A Small PRG for Polynomial Threshold Functions of Gaussians [arXiv]

Daniel M. Kane

6. Evolution with Recombination [pdf]

Varun Kanade

7. Extractors for circuit sources [pdf]

Emanuele Viola

8. The Second-Belief Mechanism. [pdf]

Jing Chen and Silvio Micali

9. New extension of the Weil bound for character sums with applications to coding [ECCC]

Tali Kaufman and Shachar Lovett

10. A Two Prover One Round Game with Strong Soundness

Subhash Khot and Muli Safra

11. Optimal testing of multivariate polynomials over small prime fields [ECCC]

Elad Haramaty and Amir Shpilka and Madhu Sudan

12. Fully dynamic maximal matching in O(log n) update time [arXiv]

Surender Baswana and Manoj Gupta and Sandeep Sen

13. Optimal bounds for quantum bit commitment [arXiv]

André Chailloux and Iordanis Kerenidis



15. Solving connectivity problems parameterized by treewidth in single exponential time [arXiv]

Marek Cygan and Jesper Nederlof and Marcin Pilipczuk and Micha3 Pilipczuk and Johan M. M. van Rooij and Jakub Onufry Wojtaszczyk

16. How to Play Unique Games Against a Semi-Random Adversary [arXiv]

Alexandra Kolla and Konstantin Makarychev and Yury Makarychev

17. Near-Optimal Column-Based Matrix Reconstruction [arXiv]

Christos Boutsidis and Petros Drineas and Malik Magdon-Ismail

18. Tight lower bounds for 2-query LCCs over finite fields [ECCC]

Arnab Bhattacharyya and Zeev Dvir and Shubhangi Saraf and Amir Shpilka

19. Separator Theorems for Minor-Free and Shallow Minor-Free Graphs with Applications [arXiv]

Christian Wulff-Nilsen

20. 3-SAT Faster and Simpler – Unique-SAT Bounds for PPSZ Hold in General [arXiv]

Timon Hertli

21. On Range Searching in the Group Model and Combinatorial Discrepancy [pdf]

Kasper Green Larsen

22. Coin Flipping with Constant Bias Implies One-Way Functions

Iftach Haitner and Eran Omri

23. The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke- Howson Solutions. [arXiv]

Paul W. Goldberg and Christos H. Papadimitriou and Rahul Savani

24. Information Equals Amortized Communication [arXiv]

Mark Braverman and Anup Rao

25. Graph Connectivities, Network Coding, and Expander Graphs

Ho Yee Cheung and Lap Chi Lau and Kai Man Leung

26. Limitations of Randomized Mechanisms for Combinatorial Auctions

Shaddin Dughmi and Jan Vondrak

27. How to Store a Secret on Continually Leaky Devices [pdf]

Yevgeniy Dodis and Allison Lewko and Brent Waters and Daniel Wichs

28. A Polylogarithmic-Competitive Algorithm for the k-Server Problem

Nikhil Bansal and Niv Buchbinder and Aleksander Madry and Seffi Naor

29. Minimum Weight Cycles and Triangles: Equivalences and Algorithms [arXiv]

Liam Roditty and Virginia Vassilevska Williams

30. Streaming Algorithms via Precision Sampling [arXiv]

Alexandr Andoni and Robert Krauthgamer and Krzysztof Onak

31. A Parallel Approximation Algorithm for Positive Semidefinite Programming [arXiv]

Rahul Jain and Penghui Yao

32. Planar Graphs: Random Walks and Bipartiteness Testing

Artur Czumaj and Morteza Monemizadeh and Krzysztof Onak and Christian Sohler

33. Pseudorandomness for read-once formulas

Andrej Bogdanov and Periklis Papakonstantinou and Andrew Wan

34. Approximating Graphic TSP by Matchings [arXiv]

Tobias Moemke and Ola Svensson

35. Efficient Distributed Medium Access [arXiv]

Devavrat Shah and Jinwoo Shin and Prasad Tetali

36. Near Linear Lower Bound for Dimension Reduction in L1 [pdf]

Alexandr Andoni and Moses S. Charikar and Ofer Neiman and Huy L. Nguyen

37. Maximum Edge-Disjoint Paths in Planar Graphs with Congestion 2

Lo\”ic S\’eguin-Charbonneau and F. Bruce Shepherd

38. Min-Max Graph Partitioning and Small-Set Expansion

Nikhil Bansal and Uriel Feige and Robert Krauthgamer and Konstantin Makarychev and Viswanath Nagarajan and Joseph (Seffi) Naor and Roy Schwartz

39. An FPTAS for #Knapsack and Related Counting Problems

Parikshit Gopalan and Adam Klivans and Raghu Meka and Daniel Stefankovic and Santosh Vempala and Eric Vigoda

40. Improved Mixing Condition on the Grid for Counting and Sampling Independent Sets [arXiv]

Ricardo Restrepo and Jinwoo Shin and Prasad Tetali and Eric Vigoda and Linji Yang

41. Balls and Bins: Smaller Hash Families and Faster Evaluation [ECCC]

L. Elisa Celis and Omer Reingold and Gil Segev and Udi Wieder

42. Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time [arXiv]

Glencora Borradaile and Philip N. Klein and Shay Mozes and Yahav Nussbaum and Christian Wulff-Nilsen

43. Quantum query complexity of state conversion

Troy Lee and Rajat Mittal and Ben W. Reichardt and Robert Spalek and Mario Szegedy

44. A constant factor approximation algorithm for unsplittable flow on paths [arXiv]

Paul Bonsma and Jens Schulz and Andreas Wiese

45. The Graph Minor Algorithm with Parity Conditions

Ken-ichi Kawarabayashi and Bruce Reed and Paul Wollan

46. Mutual Exclusion with O(log2 log n) Amortized Work

Michael A. Bender and Seth Gilbert

47. How Bad is Forming Your Own Opinion? [pdf]

David Bindel and Jon Kleinberg and Sigal Oren

48. The Complexity of Renaming [HTML]

Dan Alistarh and James Aspnes and Seth Gilbert and Rachid Guerraoui

49. On the Power of Adaptivity in Sparse Recovery

Piotr Indyk and Eric Price and David Woodruff

50. Enumerative Lattice Algorithms in any Norm via M-ellipsoid Coverings [arXiv]

Daniel Dadush and Chris Peikert and Santosh Vempala

51. Efficient and Explicit Coding for Interactive Communication

Ran Gelles and Ankur Moitra and Amit Sahai

52. Dispersers for affine sources with sub-polynomial entropy

Ronen Shaltiel

53. Approximation Algorithms for Correlated Knaspacks and Non-Martingale Bandits [pdf]

Anupam Gupta and Ravishankar Krishnaswamy and Marco Molinaro and R. Ravi

54. Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD Objectives [arXiv]

Venkatesan Guruswami and Ali Kemal Sinop

55. A Unified Continuous Greedy Algorithm for Submodular Maximization

Moran Feldman and Joseph (Seffi) Naor and Roy Schwartz

56. Bayesian Combinatorial Auctions: Expanding Single Buyer Mechanisms to Many Buyers [arXiv]

Saeed Alaei

57.  Extreme-Value Theorems for Optimal Multidimensional Pricing [arXiv]

Yang Cai and Constantinos Daskalakis

58.  Approximation Algorithms for Submodular Multiway Partition [arXiv]

Chandra Chekuri and Alina Ene

59. Delays and the Capacity of Continuous-time Channels [arXiv]

Sanjeev Khanna and Madhu Sudan

60. Fully Homomorphic Encryption without Squashing Using Depth-3 Arithmetic Circuits [ePrint]

Craig Gentry and Shai Halevi

61. A Randomized Rounding Approach to the Traveling Salesman Problem [pdf]

Shayan Oveis Gharan and Amin Saberi and Mohit Singh

62.  Algorithms for the Generalized Sorting Problem

Zhiyi Huang and Sampath Kannan and Sanjeev Khanna

63. Privacy Amplification and Non-Malleable Extractors Via Character Sums [arXiv]

Xin Li and Trevor D. Wooley and David Zuckerman

64. A nearly mlogn time solver for SDD linear systems

Ioannis Koutis and Gary L. Miller and Richard Peng

65. Which Networks Are Least Susceptible to Cascading Failures? [pdf]

Lawrence Blume and David Easley and Jon Kleinberg and Robert Kleinberg and Eva Tardos

66. Online Node-weighted Steiner Tree and Related Problems

Joseph (Seffi) Naor and Debmalya Panigrahi and Mohit Singh

67. Welfare and Profit Maximization with Production Costs

Avrim Blum and Anupam Gupta and Yishay Mansour and Ankit Sharma

68. On the complexity of Commuting Local Hamiltonians, and tight conditions for Topological Order in such systems [arXiv]

Dorit Aharonov and Lior Eldar

69. Efficient Fully Homomorphic Encryption from (Standard) LWE [ePrint]

Zvika Brakerski and Vinod Vaikuntanathan

70. Testing and Reconstruction of Lipschitz Functions with Applications to Data Privacy [ECCC]

Madhav Jha and Sofya Raskhodnikova

71. Lexicographic Products and the Power of Non-Linear Network Coding

Anna Blasiak and Robert Kleinberg and Eyal Lubetzky

72. Efficient computation of approximate pure Nash equilibria in congestion games [arXiv]

Ioannis Caragiannis and Angelo Fanelli and Nick Gravin and Alexander Skopalik

73.  How to Garble Arithmetic Circuits

Benny Applebaum and Yuval Ishai and Eyal Kushilevitz

74. Rounding Semidefinite Programming Hierarchies via Global Correlation [arXiv]

Boaz Barak and Prasad Raghavendra and David Steurer

75. Efficient Reconstruction of Random Multilinear Formulas

Ankit Gupta and Neeraj Kayal and Satya Lokam

76. Markov Layout

Flavio Chierichetti and Ravi Kumar and Prabhakar Raghavan

77. (1+eps)-Approximate Sparse Recovery

Eric Price and David P. Woodruff

78. Quadratic Goldreich-Levin Theorems [arXiv]

Madhur Tulsiani and Julia Wolf

79. Maximizing Expected Utility for Stochastic Combinatorial Optimization Problems [arXiv]

Jian Li and Amol Deshpande

80. Stateless Cryptographic Protocols

Vipul Goyal and Hemanta K. Maji

81. Steiner Shallow-Light Trees are Exponentially Lighter than Spanning Ones

Michael Elkin and Shay Solomon

82. An algebraic proof of a robust social choice impossibility theorem

Dvir Falik and Ehud Friedgut

83. The Power of Linear Estimators [pdf]

Gregory Valiant and Paul Valiant

84. The Randomness Complexity of Parallel Repetition

Kai-Min Chung and Rafael Pass

85. The Complexity of Quantum States – a combinatorial approach

Dorit Aharonov and Itai Arad and Zeph Landau and Umesh Vazirani

STOC 2011 Accepted Papers (with pdf files)

  1. Quantum One-Way Communication can be Exponentially Stronger Than Classical Communication Bo’az Klartag and Oded Regev [arXiv]
  2. Multicut is FPT Nicolas Bousquet and Jean Daligault and Stephan Thomasse [arXiv]
  3. Pareto Optimal Solutions for Smoothed Analysts Ankur Moitra and Ryan O’Donnell [arXiv]
  4. An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance Amit Chakrabarti and Oded Regev [arXiv]
  5. Constant Round Non-Malleable Protocols using One Way Functions Vipul Goyal [ePrint]
  6. Fixed-parameter tractability of multicut parameterized by the size of the cutset Daniel Marx and Igor Razgon [arXiv]
  7. Secure Computation with Information Leaking to an Adversary Miklos Ajtai
  8. Optimal Constant-Time Approximation Algorithms and (Unconditional) Inapproximability Results for Every Bounded-Degree CSP Yuichi Yoshida [ECCC]
  9. Near-Optimal Private Approximation Protocols via a Black-Box Transformation David P. Woodruff
  10. Cover times, blanket times, and majorizing measures Jian Ding and James R. Lee and Yuval Peres [arXiv]
  11. Breaking the $k^2$ barrier for explicit RIP matrices Jean Bourgain, S. J. Dilworth, Kevin Ford, Sergei Konyagin, Denka Kutzarova [pdf]
  12. Analyzing Network Coding Gossip Made Easy Bernhard Haeupler [arXiv]
  13. Deterministic Construction of a high dimensional $\ell_p$ section in $\ell_1^n$ for any $p<2$ Zohar S. Karnin [ECCC]
  14. Schaefer’s Theorem for Graphs Manuel Bodirsky and Michael Pinsker [arXiv]
  15. Tight Bounds for Parallel Randomized Load Balancing Christoph Lenzen and Roger Wattenhofer [pdf]
  16. Pseudorandom Generators for Group Products Michal Koucky and Prajakta Nimbhorkar and Pavel Pudlak [pdf]
  17. Contraction Decomposition in H-Minor-Free Graphs and Algorithmic Applications Erik Demaine and Mohammad Hajiaghayi and Ken-ichi Kawarabayashi
  18. Correlation testing for affine invariant properties on $\F_p^n$ in the high error regime Hamed Hatami and Shachar Lovett
  19. Every Property of Hyperfinite Graphs is Testable Ilan Newman and Christian Sohler
  20. Fast Moment Estimation in Data Streams in Optimal Space Daniel M. Kane and Jelani Nelson and Ely Porat and David P. Woodruff [arXiv]
  21. An Algorithm for the Graph Crossing Number Problem Julia Chuzhoy [arXiv]
  22. From Affine to Two-Source Extractors via Approximate Duality Eli Ben-Sasson, Noga Zewi [ECCC]
  23. On Optimal Single-Item Auctions Christos Papadimitriou and George Pierrakos [arXiv]
  24. Directed Spanners via Flow-Based Linear Programs Michael Dinitz and Robert Krauthgamer [arXiv]
  25. Mechanism design with uncertain inputs (to err is human, to forgive divine) Uriel Feige and Moshe Tennenholtz
  26. Santa Claus Schedules Jobs on Unrelated Machines Ola Svensson [arXiv]
  27. Rank Bounds for Design Matrices with Applications to Combinatorial Geometry and Locally Correctable Codes Boaz Barak and Zeev Dvir and Avi Wigderson and Amir Yehudayoff [ECCC]
  28. A simpler algorithm and shorter proof for the graph minor decomposition Ken-ichi Kawarabayashi and Paul Wollan
  29. Finding topological subgraphs is fixed-parameter tractable Martin Grohe and Ken-ichi Kawarabayashi and Daniel Marx and Paul Wollan [arXiv]
  30. Constant-Round Non-Malleable Commitments from Any One-Way Function Huijia Lin, Rafael Pass [ePrint]
  31. Privacy-preserving Statistical Estimation with Optimal Convergence Rates Adam Smith
  32. Learning Submodular Functions Maria Florina Balcan and Nicholas J. A. Harvey [arXiv]
  33. Pseudorandom Generators for Combinatorial Shapes Parikshit Gopalan and Raghu Meka and Omer Reingold and David Zuckerman [ECCC]
  34. NP-Hardness of Approximately Solving Linear Equations Over Reals Subhash Khot and Dana Moshkovitz [ECCC]
  35. Towards Coding for Maximum Errors in Interactive Communication Mark Braverman and Anup Rao [pdf]
  36. K-Median Clustering, Model-Based Compressive Sensing, and Sparse Recovery for Earth Mover Distance Piotr Indyk and Eric Price
  37. Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in Undirected Graphs Paul Christiano and Jonathan A. Kelner and Aleksander Madry and Daniel A. Spielman and Shang-Hua Teng [arXiv]
  38. A General Framework for Graph Sparsification Wai Shing Fung and Ramesh Hariharan and Nicholas J. A. Harvey and Debmalya Panigrahi
  39. Breaking O(n^{1/2})-approximation algorithms for the edge-disjoint paths problem Ken-ichi Kawarabayashi and Yusuke Kobayashi
  40. Linearizable Implementations Do Not Suffice for Randomized Distributed Computation Wojciech Golab and Lisa Higham and Philipp Woelfel
  41. Online Bipartite Matching with Unknown Distributions Chinmay Karande and Aranyak Mehta and Pushkar Tripathi
  42. Near-optimal distortion bounds for embedding doubling spaces into $L_1$ James R. Lee and Anastasios Sidiropoulos
  43. Mechanisms for (Mis)allocating Scientific Credit Jon Kleinberg and Sigal Oren
  44. Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes Chandra Chekuri and Jan Vondrak and Rico Zenklusen
  45. Improved Minimum Cuts and Maximum Flows in Undirected Planar Graphs Giuseppe F. Italiano, Yahav Nussbaum, Piotr Sankowski, and Christian Wulff-Nilsen
  46. An Impossibility Result for Truthful Combinatorial Auctions with Submodular Valuations Shahar Dobzinski [arXiv]
  47. Geometric Complexity Theory and Tensor Rank Peter Buergisser and Christian Ikenmeyer [arXiv]
  48. A quasipolynomial-time algorithm for the quantum separability problem Fernando Brandao and Matthias Christandl and Jon Yard
  49. A Full Derandomization of Schoening’s k-SAT Algorithm Robin A. Moser and Dominik Scheder [arXiv]
  50. Rank-1 Bimatrix Games: A Homeomorphism and a Polynomial Time Algorithm Bharat Adsul and Jugal Garg and Ruta Mehta and Milind Sohoni [arXiv]
  51. How to Leak on Key Updates Allison Lewko and Mark Lewko and Brent Waters
  52. Separating Succinct Non-Interactive Arguments From All Falsifiable Assumptions Craig Gentry and Daniel Wichs [ePrint]
  53. Social Networks Spread Rumors in Sublogarithmic Time Benjamin Doerr and Mahmoud Fouz and Tobias Friedrich
  54. High-rate codes with sublinear-time decoding Swastik Kopparty and Shubhangi Saraf and Sergey Yekhanin [ECCC]
  55. The Computational Complexity of Linear Optics Scott Aaronson and Alex Arkhipov [arXiv]
  56. Dueling algorithms Nicole Immorlica and Adam Tauman Kalai and Brendan Lucier and Ankur Moitra and Andrew Postlewaite and Moshe Tennenholtz [arXiv]
  57. Blackbox identity testing for bounded top fanin depth-3 circuits: the field doesn’t matter Nitin Saxena and C. Seshadhri [ECCC]
  58. Don’t Rush into a Union: Take Time to Find Your Roots Mihai Patrascu and Mikkel Thorup
  59. From Convex Optimization to Randomized Mechanisms: Toward Optimal Combinatorial Auctions for Submodular Bidders Shaddin Dughmi and Tim Roughgarden and Qiqi Yan
  60. Privately Releasing Conjunctions and the Statistical Query Barrier Anupam Gupta and Moritz Hardt and Aaron Roth and Jonathan Ullman [arXiv]
  61. Optimal Path Search in Small Worlds: Dimension Matters George Giakkoupis and Nicolas Schabanel
  62. Distributed Verification and Hardness of Distributed Approximation Atish Das Sarma and Stephan Holzer and Liah Kor and Amos Korman and Danupon Nanongkai and Gopal Pandurangan and David Peleg and Roger Wattenhofer [arXiv]
  63. Parallel Repetition of Entangled Games Julia Kempe and Thomas Vidick [arXiv]
  64. Subspace Embeddings for the L_1-norm with Applications Christian Sohler and David Woodruff
  65. A Unified Framework for Approximating and Clustering Data Dan Feldman and Michael Langberg
  66. The Equivalence of the Random Oracle Model and the Ideal Cipher Model, Revisited Thomas Holenstein and Robin Kunzler and Stefano Tessaro [arXiv]
  67. Limits of Provable Security From Standard Assumptions Rafael Pass
  68. Optimal Auctions with Correlated Bidders are Easy Shahar Dobzinski and Hu Fu and Robert Kleinberg [arXiv]
  69. Strong Direct Product Theorems for Quantum Communication and Query Complexity Alexander A. Sherstov [arXiv]
  70. Inner Product Spaces for MinSum Coordination Mechanisms Richard Cole and Jose R. Correa and Vasilis Gkatzelis and Vahab Mirrokni and Neil Olver [arXiv]
  71. The Topology of Wireless Communication Erez Kantor and Zvi Lotker and Merav Parter and David Peleg
  72. An LLL-Reduction Algorithm with Quasi-linear Time Complexity Andrew Novocin and Damien Stehle and Gilles Villard [pdf]
  73. From Low-Distortion Norm Embeddings to Explicit Uncertainty Relations and Efficient Information Locking Omar Fawzi and Patrick Hayden and Pranab Sen [arXiv]
  74. The Power of Simple Tabulation Hashing Mihai Patrascu and Mikkel Thorup [arXiv]
  75. Subexponential lower bounds for randomized pivoting rules for the simplex algorithm Oliver Friedmann and Thomas Dueholm Hansen and Uri Zwick [pdf]
  76. Almost Settling the Hardness of Noncommutative Determinant Steve Chien and Prahladh Harsha and Alistair Sinclair and Srikanth Srinivasan [arXiv]
  77. Approximate Polytope Membership Queries Sunil Arya and Guilherme D. da Fonseca and David M. Mount [pdf]
  78. Exact Algorithms for Solving Stochastic Games Kristoffer Arnsfelt Hansen and Michal Koucky and Niels Lauritzen and Peter Bro Miltersen and Elias P. Tsigaridas
  79. Online Bipartite Matching with Random Arrivals: A Strongly Factor Revealing LP Approach Mohammad Mahdian and Qiqi Yan
  80. Estimating the unseen: an n/log(n)-sample estimator for entropy, support size, and other distribution properties, with a proof of optimality via two new central limit theorems Gregory Valiant and Paul Valiant
  81. Almost Tight Bounds for Reordering Buffer Management Anna Adamaszek and Artur Czumaj and Matthias Englert and Harald Raecke
  82. Black-Box Identity Testing of Depth-4 Multilinear Circuits Shubhangi Saraf and Ilya Volkovich
  83. Moser and Tardos meet Lovasz Kashyap Kolipaka and Mario Szegedy
  84. On the Complexity of Powering in Finite Fields Swastik Kopparty

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.