FOCS 2011 Accepted Papers (with pdf files)

FOCS 2011 accepted paper list with abstracts is here. Following are PDF pointers to online versions.

1. The Grothendieck constant is strictly smaller than Krivine’s bound [arXiv]

Mark Braverman, Konstantin Makarychev, Yury Makarychev, Assaf Naor

2. The minimum k-way cut of bounded size is fixed-parameter tractable [arXiv]

Mikkel Thorup and Ken-ichi Kawarabayashi

3. Randomness buys depth for approximate counting [ECCC]

Emanuele Viola

4. Local Distributed Decision [arXiv]

Pierre Fraigniaud and Amos Korman and David Peleg

5. A Small PRG for Polynomial Threshold Functions of Gaussians [arXiv]

Daniel M. Kane

6. Evolution with Recombination [pdf]

Varun Kanade

7. Extractors for circuit sources [pdf]

Emanuele Viola

8. The Second-Belief Mechanism. [pdf]

Jing Chen and Silvio Micali

9. New extension of the Weil bound for character sums with applications to coding [ECCC]

Tali Kaufman and Shachar Lovett

10. A Two Prover One Round Game with Strong Soundness

Subhash Khot and Muli Safra

11. Optimal testing of multivariate polynomials over small prime fields [ECCC]

Elad Haramaty and Amir Shpilka and Madhu Sudan

12. Fully dynamic maximal matching in O(log n) update time [arXiv]

Surender Baswana and Manoj Gupta and Sandeep Sen

13. Optimal bounds for quantum bit commitment [arXiv]

André Chailloux and Iordanis Kerenidis

14. SHARP MIXING TIME BOUNDS FOR SAMPLING RANDOM SURFACES

PIETRO CAPUTO AND FABIO MARTINELLI AND FABIO LUCIO TONINELLI

15. Solving connectivity problems parameterized by treewidth in single exponential time [arXiv]

Marek Cygan and Jesper Nederlof and Marcin Pilipczuk and Micha3 Pilipczuk and Johan M. M. van Rooij and Jakub Onufry Wojtaszczyk

16. How to Play Unique Games Against a Semi-Random Adversary [arXiv]

Alexandra Kolla and Konstantin Makarychev and Yury Makarychev

17. Near-Optimal Column-Based Matrix Reconstruction [arXiv]

Christos Boutsidis and Petros Drineas and Malik Magdon-Ismail

18. Tight lower bounds for 2-query LCCs over finite fields [ECCC]

Arnab Bhattacharyya and Zeev Dvir and Shubhangi Saraf and Amir Shpilka

19. Separator Theorems for Minor-Free and Shallow Minor-Free Graphs with Applications [arXiv]

Christian Wulff-Nilsen

20. 3-SAT Faster and Simpler – Unique-SAT Bounds for PPSZ Hold in General [arXiv]

Timon Hertli

21. On Range Searching in the Group Model and Combinatorial Discrepancy [pdf]

Kasper Green Larsen

22. Coin Flipping with Constant Bias Implies One-Way Functions

Iftach Haitner and Eran Omri

23. The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke- Howson Solutions. [arXiv]

Paul W. Goldberg and Christos H. Papadimitriou and Rahul Savani

24. Information Equals Amortized Communication [arXiv]

Mark Braverman and Anup Rao

25. Graph Connectivities, Network Coding, and Expander Graphs

Ho Yee Cheung and Lap Chi Lau and Kai Man Leung

26. Limitations of Randomized Mechanisms for Combinatorial Auctions

Shaddin Dughmi and Jan Vondrak

27. How to Store a Secret on Continually Leaky Devices [pdf]

Yevgeniy Dodis and Allison Lewko and Brent Waters and Daniel Wichs

28. A Polylogarithmic-Competitive Algorithm for the k-Server Problem

Nikhil Bansal and Niv Buchbinder and Aleksander Madry and Seffi Naor

29. Minimum Weight Cycles and Triangles: Equivalences and Algorithms [arXiv]

Liam Roditty and Virginia Vassilevska Williams

30. Streaming Algorithms via Precision Sampling [arXiv]

Alexandr Andoni and Robert Krauthgamer and Krzysztof Onak

31. A Parallel Approximation Algorithm for Positive Semidefinite Programming [arXiv]

Rahul Jain and Penghui Yao

32. Planar Graphs: Random Walks and Bipartiteness Testing

Artur Czumaj and Morteza Monemizadeh and Krzysztof Onak and Christian Sohler

33. Pseudorandomness for read-once formulas

Andrej Bogdanov and Periklis Papakonstantinou and Andrew Wan

34. Approximating Graphic TSP by Matchings [arXiv]

Tobias Moemke and Ola Svensson

35. Efficient Distributed Medium Access [arXiv]

Devavrat Shah and Jinwoo Shin and Prasad Tetali

36. Near Linear Lower Bound for Dimension Reduction in L1 [pdf]

Alexandr Andoni and Moses S. Charikar and Ofer Neiman and Huy L. Nguyen

37. Maximum Edge-Disjoint Paths in Planar Graphs with Congestion 2

Lo\”ic S\’eguin-Charbonneau and F. Bruce Shepherd

38. Min-Max Graph Partitioning and Small-Set Expansion

Nikhil Bansal and Uriel Feige and Robert Krauthgamer and Konstantin Makarychev and Viswanath Nagarajan and Joseph (Seffi) Naor and Roy Schwartz

39. An FPTAS for #Knapsack and Related Counting Problems

Parikshit Gopalan and Adam Klivans and Raghu Meka and Daniel Stefankovic and Santosh Vempala and Eric Vigoda

40. Improved Mixing Condition on the Grid for Counting and Sampling Independent Sets [arXiv]

Ricardo Restrepo and Jinwoo Shin and Prasad Tetali and Eric Vigoda and Linji Yang

41. Balls and Bins: Smaller Hash Families and Faster Evaluation [ECCC]

L. Elisa Celis and Omer Reingold and Gil Segev and Udi Wieder

42. Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time [arXiv]

Glencora Borradaile and Philip N. Klein and Shay Mozes and Yahav Nussbaum and Christian Wulff-Nilsen

43. Quantum query complexity of state conversion

Troy Lee and Rajat Mittal and Ben W. Reichardt and Robert Spalek and Mario Szegedy

44. A constant factor approximation algorithm for unsplittable flow on paths [arXiv]

Paul Bonsma and Jens Schulz and Andreas Wiese

45. The Graph Minor Algorithm with Parity Conditions

Ken-ichi Kawarabayashi and Bruce Reed and Paul Wollan

46. Mutual Exclusion with O(log2 log n) Amortized Work

Michael A. Bender and Seth Gilbert

47. How Bad is Forming Your Own Opinion? [pdf]

David Bindel and Jon Kleinberg and Sigal Oren

48. The Complexity of Renaming [HTML]

