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

———————————————————————————————————————————————————–

2 thoughts on “FOCS 2013 Accepted Papers (with pdf files)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s