FOCS 2010 有趣的論文

Ref.: FOCS 2010 Accepted Papers (with pdf files) « My Brain is Open

依照慣例, 我每年都會把有趣的論文挑出來, 今年有蠻多都蠻有趣的. 不過我有沒有機會去看, 甚至找出來瞄一眼都很難說了.

• Settling the Polynomial Learnability of Mixtures of Gaussians
• Constructive Algorithms for Discrepancy Minimization
• A non-linear lower bound for planar epsilon-nets
• A lower bound for dynamic approximate membership data structures
• A Decidable Dichotomy Theorem on Directed Graph Homomorphisms with Non-negative Weights
• New Constructive Aspects of the Lovasz Local Lemma
• Approximation Algorithms for the Edge-Disjoint Paths Problem via Raecke Decompositions
• The complexity of distributions
• A Unified Framework for Testing Linear-Invariant Properties
• A Fourier-analytic approach to Reed-Muller decoding
• Backyard Cuckoo Hashing: Constant Worst-Case Operations with a Succinct Representation
• Clustering with Spectral Norm and the k-means Algorithm
• A separator theorem in minor-closed classes
• Stability yields a PTAS for k-Median and k-Means Clustering
• Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity
• Fast approximation algorithms for flow and cut-based problems in undirected graphs
• Estimating the longest increasing sequence in polylogarithmic time
• Lower Bounds for Near Neighbor Search via Metric Expansion
• The Monotone Complexity of k-Clique on Random Graphs
• Learning Convex Concepts from Gaussian Distributions with PCA
• Sublinear Optimization for Machine Learning
• On the Computational Complexity of Coin Flipping