Dan Alistarh and James Aspnes and Seth Gilbert and Rachid Guerraoui

49. On the Power of Adaptivity in Sparse Recovery

Piotr Indyk and Eric Price and David Woodruff

50. Enumerative Lattice Algorithms in any Norm via M-ellipsoid Coverings [arXiv]

Daniel Dadush and Chris Peikert and Santosh Vempala

51. Efficient and Explicit Coding for Interactive Communication

Ran Gelles and Ankur Moitra and Amit Sahai

52. Dispersers for affine sources with sub-polynomial entropy

Ronen Shaltiel

53. Approximation Algorithms for Correlated Knaspacks and Non-Martingale Bandits [pdf]

Anupam Gupta and Ravishankar Krishnaswamy and Marco Molinaro and R. Ravi

54. Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD Objectives [arXiv]

Venkatesan Guruswami and Ali Kemal Sinop

55. A Unified Continuous Greedy Algorithm for Submodular Maximization

Moran Feldman and Joseph (Seffi) Naor and Roy Schwartz

56. Bayesian Combinatorial Auctions: Expanding Single Buyer Mechanisms to Many Buyers [arXiv]

Saeed Alaei

57.  Extreme-Value Theorems for Optimal Multidimensional Pricing [arXiv]

Yang Cai and Constantinos Daskalakis

58.  Approximation Algorithms for Submodular Multiway Partition [arXiv]

Chandra Chekuri and Alina Ene

59. Delays and the Capacity of Continuous-time Channels [arXiv]

Sanjeev Khanna and Madhu Sudan

60. Fully Homomorphic Encryption without Squashing Using Depth-3 Arithmetic Circuits [ePrint]

Craig Gentry and Shai Halevi

61. A Randomized Rounding Approach to the Traveling Salesman Problem [pdf]

Shayan Oveis Gharan and Amin Saberi and Mohit Singh

62.  Algorithms for the Generalized Sorting Problem

Zhiyi Huang and Sampath Kannan and Sanjeev Khanna

63. Privacy Amplification and Non-Malleable Extractors Via Character Sums [arXiv]

Xin Li and Trevor D. Wooley and David Zuckerman

64. A nearly mlogn time solver for SDD linear systems

Ioannis Koutis and Gary L. Miller and Richard Peng

65. Which Networks Are Least Susceptible to Cascading Failures? [pdf]

Lawrence Blume and David Easley and Jon Kleinberg and Robert Kleinberg and Eva Tardos

66. Online Node-weighted Steiner Tree and Related Problems

Joseph (Seffi) Naor and Debmalya Panigrahi and Mohit Singh

67. Welfare and Profit Maximization with Production Costs

Avrim Blum and Anupam Gupta and Yishay Mansour and Ankit Sharma

68. On the complexity of Commuting Local Hamiltonians, and tight conditions for Topological Order in such systems [arXiv]

Dorit Aharonov and Lior Eldar

69. Efficient Fully Homomorphic Encryption from (Standard) LWE [ePrint]

Zvika Brakerski and Vinod Vaikuntanathan

70. Testing and Reconstruction of Lipschitz Functions with Applications to Data Privacy [ECCC]

Madhav Jha and Sofya Raskhodnikova

71. Lexicographic Products and the Power of Non-Linear Network Coding

Anna Blasiak and Robert Kleinberg and Eyal Lubetzky

72. Efficient computation of approximate pure Nash equilibria in congestion games [arXiv]

Ioannis Caragiannis and Angelo Fanelli and Nick Gravin and Alexander Skopalik

73.  How to Garble Arithmetic Circuits

Benny Applebaum and Yuval Ishai and Eyal Kushilevitz

74. Rounding Semidefinite Programming Hierarchies via Global Correlation [arXiv]

Boaz Barak and Prasad Raghavendra and David Steurer

75. Efficient Reconstruction of Random Multilinear Formulas

Ankit Gupta and Neeraj Kayal and Satya Lokam

76. Markov Layout

Flavio Chierichetti and Ravi Kumar and Prabhakar Raghavan

77. (1+eps)-Approximate Sparse Recovery

Eric Price and David P. Woodruff

78. Quadratic Goldreich-Levin Theorems [arXiv]

Madhur Tulsiani and Julia Wolf

79. Maximizing Expected Utility for Stochastic Combinatorial Optimization Problems [arXiv]

Jian Li and Amol Deshpande

80. Stateless Cryptographic Protocols

Vipul Goyal and Hemanta K. Maji

81. Steiner Shallow-Light Trees are Exponentially Lighter than Spanning Ones

Michael Elkin and Shay Solomon

82. An algebraic proof of a robust social choice impossibility theorem

Dvir Falik and Ehud Friedgut

83. The Power of Linear Estimators [pdf]

Gregory Valiant and Paul Valiant

84. The Randomness Complexity of Parallel Repetition

Kai-Min Chung and Rafael Pass

85. The Complexity of Quantum States – a combinatorial approach

Dorit Aharonov and Itai Arad and Zeph Landau and Umesh Vazirani

