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



TrueShelf 1.0

One year back (on 6/6/12) I announced a beta version of TrueShelf, a social-network for sharing exercises and puzzles especially in mathematics and computer science. After an year of testing and adding new features, now I can say that TrueShelf is out of beta.

TrueShelf turned out to be a very useful website. When students ask me for practice problems (or books) on a particular topic, I simply point them to trueshelf and tell them the tags related to that topic. When I am advising students on research projects, I first tell them to solve all related problems (in the first couple of weeks) to prepare them to read research papers.

Here are the features in TrueShelf 1.0.

  • Post an exercise (or) multiple-choice question (or) video (or) notes.
  • Solve any multiple-choice question directly on the website.
  • Add topic and tags to any post
  • Add source or level (high-school/undergraduate/graduate/research).
  • Show text-books related to a post
  • Show related posts for every post.
  • View printable version (or) LaTex version of any post.
  • Email / Tweet / share on facebook (or) Google+ any post directly from the post.
  • Add any post to your Favorites
  • Like (a.k.a upvote) any post.

Feel free to explore TrueShelf, contribute new exercises and let me know if you have any feedback (or) new features you want to see. You can also follow TrueShelf on facebooktwitter and google+. Here is a screenshot highlighting the important features.