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.
Recent Comments
non-theory
theory
Archives
- May 2013
- April 2013
- March 2013
- November 2012
- August 2012
- July 2012
- June 2012
- May 2012
- February 2012
- January 2012
- December 2011
- November 2011
- September 2011
- June 2011
- May 2011
- April 2011
- March 2011
- February 2011
- January 2011
- December 2010
- November 2010
- October 2010
- September 2010
- August 2010
- July 2010
- June 2010
- May 2010
- April 2010
- March 2010
- February 2010
- January 2010
- December 2009
- November 2009
- October 2009
- September 2009
- July 2009
- June 2009
- May 2009
- April 2009
- March 2009
- February 2009
- January 2009
- December 2008
- November 2008
- October 2008
- September 2008
- August 2008
- July 2008
- June 2008
- May 2008
- April 2008
- March 2008
- February 2008
- January 2008
- December 2007
- November 2007
- October 2007
- September 2007
- August 2007
- July 2007
- June 2007
- May 2007
- April 2007
- March 2007
- February 2007
- January 2007
- December 2006
- November 2006
- October 2006
- September 2006
- August 2006
- July 2006
- June 2006
- May 2006
- April 2006
- March 2006
a
Tags
Additive Combinatorics
Apple
Avi Wigderson
CCA security
circuit lower bounds
Conceptual contributions
cryptography
CS254 2010
eigenvalues
Expanders
Fields Medal
FOCS 2006
FOCS 2010
Hard-Core Sets
ICM 2006
Integrality gap
Leonid Levin
linear programming
Luby-Rackoff
maximum flow
Metric embeddings
Oded Goldreich
Proposition 8
pseudorandom function
Pseudorandomness
pseudorandom permutation
public-key encryption
quadratic residue
Random Oracle Model
Regularity Lemma
RSA
SAT
signature schemes
sparsest cut
Spectral partitioning
STOC and FOCS
Szemeredi Theorem
Tamar Ziegler
Terence Tao
things that are excellent
Tim Gowers
Turing Centennial
unique games
World Cup
Zero Knowledge
14 comments
Comments feed for this article
July 1, 2010 at 5:54 pm
Anonymous
Testing:
1. Settling the Polynomial Learnability of Mixtures of Gaussians
http://arxiv.org/abs/1004.4223
July 1, 2010 at 5:55 pm
Anonymous
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
July 1, 2010 at 5:57 pm
Anonymous
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
July 1, 2010 at 6:06 pm
Anonymous
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
July 1, 2010 at 6:07 pm
Anonymous
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
July 1, 2010 at 6:08 pm
Anonymous
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/
July 1, 2010 at 6:09 pm
Anonymous
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
July 1, 2010 at 6:30 pm
Anonymous
21. The complexity of distributions
not online
22. All-Pairs Shortest Paths in $O(n^2)$ Time With High Probability
not online
23. Computational Transition at the Uniqueness Threshold
http://arxiv.org/abs/1005.5584
24. Strong Fault-Tolerance for Self-Assembly with Fuzzy Temperature
http://arxiv.org/abs/1004.0995
25. Subcubic Equivalences Between Path, Matrix, and Triangle Problems
http://www.cs.cmu.edu/~ryanw/tria-mmult.pdf
July 1, 2010 at 6:30 pm
Anonymous
26. Minimum-Cost Network Design with (Dis)economies of Scale
not online
27. A Unified Framework for Testing Linear-Invariant Properties
not online
28. Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition
http://arxiv.org/abs/1004.3304
29. Optimal stochastic planarization
http://arxiv.org/abs/1004.1666
30. Bounds on Monotone Switching Networks for Directed Connectivity
http://arxiv.org/abs/0911.0664
July 1, 2010 at 6:33 pm
Anonymous
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
July 1, 2010 at 6:35 pm
Anonymous
http://kintali.wordpress.com/2010/07/01/focs-2010-accepted-papers-with-pdf-files/
July 1, 2010 at 6:47 pm
anon
Thanks for all your work! Looks like it will be a great conference.
July 1, 2010 at 9:09 pm
anon
also:
25. Subcubic Equivalences Between Path, Matrix, and Triangle Problems:
http://www.eecs.berkeley.edu/~virgi/tria-mmult-conf.pdf
July 2, 2010 at 1:37 pm
Anonymous
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).