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
Advertisements
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.