STOC 2011 Accepted Papers (with pdf files)

  1. Quantum One-Way Communication can be Exponentially Stronger Than Classical Communication Bo’az Klartag and Oded Regev [arXiv]
  2. Multicut is FPT Nicolas Bousquet and Jean Daligault and Stephan Thomasse [arXiv]
  3. Pareto Optimal Solutions for Smoothed Analysts Ankur Moitra and Ryan O’Donnell [arXiv]
  4. An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance Amit Chakrabarti and Oded Regev [arXiv]
  5. Constant Round Non-Malleable Protocols using One Way Functions Vipul Goyal [ePrint]
  6. Fixed-parameter tractability of multicut parameterized by the size of the cutset Daniel Marx and Igor Razgon [arXiv]
  7. Secure Computation with Information Leaking to an Adversary Miklos Ajtai
  8. Optimal Constant-Time Approximation Algorithms and (Unconditional) Inapproximability Results for Every Bounded-Degree CSP Yuichi Yoshida [ECCC]
  9. Near-Optimal Private Approximation Protocols via a Black-Box Transformation David P. Woodruff
  10. Cover times, blanket times, and majorizing measures Jian Ding and James R. Lee and Yuval Peres [arXiv]
  11. Breaking the $k^2$ barrier for explicit RIP matrices Jean Bourgain, S. J. Dilworth, Kevin Ford, Sergei Konyagin, Denka Kutzarova [pdf]
  12. Analyzing Network Coding Gossip Made Easy Bernhard Haeupler [arXiv]
  13. Deterministic Construction of a high dimensional $\ell_p$ section in $\ell_1^n$ for any $p<2$ Zohar S. Karnin [ECCC]
  14. Schaefer’s Theorem for Graphs Manuel Bodirsky and Michael Pinsker [arXiv]
  15. Tight Bounds for Parallel Randomized Load Balancing Christoph Lenzen and Roger Wattenhofer [pdf]
  16. Pseudorandom Generators for Group Products Michal Koucky and Prajakta Nimbhorkar and Pavel Pudlak [pdf]
  17. Contraction Decomposition in H-Minor-Free Graphs and Algorithmic Applications Erik Demaine and Mohammad Hajiaghayi and Ken-ichi Kawarabayashi
  18. Correlation testing for affine invariant properties on $\F_p^n$ in the high error regime Hamed Hatami and Shachar Lovett
  19. Every Property of Hyperfinite Graphs is Testable Ilan Newman and Christian Sohler
  20. Fast Moment Estimation in Data Streams in Optimal Space Daniel M. Kane and Jelani Nelson and Ely Porat and David P. Woodruff [arXiv]
  21. An Algorithm for the Graph Crossing Number Problem Julia Chuzhoy [arXiv]
  22. From Affine to Two-Source Extractors via Approximate Duality Eli Ben-Sasson, Noga Zewi [ECCC]
  23. On Optimal Single-Item Auctions Christos Papadimitriou and George Pierrakos [arXiv]
  24. Directed Spanners via Flow-Based Linear Programs Michael Dinitz and Robert Krauthgamer [arXiv]
  25. Mechanism design with uncertain inputs (to err is human, to forgive divine) Uriel Feige and Moshe Tennenholtz
  26. Santa Claus Schedules Jobs on Unrelated Machines Ola Svensson [arXiv]
  27. Rank Bounds for Design Matrices with Applications to Combinatorial Geometry and Locally Correctable Codes Boaz Barak and Zeev Dvir and Avi Wigderson and Amir Yehudayoff [ECCC]
  28. A simpler algorithm and shorter proof for the graph minor decomposition Ken-ichi Kawarabayashi and Paul Wollan
  29. Finding topological subgraphs is fixed-parameter tractable Martin Grohe and Ken-ichi Kawarabayashi and Daniel Marx and Paul Wollan [arXiv]
  30. Constant-Round Non-Malleable Commitments from Any One-Way Function Huijia Lin, Rafael Pass [ePrint]
  31. Privacy-preserving Statistical Estimation with Optimal Convergence Rates Adam Smith
  32. Learning Submodular Functions Maria Florina Balcan and Nicholas J. A. Harvey [arXiv]
  33. Pseudorandom Generators for Combinatorial Shapes Parikshit Gopalan and Raghu Meka and Omer Reingold and David Zuckerman [ECCC]
  34. NP-Hardness of Approximately Solving Linear Equations Over Reals Subhash Khot and Dana Moshkovitz [ECCC]
  35. Towards Coding for Maximum Errors in Interactive Communication Mark Braverman and Anup Rao [pdf]
  36. K-Median Clustering, Model-Based Compressive Sensing, and Sparse Recovery for Earth Mover Distance Piotr Indyk and Eric Price
  37. Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in Undirected Graphs Paul Christiano and Jonathan A. Kelner and Aleksander Madry and Daniel A. Spielman and Shang-Hua Teng [arXiv]
  38. A General Framework for Graph Sparsification Wai Shing Fung and Ramesh Hariharan and Nicholas J. A. Harvey and Debmalya Panigrahi
  39. Breaking O(n^{1/2})-approximation algorithms for the edge-disjoint paths problem Ken-ichi Kawarabayashi and Yusuke Kobayashi
  40. Linearizable Implementations Do Not Suffice for Randomized Distributed Computation Wojciech Golab and Lisa Higham and Philipp Woelfel
  41. Online Bipartite Matching with Unknown Distributions Chinmay Karande and Aranyak Mehta and Pushkar Tripathi
  42. Near-optimal distortion bounds for embedding doubling spaces into $L_1$ James R. Lee and Anastasios Sidiropoulos
  43. Mechanisms for (Mis)allocating Scientific Credit Jon Kleinberg and Sigal Oren
  44. Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes Chandra Chekuri and Jan Vondrak and Rico Zenklusen
  45. Improved Minimum Cuts and Maximum Flows in Undirected Planar Graphs Giuseppe F. Italiano, Yahav Nussbaum, Piotr Sankowski, and Christian Wulff-Nilsen
  46. An Impossibility Result for Truthful Combinatorial Auctions with Submodular Valuations Shahar Dobzinski [arXiv]
  47. Geometric Complexity Theory and Tensor Rank Peter Buergisser and Christian Ikenmeyer [arXiv]
  48. A quasipolynomial-time algorithm for the quantum separability problem Fernando Brandao and Matthias Christandl and Jon Yard
  49. A Full Derandomization of Schoening’s k-SAT Algorithm Robin A. Moser and Dominik Scheder [arXiv]
  50. Rank-1 Bimatrix Games: A Homeomorphism and a Polynomial Time Algorithm Bharat Adsul and Jugal Garg and Ruta Mehta and Milind Sohoni [arXiv]
  51. How to Leak on Key Updates Allison Lewko and Mark Lewko and Brent Waters
  52. Separating Succinct Non-Interactive Arguments From All Falsifiable Assumptions Craig Gentry and Daniel Wichs [ePrint]
  53. Social Networks Spread Rumors in Sublogarithmic Time Benjamin Doerr and Mahmoud Fouz and Tobias Friedrich
  54. High-rate codes with sublinear-time decoding Swastik Kopparty and Shubhangi Saraf and Sergey Yekhanin [ECCC]
  55. The Computational Complexity of Linear Optics Scott Aaronson and Alex Arkhipov [arXiv]
  56. Dueling algorithms Nicole Immorlica and Adam Tauman Kalai and Brendan Lucier and Ankur Moitra and Andrew Postlewaite and Moshe Tennenholtz [arXiv]
  57. Blackbox identity testing for bounded top fanin depth-3 circuits: the field doesn’t matter Nitin Saxena and C. Seshadhri [ECCC]
  58. Don’t Rush into a Union: Take Time to Find Your Roots Mihai Patrascu and Mikkel Thorup
  59. From Convex Optimization to Randomized Mechanisms: Toward Optimal Combinatorial Auctions for Submodular Bidders Shaddin Dughmi and Tim Roughgarden and Qiqi Yan
  60. Privately Releasing Conjunctions and the Statistical Query Barrier Anupam Gupta and Moritz Hardt and Aaron Roth and Jonathan Ullman [arXiv]
  61. Optimal Path Search in Small Worlds: Dimension Matters George Giakkoupis and Nicolas Schabanel
  62. Distributed Verification and Hardness of Distributed Approximation Atish Das Sarma and Stephan Holzer and Liah Kor and Amos Korman and Danupon Nanongkai and Gopal Pandurangan and David Peleg and Roger Wattenhofer [arXiv]
  63. Parallel Repetition of Entangled Games Julia Kempe and Thomas Vidick [arXiv]
  64. Subspace Embeddings for the L_1-norm with Applications Christian Sohler and David Woodruff
  65. A Unified Framework for Approximating and Clustering Data Dan Feldman and Michael Langberg
  66. The Equivalence of the Random Oracle Model and the Ideal Cipher Model, Revisited Thomas Holenstein and Robin Kunzler and Stefano Tessaro [arXiv]
  67. Limits of Provable Security From Standard Assumptions Rafael Pass
  68. Optimal Auctions with Correlated Bidders are Easy Shahar Dobzinski and Hu Fu and Robert Kleinberg [arXiv]
  69. Strong Direct Product Theorems for Quantum Communication and Query Complexity Alexander A. Sherstov [arXiv]
  70. Inner Product Spaces for MinSum Coordination Mechanisms Richard Cole and Jose R. Correa and Vasilis Gkatzelis and Vahab Mirrokni and Neil Olver [arXiv]
  71. The Topology of Wireless Communication Erez Kantor and Zvi Lotker and Merav Parter and David Peleg
  72. An LLL-Reduction Algorithm with Quasi-linear Time Complexity Andrew Novocin and Damien Stehle and Gilles Villard [pdf]
  73. From Low-Distortion Norm Embeddings to Explicit Uncertainty Relations and Efficient Information Locking Omar Fawzi and Patrick Hayden and Pranab Sen [arXiv]
  74. The Power of Simple Tabulation Hashing Mihai Patrascu and Mikkel Thorup [arXiv]
  75. Subexponential lower bounds for randomized pivoting rules for the simplex algorithm Oliver Friedmann and Thomas Dueholm Hansen and Uri Zwick [pdf]
  76. Almost Settling the Hardness of Noncommutative Determinant Steve Chien and Prahladh Harsha and Alistair Sinclair and Srikanth Srinivasan [arXiv]
  77. Approximate Polytope Membership Queries Sunil Arya and Guilherme D. da Fonseca and David M. Mount [pdf]
  78. Exact Algorithms for Solving Stochastic Games Kristoffer Arnsfelt Hansen and Michal Koucky and Niels Lauritzen and Peter Bro Miltersen and Elias P. Tsigaridas
  79. Online Bipartite Matching with Random Arrivals: A Strongly Factor Revealing LP Approach Mohammad Mahdian and Qiqi Yan
  80. Estimating the unseen: an n/log(n)-sample estimator for entropy, support size, and other distribution properties, with a proof of optimality via two new central limit theorems Gregory Valiant and Paul Valiant
  81. Almost Tight Bounds for Reordering Buffer Management Anna Adamaszek and Artur Czumaj and Matthias Englert and Harald Raecke
  82. Black-Box Identity Testing of Depth-4 Multilinear Circuits Shubhangi Saraf and Ilya Volkovich
  83. Moser and Tardos meet Lovasz Kashyap Kolipaka and Mario Szegedy
  84. On the Complexity of Powering in Finite Fields Swastik Kopparty

