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