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 
Maximization
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