FOCS 2010 Accepted Papers (with pdf files)

FOCS 2010 accepted paper list is here and list with abstracts is here. Following are PDF pointers to online versions.

  1. Settling the Polynomial Learnability of Mixtures of Gaussians [arXiv]
    Authors: Ankur Moitra (MIT) and Gregory Valiant (UC Berkeley)
  2. Solving linear systems through nested dissection [pdf]
    Authors: Noga Alon (Tel Aviv University) Raphael Yuster (University of Haifa)
  3. Improved Bounds for Geometric Permutations [arXiv]
    Authors: Natan Rubin, Haim Kaplan and Micha Sharir (Tel Aviv University)
  4. Constructive Algorithms for Discrepancy Minimization [arXiv]
    Authors: Nikhil Bansal (IBM Research)
  5. An efficient test for product states, with applications to quantum Merlin-Arthur games [arXiv]
    Authors:Aram W. Harrow: Department of Mathematics, University of Bristol & Departmenty of Computer Science and Engineering, University of Washington and Ashley Montanaro: Department of Computer Science, University of Bristol and Department of Applied Mathematics and Theoretical Physics, University of Cambridge
  6. Replacement Paths via Fast Matrix Multiplication [pdf]
    Authors: Oren Weimann (Weizmann Institute of Science) Raphael Yuster (University of Haifa)
  7. Logspace Versions of the Theorems of Bodlaender and Courcelle [ECCC]
    Authors: Michael Elberfeld, Andreas Jakoby, Till Tantau, Institute of Theoretical Computer Science, University of Lubeck, Germany.
  8. Impossibility of Differentially Private Universally Optimal Mechanisms [arXiv]
    Authors : Kobbi Nissim (Microsoft AI, Israel, and Dept. of Computer Science, Ben-Gurion University) Hai Brenner (Dept. of Mathematics, Ben-Gurion University)
  9. Determinant Sums for Undirected Hamiltonicity [arXiv]
    Author: Andreas Bjorklund, Lund University, Department of Computer Science, P.O.Box 118, SE-22100 Lund, Sweden
  10. A non-linear lower bound for planar epsilon-nets [pdf]
    Author: Noga Alon, Tel Aviv University and IAS, Princeton
  11. Pseudorandom generators for CC_0[p] and the Fourier spectrum of low-degree polynomials over finite fields [ECCC]
    Authors: Shachar Lovett, The Weizmann Institute of Science, Partha Mukhopadhyay, Technion – Israel Institute of Technology, Amir Shpilka, Technion – Israel Institute of Technology
  12. A lower bound for dynamic approximate membership data structures [ECCC]
    Authors: Shachar Lovett and Ely Porat
  13. A Decidable Dichotomy Theorem on Directed Graph Homomorphisms with Non-negative Weights [pdf]
    Authors: Jin-Yi Cai: University of Wisconsin – Madison Xi Chen: University of Southern California
  14. The Geometry of Manipulation – a Quantitative Proof of the Gibbard Satterthwaite Theorem [arXiv]
    Authors: Marcus Isaksson and Guy Kindler and Elchanan Mossel
  15. Optimal Testing of Reed-Muller Codes [ECCC]
    Authors: Arnab Bhattacharyya (MIT) Swastik Kopparty (MIT) Grant Schoenebeck (UC Berkeley) Madhu Sudan (Microsoft Research New England) David Zuckerman (UT Austin)
  16. Pseudorandom generators for regular branching programs. [ECCC]
    Authors: Mark Braverman (MSR New England and University of Toronto), Anup Rao (University of Washington), Ran Raz (Weizmann Institute of Science) and Amir Yehudayoff (IAS and Technion)
  17. Local list decoding with a constant number of queries [ECCC]
    Authors: Avraham Ben-Aroya and Klim Efremenko and Amnon Ta-Shma
  18. New Constructive Aspects of the Lovasz Local Lemma [arXiv]
    Authors: Bernhard Haeupler (MIT) Barna Saha (University of Maryland) and Aravind Srinivasan (University of Maryland)
  19. Matching vector codes [html]
    Authors: Zeev Dvir, Princeton University Parikshit Gopalan, Microsoft Research Sergey Yekhanin, Microsoft Research
  20. Approximation Algorithms for the Edge-Disjoint Paths Problem via Raecke Decompositions
    Author: Matthew Andrews, Alcatel-Lucent Bell Laboratories, 600-700 Mountain Avenue, Murray Hill, NJ 07974
  21. The complexity of distributions [pdf]
    Author: Emanuele Viola, Northeastern University
  22. All-Pairs Shortest Paths in $O(n^2)$ Time With High Probability [video]
    Authors: Yuval Peres, Microsoft Research, Redmond, Dmitry Sotnikov, Tel Aviv University, Benny Sudakov, UCLA, Uri Zwick, Tel Aviv University
  23. Computational Transition at the Uniqueness Threshold [arXiv]
    Author: Allan Sly, Microsoft Research, Redmond
  24. Strong Fault-Tolerance for Self-Assembly with Fuzzy Temperature  [arXiv]
    Authors: David Doty, University of Western Ontario, Matthew J. Patitz, University of Texas — Pan American, Dustin Reishus, University of Southern California, Robert T. Schweller, University of Texas — Pan American, Scott M. Summers, University of Wisconsin — Platteville
  25. Subcubic Equivalences Between Path, Matrix, and Triangle Problems [pdf]
    Authors: Virginia Vassilevska Williams, UC Berkeley and Ryan Williams, IBM Almaden Research Center
  26. Minimum-Cost Network Design with (Dis)economies of Scale
    Authors: Matthew Andrews and Spyridon Antonakopoulos and Lisa Zhang, Bell Laboratories, 600-700 Mountain Avenue, Murray Hill, NJ 07974
  27. A Unified Framework for Testing Linear-Invariant Properties
    Authors: Arnab Bhattacharyya (MIT), Elena Grigorescu (MIT), Asaf Shapira (Georgia Tech)
  28. Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition [arXiv]
    Authors: Amit Chakrabarti, Dartmouth College, Graham Cormode, AT&T Labs — Research, Ranganath Kondapally, Dartmouth College, Andrew McGregor, University of Massachusetts, Amherst
  29. Optimal stochastic planarization [arXiv]
    Anastasios Sidiropoulos , Toyota Technological Institute at Chicago
  30. Bounds on Monotone Switching Networks for Directed Connectivity [arXiv]
    Author: Aaron Potechin, MIT
  31. A Fourier-analytic approach to Reed-Muller decoding [html]
    Parikshit Gopalan, Microsoft Research Silicon Valley.
  32. Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP [arXiv]
    Authors: Jin-Yi Cai, University of Wisconsin-Madison and Beijing University, Pinyan Lu, Microsoft Research Asia, and Mingji Xia, Institute of Software, Chinese Academy of Sciences
  33. Backyard Cuckoo Hashing: Constant Worst-Case Operations with a Succinct Representation [arXiv]
    Authors: Yuriy Arbitman and Moni Naor and Gil Segev, Weizmann Institute of Science.
  34. Vertex Sparsifiers and Abstract Rounding Algorithms [arXiv]
    Moses Charikar (Princeton University), Tom Leighton (MIT and Akamai Technologies, Inc), Shi Li (Princeton University), Ankur Moitra (MIT)
  35. Deciding first-order properties for sparse graphs [pdf]
    Authors: Zdenek Dvorak (Charles University, Prague), Daniel Kral (Charles University, Prague), Robin Thomas (Georgia Institute of Technology, Atlanta)
  36. Clustering with Spectral Norm and the k-means Algorithm [arXiv]
    Amit Kumar (IIT Delhi) and Ravindran Kannan (Microsoft Research India Lab, Bangalore)
  37. Testing Properties of Sparse Images [pdf]
    Authors: Dana Ron and Gilad Tsur, Department of Electrical Engineering – Systems, Tel-Aviv University.
  38. Frugal Mechanism Design via Spectral Techniques [arXiv]
    Authors: Ning Chen and Edith Elkind and Nick Gravin and Fedor Petrov
  39. A separator theorem in minor-closed classes
    Authors Ken-ichi Kawarabayashi (National Institute of Informatics, Japan) and Bruce Reed (McGill University, Canada, and Sophia Antipolis, France)
  40. On the Insecurity of Parallel Repetition for Leakage Resilience [pdf]
    Allison Lewko (University of Texas at Austin) and Brent Waters (University of Texas at Austin)
  41. Approaching optimality for solving SDD linear systems [pdf]
    Ioannis Koutis†, Gary L. Miller and Richard Peng, Computer Science Department, Carnegie Mellon University, Pittsburgh, PA 15213
  42. The subexponential upper bound for on-line chain partitioning problem
    Authors: Bart\l{}omiej Bosek – Jagiellonian University, Theoretical Computer Science, ul. prof. Stanis\l{}awa \L{}ojasiewicza 6, Krak\'{o}w 30-348, Poland and Tomasz Krawczyk – Jagiellonian University, Theoretical Computer Science, ul. prof. Stanis\l{}awa \L{}ojasiewicza 6, Krak\'{o}w 30-348, Poland.
  43. One Tree Suffices: A Simultaneous O(1)-Approximation for Single-Sink Buy-at-Bulk [arXiv]
    Authors: Ashish Goel (Stanford University) Ian Post (Stanford University)
  44. On the Queue Number of Planar Graphs [pdf]
    Authors: Giuseppe Di Battista, Roma Tre University, Italy, Fabrizio Frati, Roma Tre University, Italy, J\’anos Pach, EPFL Lausanne, Switzerland
  45. Cryptography Against Continuous Memory Attacks [ePrint]
    AUthors: Yevgeniy Dodis and Kristiyan Haralambiev and Adriana Lopez-Alt and Daniel Wich
  46. Hardness of Finding Independent Sets in Almost 3-Colorable Graphs
    Authors: Irit Dinur and Subhash Khot and Will Perkins and Muli Safra
  47. Min st-Cut Oracle for Planar Graphs with Near-Linear Preprocessing Time [arXiv]
    Authors: Glencora Borradaile: School of Electrical Engineering and Computer Science, Oregon State University; Piotr Sankowski: Institute of Informatics, University of Warsaw and Department of Computer and System Science, Sapienza University of Rome; Christian Wulff-Nilsen: Department of Computer Science, University of Copenhagen
  48. Codes for Computationally Simple Channels: Explicit Constructions with Optimal Rate [arXiv]
    Authors: Venkatesan Guruswami (Carnegie Mellon University) Adam Smith (Pennsylvania State University)
  49. Polynomial Learning of Distribution Families [arXiv]
    Mikhail Belkin (Ohio State University) and Kaushik Sinha (Ohio State University)
  50. Overcoming the Hole in the Bucket: Public-Key Cryptography Resilient to Continual Memory Leakage [ePrint]
    Authors: Zvika Brakerski and Yael Tauman Kalai and Jonathan Katz and Vinod Vaikuntanathan
  51. Sequential Rationality in Cryptographic Protocols [arXiv]
    Authors: Ronen Gradwohl, Kellogg School of Management, Northwestern University; Noam Livne, Weizmann Institute of Science; Alon Rosen, Herzliya IDC
  52. Dependent Randomized Rounding via Exchange Properties of Combinatorial Structures [pdf with different title]
    Authors: Chandra Chekuri Dept. of Computer Science, Univ. of Illinois; Jan Vondrak IBM Almaden Research Center; Rico Zenklusen Dept. of Mathematics, MIT;
  53. From Sylvester-Gallai Configurations to Rank Bounds: Improved Black-box Identity Test for Depth-3 Circuits [ECCC]
    Authors: Nitin Saxena, Hausdorff Center for Mathematics, Bonn; C. Seshadhri, IBM Almaden
  54. The Geometry of Scheduling [arXiv]
    Authors: Nikhil Bansal (IBM Research) and Kirk Pruhs (Univ. of Pittsburgh)
  55. Stability yields a PTAS for k-Median and k-Means Clustering [pdf]
    Authors: Pranjal Awasthi and Avrim Blum and Or Sheffet, Carnegie Mellon University
  56. Metric Extension Operators, Vertex Sparsifiers and Lipschitz Extendability
    Authors:Konstantin Makarychev (IBM Research) and Yury Makarychev (TTIC).
  57. Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity [arXiv]
    Authors: Alexandr Andoni (Princeton University & Center for Computational Intractability) Robert Krauthgamer (Weizmann Institute) Krzysztof Onak (Massachusetts Institute of Technology)
  58. Fast approximation algorithms for flow and cut-based problems in undirected graphs [pdf]
    Author: Aleksander Madry, MIT
  59. Efficient volume sampling for row/column subset selection [pdf]
    Amit Deshpande, Microsoft Research India and Luis Rademacher, Computer Science and Engineering, Ohio State University
  60. Position-Based Quantum Cryptography [arXiv]
    Authors: Nishanth Chandran (UCLA), Serge Fehr (CWI), Ran Gelles (UCLA), Vipul Goyal (Microsoft Research, India), Rafail Ostrovsky (UCLA)
  61. Estimating the longest increasing sequence in polylogarithmic time [pdf]
    Authors: Michael Saks, Rutgers University and C. Seshadhri, IBM Almaden
  62. The Monotone Complexity of k-Clique on Random Graphs [pdf]
    Author: Benjamin Rossman, MIT
  63. Frugal and Truthful Auctions for Vertex Covers, Flows, and Cuts [arXiv]
    Authors: David Kempe and Mahyar Salek and Cristopher Moore
  64. The Coin Problem, and Pseudorandomness for Branching Programs
    Authors: Joshua Brody and Elad Verbin
  65. Agnostically learning under permutation invariant distributions
    Author: Karl Wimmer (Duquesne University)
  66. Approximating Maximum Weight Matching in Near-linear Time [pdf]
    Ran Duan, University of Michigan and Seth Pettie, University of Michigan
  67. Bounded Independence Fools Degree-2 Threshold Functions [ECCC]
    Authors: Ilias Diakonikolas (Columbia), Daniel M. Kane (Harvard), Jelani Nelson (MIT)
  68. Boosting and Differential Privacy
    Authors: Cynthia Dwork (Microsoft Research), Guy Rothblum (Princeton University), Salil Vadhan (Harvard University
  69. Fighting Perebor: New and Improved Algorithms for Formula and QBF Satisfiability
    Author: Rahul Santhanam, University of Edinburgh
  70. Lower Bounds for Near Neighbor Search via Metric Expansion [arXiv]
    Authors: Rina Panigrahy (Microsoft Research Silicon Valley), Kunal Talwar (Microsoft Research Silicon Valley), Udi Wieder (Microsoft Research Silicon Valley)
  71. Black-Box Randomized Reductions in Algorithmic Mechanism Design [pdf]
    Authors: Shaddin Dughmi and Tim Roughgarden (Stanford University)
  72. Pure and Bayes-Nash Price of Anarchy for Generalized Second Price Auction [pdf]
    Authors: Renato Paes Leme and Eva Tardos (Cornell)
  73. Learning Convex Concepts from Gaussian Distributions with PCA [pdf]
    Authors: Santosh Vempala (Georgia Tech)
  74. Sublinear Optimization for Machine Learning [pdf]
    Authors: Kenneth L. Clarkson and Elad Hazan and David P. Woodruff (IBM Almaden Research Center)
  75. The Limits of Two-Party Differential Privacy [html]
    Authors: Andrew McGregor (University of Massachusetts, Amherst) Ilya Mironov (Microsoft Research Silicon Valley) Toniann Pitassi (University of Toronto) Omer Reingold (Microsoft Research Silicon Valley) Kunal Talwar (Microsoft Research Silicon Valley) Salil Vadhan (Harvard)
  76. Distance Oracles Beyond the Thorup-Zwick Bound
    Authors: Mihai Patrascu – AT&T Labs; Liam Roditty – Bar Ilan University
  77. A Multiplicative Weights Mechanism for Interactive Privacy-Preserving Data Analysis
    Authors: Moritz Hardt (Princeton University); Guy Rothblum (Princeton University)
  78. Subexponential Algorithms for Unique Games and Related problems [pdf]
    Authors: Sanjeev Arora: Princeton University and Center for Computational Intractability; Boaz Barak: Microsoft Research and Princeton University; David Steurer: Princeton University and Center for Computational Intractability.
  79. Budget Feasible Mechanisms [arXiv]
    Author: Yaron Singer, UC Berkeley
  80. Black-Box, Round-Efficient Secure Computation via Non-Malleability Amplification
    Hoeteck Wee (Queens College, CUNY)
  81. On the Computational Complexity of Coin Flipping [pdf]
    Authors: Hemanta K. Maji (UIUC) Manoj Prabhakaran (UIUC) Amit Sahai (UCLA)
  82. Adaptive Hardness and Composable Security in the Plain Model from Standard Assumptions
    Authors: Ran Canetti, Huijia Lin, and Rafael Pass.

STOC 2010 Accepted Papers (with pdf files)

STOC 2010 accepted paper list is here.
As usual (ICS 2010 pdf files, FOCS 2009 pdf files), I am collecting pointers to online versions.
  • Oblivious RAMs without Cryptographic Assumptions [ECCC]
    Miklos Ajtai (IBM Almaden Research Center)
  • Improved Algorithms for Computing Fisher’s Market Clearing Prices
    James B. Orlin (MIT)
  • Optimal Bounds for Sign-Representing the Intersection of Two Halfspaces by Polynomials [arXiv]
    Alexander A. Sherstov (Microsoft Research)
  • Augmenting undirected node-connectivity by one [pdf]
    Laszlo A. Vegh (MTA-ELTE Egervary Research Group and Department of Operations Research, Eotvos University)
  • Solving Polynomial Equations in Smoothed Polynomial Time and a Near Solution to Smale’s 17th Problem ([arXiv] with a different title)
    Peter Buergisser (University of Paderborn) and Felipe Cucker (City University of Hong Kong)
  • Matroid Matching: the Power of Local Search [IBM TechReport]
    Jon Lee (IBM TJ Watson Research Center), Maxim Sviridenko (IBM TJ Watson Research Center) and Jan Vondrak (IBM Almaden Research Center)
  • Tensor-Rank and Lower Bounds for Arithmetic Formulas [pdf]
    Ran Raz (Weizmann Institute)
  • Towards Polynomial Lower Bounds for Dynamic Problems [pdf]
    Mihai Patrascu (AT&T Labs)
  • Improving Exhaustive Search Implies Superpolynomial Lower Bounds [pdf]
    Ryan Williams (IBM Almaden Research Center)
  • An Optimal Ancestry Scheme and Small Universal Posets [pdf]
    Pierre Fraigniaud and Amos Korman (CNRS and Univ. Paris Diderot)
  • Tractable hypergraph properties for constraint satisfaction and conjunctive queries [arXiv]
    Dániel Marx (Tel Aviv University)
  • On the searchability of small-world networks with arbitrary underlying structure [pdf]
    Pierre Fraigniaud (CNRS and Univ. Paris Diderot) and George Giakkoupis (Univ. Paris Diderot)
  • Satisfiability Allows No Nontrivial Sparsification Unless The Polynomial-Time Hierarchy Collapses [ECCC]
    Holger Dell (Humboldt University of Berlin) and Dieter van Melkebeek (University of Wisconsin-Madison)
  • A shorter proof of the Graph Minor Algorithm – The Unique Linkage Theorem
    Ken-ichi Kawarabayashi (National Institute of Informatics, Tokyo) and Paul Wollan (University of Rome, La Sapienza)
  • Pseudorandom Generators for Polynomial Threshold Functions [arXiv]
    Raghu Meka and David Zuckerman (University of Texas at Austin)
  • How to Compress Interactive Communication [pdf]
    Boaz Barak (Princeton University), Mark Braverman (Microsoft Research New England), Xi Chen (University of Southern California) and Anup Rao (University of Washington)
  • The maximum multiflow problems with bounded fractionality [pdf]
    Hiroshi Hirai (Reseach Institute for Mathematical Sciences, Kyoto University)
  • Measuring Independence of Datasets [arXiv]
    Vladimir Braverman and Rafail Ostrovsky (UCLA)
  • On the Geometry of Differential Privacy [arXiv]
    Moritz Hardt (Princeton University) and Kunal Talwar (Microsoft Research)
  • An Invariance Principle For Polytopes [arXiv]
    Prahladh Harsha (Tata Institute of Fundamental Research), Adam Klivans (UT-Austin) and Raghu Meka (UT-Austin)
  • Perfect Matchings in O(n log n) Time in Regular Bipartite Graphs [arXiv]
    Ashish Goel (Stanford University and Twitter), Michael Kapralov (Stanford University) and Sanjeev Khanna (University of Pennsylvania)
  • A Quantum Lovasz Local Lemma [arXiv]
    Andris Ambainis (University of Latvia), Julia Kempe (Tel Aviv University) and Or Sattath (Hebrew University and Tel Aviv University)
  • Bayesian Algorithmic Mechanism Design [arXiv]
    Jason D. Hartline (Northwestern University) and Brendan Lucier (University of Toronto)
  • A Strong Direct Product Theorem for Disjointness [arXiv]
    Hartmut Klauck (Centre for Quantum Technologies, Singapore)
  • Recognizing well-parenthesized expressions in the streaming model [arXiv]
    Frederic Magniez (LRI, Univ. Paris-Sud, CNRS), Claire Mathieu (Brown University) and Ashwin Nayak (U. Waterloo and Perimeter Institute)
  • Conditional Hardness of Precedence Constrained Scheduling on Identical Machines [pdf]
    Ola Svensson (KTH – Royal Institute of Technology, Stockholm)
  • An Improved LP-based Approximation for Steiner Tree [html] [pdf]
    Jaroslaw Byrka (EPFL, Lausanne), Fabrizio Grandoni (Universita di Roma Tor Vergata), Thomas Rothvoss (EPFL, Lausanne) and Laura Sanita (EPFL, Lausanne)
  • On the Complexity of #CSP [arXiv]
    Martin Dyer and David Richerby (University of Leeds)
  • Approximate Sparse Recovery: Optimizing Time and Measurements [arXiv]
    Anna Gilbert (University of Michigan) Yi Li (University of Michigan), Ely Porat (Bar Ilan University) and Martin Strauss (University of Michigan)
  • On the Hardness of the Noncommutative Determinant [arXiv]
    Vikraman Arvind and Srikanth Srinivasan (Institute of Mathematical Sciences, Chennai)
  • A Deterministic Single Exponential Time Algorithm for Most Lattice Problems based on Voronoi Cell Computations [ECCC]
    Daniele Micciancio and Panagiotis Voulgaris (UCSD)
  • Combinatorial approach to the interpolation method and scaling limits in sparse random graphs [arXiv]
    Mohsen Bayati (Stanford), David Gamarnik (MIT) and Prasad Tetali (Georgia Institute of Technology)
  • Complexity Theory for Operators in Analysis [pdf]
    Akitoshi Kawamura and Stephen Cook (University of Toronto)
  • The Median Mechanism: Interactive and Efficient Privacy with Multiple Queries [pdf]
    Aaron Roth (CMU) and Tim Roughgarden (Stanford)
  • On the Round Complexity of Covert Computation [pdf]
    Vipul Goyal (MSR India) and Abhishek Jain (UCLA)
  • Public-Key Cryptography from Different Assumptions [pdf]
    Benny Applebaum (Weizmann Institute of Science), Boaz Barak (Princeton University) and Avi Wigderson (Institute for Advanced Study)
  • On the List-Decodability of Random Linear Codes [arXiv]
    Venkatesan Guruswami (Carnegie Mellon University), Johan Håstad (KTH – Royal Institute of Technology) and Swastik Koppart (Massachusetts Institute of Technology)
  • Hardness Amplification in Proof Complexity [arXiv]
    Paul Beame (University of Washington), Trinh Huynh (University of Washington) and Toniann Pitassi (University of Toronto)
  • Non-commutative circuits and the sum-of-squares problem [pdf]
    Pavel Hrubes (Princeton University), Avi Wigderson (Institute for Advanced Study) and Amir Yehudayoff (Institute for Advanced Study)
  • Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms [abstract] [arXiv]
    Aleksander Madry (MIT)
  • Efficiency Improvements in Constructing Pseudorandom Generators from One-Way Functions [pdf]
    Iftach Haitner (Microsoft Research New England), Omer Reingold (Microsoft Research Silicon Valley and Weizmann Institute of Science) and Salil Vadhan (Harvard University)
  • Load balancing and orientability thresholds for random hypergraphs
    Pu Gao and Nicholas Wormald (University of Waterloo)
  • Bounding the average sensitivity and noise sensitivity of polynomial threshold functions (merge of [arXiv] and [arXiv])
    Ilias Diakonikolas (Columbia University), Prahladh Harsha (Tata Institute of Fundamental Research), Adam R. Klivans (University of Texas), Raghu Meka (University of Texas), Prasad Raghavendra (Microsoft Research New England), Rocco A. Servedio (Columbia University) and Li-Yang Tan (Columbia University)
  • Graph Expansion and the Unique Games Conjecture [pdf]
    Prasad Raghavendra (Microsoft Research New England) and David Steurer (Princeton University)
  • Approximations for the Isoperimetric and Spectral Profile of Graphs and Related Parameters [pdf]
    Prasad Raghavendra (Microsoft Research New England), David Steurer (Princeton University) and Prasad Tetali (Georgia Tech)
  • Detecting High Log-Densities — an $O(n^{1/4})$ Approximation for Densest $k$-Subgraph [arXiv]
    Aditya Bhaskara (Princeton University), Moses Charikar (Princeton University), Eden Chlamtac (Weizmann Institute of Science), Uriel Feige (Weizmann Institute of Science) and Aravindan Vijayaraghavan (Princeton University)
  • Near-optimal extractors against quantum storage [arXiv]
    Anindya De and Thomas Vidick (UC Berkeley)
  • On the Complexity of Circuit Satisfiability [pdf] [video]
    Ramamohan Paturi (University of California, San Diego) and Pavel Pudl\’ak (Mathematical Institute of the Czech Academy of Sciences)
  • Multi-parameter mechanism design and sequential posted pricing [arXiv]
    Shuchi Chawla (University of Wisconsin-Madison), Jason Hartline (Northwestern University), David Malec (University of Wisconsin-Madison) and Balasubramanian Sivan (University of Wisconsin-Madison)
  • Subgraph Sparsification and Nearly Optimal Ultrasparsifiers [arXiv]
    Alexandra Kolla (Institute for Advanced Study), Yury Makarychev (Toyota Technological Institute at Chicago), Amin Saberi (Stanford University) and Shang-Hua Teng (University of Southern California)
  • Bilipschitz snowflakes, metrics of negative type, and PSD flows
    James R. Lee and Mohammad Moharrami (University of Washington)
  • The Limits of Buffering: A Tight Lower Bound for Dynamic Membership in the External Memory Model [pdf]
    Elad Verbin (ITCS, Tsinghua University) and Qin Zhang (Hong Kong University of Science and Technology)
  • Optimal Homologous Cycles, Total Unimodularity, and Linear Programming [arXiv]
    Tamal K. Dey (Ohio State University), Anil N. Hirani (University of Illinois at Urbana-Champaign) and Bala Krishnamoorthy (Washington State University)
  • Distributed Computation in Dynamic Networks [pdf]
    Fabian Kuhn (University of Lugano), Nancy Lynch (MIT) and Rotem Oshman (MIT)
  • Maintaining a Large Matching or a Small Vertex Cover [html]
    Krzysztof Onak (MIT) and Ronitt Rubinfeld (MIT and Tel Aviv University)
  • Almost Tight Bounds for Rumour Spreading with Conductance [pdf]
    Flavio Chierichetti, Silvio Lattanzi and Alessandro Panconesi (Sapienza University)
  • Changing Base without Losing Space ([pdf] with a different title)
    Yevgeniy Dodis (New York University) and Mihai Patrascu (AT&T Labs) and Mikkel Thorup (AT&T Labs)

Open Problems from FOCS 2009

Here are some open problems (that interest me) from FOCS 2009. If you want to share an open problem, please leave a comment.

Starting with my paper…….

1) Reducibility Among Fractional Stability Problems [pdf]

