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.

About these ads

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