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

    Click to access 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

    Click to access 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

    Click to access 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

    Click to access 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

    Click to access 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

    Click to access 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

    Click to access 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

    Click to access 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. 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

    Click to access 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/

  4. 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

  5. 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

    Click to access iti484.pdf

  6. 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 )

Connecting to %s