Shiva Kintali, Laura Poplawski, Rajmohan Rajaraman, Ravi Sundaram and Shang-Hua Teng.

Summary : We resolve the computational complexity of a number of outstanding open problems with practical applications and introduce a simple PPAD-complete game (the preference game). Here is the list of problems we show to be PPAD-complete, along with the domains of practical significance:  1) Fractional Stable Paths Problem (FSPP) – Internet routing;  2) Core of Balanced Games – Economics and Game theory;  3) Scarf’s Lemma – Combinatorics;  4) Hypergraph Matching – Social Choice and Preference Systems;  5) Fractional Bounded Budget Connection Games (FBBC) – Social networks; and 6) Strong Fractional Kernel – Graph Theory.

Open Problems : The complexity of Discrete Ham Sandwich Problem and Necklace Splitting Problem are open. These are shown to be in PPAD by Papadimitiou in 1994.

2) Linear systems over composite moduli [pdf]

Arkadev Chattopadhyay and Avi Wigderson.

Summary and Open Problems : Dick Lipton already summarized their result along with open problems.

3) Regularity Lemmas and Combinatorial Algorithms [pdf]

Nikhil Bansal, Ryan Williams

Summary : This paper presents new combinatorial algorithms for Boolean matrix multiplication (BMM) and preprocessing a graph to answer independent set queries. The authors give the first asymptotic improvements on “combinatorial” algorithms for dense BMM in many years, improving on the Four Russians O(n^3/(log^{2}n)) bound. Their use of Triangle removal lemma and Regularity lemma are particularly interesting.

Open Problems : Ryan mentioned the following open problems in his talk : (1) Can one construct a Weak Regular partition in O(n^{2.9}) time, deterministically ? (2) Can their techniques be applied to All Pairs Shortest Paths Problems ? (3) is there a Regularity concept that is better suited for Matrix Multiplication ?

4) Improved Approximation Algorithms for PRIZE-COLLECTING STEINER TREE and TSP [pdf]

Aaron Archer, MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Howard Karloff

Summary : They give a factor 1.990283 approximation algorithm for Prize-collecting TSP. This is the first result to break the barrier of 2 improving the primal-dual algorithm  of Goemans and Williamson. Recently Goemans, presented a 1.91457-approximation algorithm for the prize-collecting travelling salesman problem.

Open Problem : Obvious open problem is to improve this approximation factor.

5) Blackbox Polynomial Identity Testing for Depth 3 Circuits [pdf]

Neeraj Kayal and Shubhangi Saraf.

Open Problems : This paper has a well-written open problems section with specific open problems. If you are interested in polynomial identity testing, I encourage you to read them.