Accepted Papers at FOCS 2010

Eighty-two out of 270. Also with abstracts.

If you know links to where some of the papers are available online, I will try to add them. (But I will be offline most of next week.)

Thanks to all who submitted and all who reviewed.

14 thoughts on “Accepted Papers at FOCS 2010

  1. Here are the first 20:

    1. Settling the Polynomial Learnability of Mixtures of Gaussians
    http://arxiv.org/abs/1004.4223
    2. Solving linear systems through nested dissection
    http://www.cs.tau.ac.il/~nogaa/PDFS/sparsesystem.pdf
    3. Improved Bounds for Geometric Permutations
    not online
    4. Constructive Algorithms for Discrepancy Minimization
    http://arxiv.org/abs/1002.2259
    5. An efficient test for product states, with applications to quantum Merlin-Arthur games
    http://arxiv.org/abs/1001.0017
    6. Replacement Paths via Fast Matrix Multiplication
    http://www.wisdom.weizmann.ac.il/~oweimann/Publications/replacement.pdf
    7. Logspace Versions of the Theorems of Bodlaender and Courcelle
    http://eccc.hpi-web.de/report/2010/062/
    8. Impossibility of Differentially Private Universally Optimal Mechanisms
    not online
    9. Determinant Sums for Undirected Hamiltonicity
    not online
    10. A non-linear lower bound for planar epsilon-nets
    http://www.math.tau.ac.il/~nogaa/PDFS/epsnet3.pdf
    11. Pseudorandom generators for CC_0[p] and the Fourier spectrum of low-degree polynomials over finite fields
    http://eccc.hpi-web.de/report/2010/033
    12. A lower bound for dynamic approximate membership data structures
    http://www.eccc.uni-trier.de/report/2010/087/
    13. A Decidable Dichotomy Theorem on Directed Graph Homomorphisms with Non-negative Weights
    http://www-rcf.usc.edu/~chen73/Homomorphism.pdf
    14. The Geometry of Manipulation – a Quantitative Proof of the Gibbard Satterthwaite Theorem
    http://arxiv.org/abs/0911.0517
    15. Optimal Testing of Reed-Muller Codes
    http://eccc.hpi-web.de/report/2009/086/
    16. Pseudorandom Generators for Regular Branching Programs
    http://eccc.hpi-web.de/report/2010/035/
    17. Local list decoding with a constant number of queries
    http://eccc.hpi-web.de/report/2010/047/
    18. New Constructive Aspects of the Lovasz Local Lemma
    http://arxiv.org/abs/1001.1231
    19. Matching Vector Codes
    http://www.eccc.uni-trier.de/report/2010/012/
    20. Approximation Algorithms for the Edge-Disjoint Paths Problem via Raecke Decompositions
    not online

  2. Here are the first twenty papers:

    1. Settling the Polynomial Learnability of Mixtures of Gaussians
    http://arxiv.org/abs/1004.4223
    2. Solving linear systems through nested dissection
    http://www.cs.tau.ac.il/~nogaa/PDFS/sparsesystem.pdf
    3. Improved Bounds for Geometric Permutations
    not online
    4. Constructive Algorithms for Discrepancy Minimization
    http://arxiv.org/abs/1002.2259
    5. An efficient test for product states, with applications to quantum Merlin-Arthur games
    http://arxiv.org/abs/1001.0017
    6. Replacement Paths via Fast Matrix Multiplication
    http://www.wisdom.weizmann.ac.il/~oweimann/Publications/replacement.pdf
    7. Logspace Versions of the Theorems of Bodlaender and Courcelle
    http://eccc.hpi-web.de/report/2010/062/
    8. Impossibility of Differentially Private Universally Optimal Mechanisms
    not online
    9. Determinant Sums for Undirected Hamiltonicity
    not online
    10. A non-linear lower bound for planar epsilon-nets
    http://www.math.tau.ac.il/~nogaa/PDFS/epsnet3.pdf
    11. Pseudorandom generators for CC_0[p] and the Fourier spectrum of low-degree polynomials over finite fields
    http://eccc.hpi-web.de/report/2010/033
    12. A lower bound for dynamic approximate membership data structures
    http://www.eccc.uni-trier.de/report/2010/087/
    13. A Decidable Dichotomy Theorem on Directed Graph Homomorphisms with Non-negative Weights
    http://www-rcf.usc.edu/~chen73/Homomorphism.pdf
    14. The Geometry of Manipulation – a Quantitative Proof of the Gibbard Satterthwaite Theorem
    http://arxiv.org/abs/0911.0517
    15. Optimal Testing of Reed-Muller Codes
    http://eccc.hpi-web.de/report/2009/086/
    16. Pseudorandom Generators for Regular Branching Programs
    http://eccc.hpi-web.de/report/2010/035/
    17. Local list decoding with a constant number of queries
    http://eccc.hpi-web.de/report/2010/047/
    18. New Constructive Aspects of the Lovasz Local Lemma
    http://arxiv.org/abs/1001.1231
    19. Matching Vector Codes
    http://www.eccc.uni-trier.de/report/2010/012/
    20. Approximation Algorithms for the Edge-Disjoint Paths Problem via Raecke Decompositions
    not online

  3. 1. Settling the Polynomial Learnability of Mixtures of Gaussians
    http://arxiv.org/abs/1004.4223
    2. Solving linear systems through nested dissection
    http://www.cs.tau.ac.il/~nogaa/PDFS/sparsesystem.pdf
    3. Improved Bounds for Geometric Permutations
    not online
    4. Constructive Algorithms for Discrepancy Minimization
    http://arxiv.org/abs/1002.2259
    5. An efficient test for product states, with applications to quantum Merlin-Arthur games
    http://arxiv.org/abs/1001.0017

  4. 6. Replacement Paths via Fast Matrix Multiplication
    http://www.wisdom.weizmann.ac.il/~oweimann/Publications/replacement.pdf
    7. Logspace Versions of the Theorems of Bodlaender and Courcelle
    http://eccc.hpi-web.de/report/2010/062/
    8. Impossibility of Differentially Private Universally Optimal Mechanisms
    not online
    9. Determinant Sums for Undirected Hamiltonicity
    not online
    10. A non-linear lower bound for planar epsilon-nets
    http://www.math.tau.ac.il/~nogaa/PDFS/epsnet3.pdf

  5. 11. Pseudorandom generators for CC_0[p] and the Fourier spectrum of low-degree polynomials over finite fields
    http://eccc.hpi-web.de/report/2010/033
    12. A lower bound for dynamic approximate membership data structures
    http://www.eccc.uni-trier.de/report/2010/087/
    13. A Decidable Dichotomy Theorem on Directed Graph Homomorphisms with Non-negative Weights
    http://www-rcf.usc.edu/~chen73/Homomorphism.pdf
    14. The Geometry of Manipulation – a Quantitative Proof of the Gibbard Satterthwaite Theorem
    http://arxiv.org/abs/0911.0517
    15. Optimal Testing of Reed-Muller Codes
    http://eccc.hpi-web.de/report/2009/086/

  6. 16. Pseudorandom Generators for Regular Branching Programs
    http://eccc.hpi-web.de/report/2010/035/
    17. Local list decoding with a constant number of queries
    http://eccc.hpi-web.de/report/2010/047/
    18. New Constructive Aspects of the Lovasz Local Lemma
    http://arxiv.org/abs/1001.1231
    19. Matching Vector Codes
    http://www.eccc.uni-trier.de/report/2010/012/
    20. Approximation Algorithms for the Edge-Disjoint Paths Problem via Raecke Decompositions
    not online

  7. 31. A Fourier-analytic approach to Reed-Muller decoding
    http://www.eccc.uni-trier.de/report/2009/037/
    32. Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP
    not online
    33. Backyard Cuckoo Hashing: Constant Worst-Case Operations with a Succinct Representation
    http://arxiv.org/abs/0912.5424
    34. Vertex Sparsifiers and Abstract Rounding Algorithms
    http://arxiv.org/abs/1006.4536
    35. Deciding first-order properties for sparse graphs
    http://iti.mff.cuni.cz/series/files/2009/iti484.pdf

  8. Pretty high acceptance rate and surprised at some of the exclusions (I mean I know of some of the submissions which did not make it through).

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