### Alternative Measures of Complexity

A fundamental problem of complexity theory: Worst-case complexity is the most common and researched measure of computational complexity. However, it is known to give rise to over-pessimistic complexity results. Many problems that are hard from the point of view of that theory turn out to be efficiently solvable in practice (SAT is the most conspicuous of those). A variety of algorithmic problems in machine learning fall in that category. In (TAMC 06), I propose an alternative measure of computational complexity that takes into account not just the input size but also its "noise robustness" w.r.t. a given task. The new measure coincides with the common worst-case complexity for "nicely behaving" inputs, but becomes less demanding for noise-sensitive inputs. I introduced algorithms that are computationally efficient w.r.t. the new measure for a variety of NP-hard tasks (MLJ 2007, NIPS2000, AISTATS 2009). Assuming that inputs that arise naturally in machine learning are nicely behaved, these results provide a possible explanation to the above mentioned theory-practice gap.

However, the problem is still wide open: The algorithms described above are not practical, and the scope of problems they apply to is only a small fraction of the wide range of problems demonstrating the practice-theory gap described above. This is a very challenging and exiting area of research that is currently addressed by several groups around the word.

### Publications

- Which Data Sets are Clusterable? - A Theoretical Study of Clusterability

Margarita Ackerman and S. Ben-David AISTATS 2009 - A framework for statistical clustering with constant time approximation algorithms for K-median and K-means clustering

Shai Ben-David. Machine Learning 66(2-3): 243-257 (2007) -
Alternative Measures of Computational Complexity

S. Ben-David TAMC'06 -
A Framework for Statistical Clustering with a Constant Time Approximation Algorithms for K-Median Clustering

S. Ben-David COLT 2004 - Efficient Learning of Linear Perceptrons

Shai Ben-David and Hans-Ulrich Simon NIPS 2000