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



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

15 thoughts on “FOCS 2011 Accepted Papers (with pdf files)

  1. Yet more of the same failed kind: choosing papers in fashionable areas. Rejecting good papers based on no grounds whatsoever. Committee members having to judge papers written by their colleagues, friends and students, while choosing between works in inapproximability, mechanism design and universal algebra (how professional!). We must move to journal submissions. This is just not working anymore.

    • Could you elaborate, instead of ranting?

      Could you give an example of some good papers rejected on no grounds whatsoever?

      Do you have any hint of improper behavior on the part of the committee?

      I am actually familiar with some of these papers, that I believe to be excellent. As examples, the papers on communication complexity, new results on graph minors and their algorithmic applications, and interesting new results on quantum computing are among the ones accepted (and of course none are in the subareas CS objected to.)

      We should in fact give more importance to journal submissions, but that does not justify denigrating the difficult work of your colleagues in the program committee, or to call them unethical.

  2. simonchicago,
    the complaint is not about the ethics of the committee, nor about some specific papers or subareas of CS, but about a conference that transformed into a contest of too broad scope (having to compare papers from completely different areas).

  3. Yes, being on a FOCS program committee is a difficult job because the scope is very broad. We do the best we can, but make mistakes. However, that is not a reason to narrow the conference scope. There are many more specialized conferences. As a member of the FOCS PC, I tried to support papers that are of the widest general interest to the TCS community, rather than having it be a contest at all. Really, our only responsibility (besides ethical behavior) is to assemble a program that will generate excitement among TCS researchers and make them want to attend, and inform them of the state-of-the-art in the TCS when they do. We are not trying to be impartial judges of quality.

    If anything, I think the complaint could be made that we become too narrow and compartmentalized over time, rather than too broad. Many areas have splintered away and no longer perceive themselves as having a home within
    the FOCS/STOC definition of TCS. We want to appeal to TCS researchers, but in some sense the FOCS/STOC program also defines who is a TCS researcher. I hope we didn’t lose too many this year!

    Russell Impagliazzo

  4. Two examples of bad scope extensions:
    * I think that sometimes a new problem gets presented at FOCS and STOC that is very nice but away from the field. This is good. Then follow-up papers that are not nearly as original and are still off-topic also get into FOCS/STOC. This can be bad. The follow-up papers should usually go to more appropriate conferences or journals. I don’t see any examples above.
    * It also happens that established authors who are used to sending everything to FOCS/STOC write a strong paper that really belongs in another field, but they send it here for their own reasons and we accept it because after all it is a strong paper. This may happen when a problem that originally had strong computational motivations becomes more and more mathematically motivated. I have not read more than the title, but the Grothendieck constant paper sounds like it could be of this type. It is not bad to accept such papers, but maybe we should be more disciplined and give preference to weaker papers with a better topic fit. In every case, this is a judgement call.

      • Thank you for pointing this out. I deliberately did not read more than the title because it is not polite to attack papers anonymously, and that was not my intention at all. I am sure that paper belongs.

      • To the anonymous below:

        Why do you say that you are sure that the paper “belongs” after admitting that you have not read it? This is the problem with conferences: PC members arguing for and against papers they have not read.

        To yeo harzog: most papers giving SDP-based algorithms introduce a new rounding technique. An old rounding technique would be dismissed as “the paper introduces no new results”. The fact that the paper introduces a new rounding technique does not automatically imply that it “belongs”. Like most papers on the list, it is a matter of taste.

  5. Another good example of a paper that one could have omitted:

    An algebraic proof of a robust social choice impossibility theorem

  6. One more paper that is nice but IMHO not good enough for STOC/FOCS: the paper “Algorithms for the Generalized Sorting Problem”

  7. It’s fine to have opinions and tastes about problems/papers. But some of the comments here are just dumb. The paper “Algorithms for the Generalized Sorting Problem” solves a >10 year old problem that many people have worked on. Why don’t you at least wait until the paper is available, before making such a comment. And while you are waiting, try to solve the problem and see if you can.

    BTW, I don’t think it is a question that the papers accepted “belong” or not. There are many rejected papers that also “belong”. How many of the accepted papers were rejected from STOC 11? I think a lot were, and the question is, is it a good use of the PC/community’s time to spend so much energy deciding which papers get presented six months before the others?

  8. Pingback: Maximum matching in general graphs « Chicken's Finite Playground

  9. R.I., I’d be wary of defining TCS researcher by FOCS/STOC program. For all you know, very little of that whatever has appeared there may remain of any consequence, if a certain equality is proved.
    Would that leave many/most TCS’ists searching for their homes then?

  10. Pingback: “Let’s enhance that” might work after all | cartesian product

  11. Pingback: Encouraged, Expected, and Enforced? « Windows On Theory

Leave a Reply

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

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

Google photo

You are commenting using your Google 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 )

Connecting to %s