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
Like this:
Like Loading...
Related
could you fix the formatting? some of the links/text won’t wrap around, and this means some of the links aren’t viewable/clickable
Fixed it. Hope this helps.