Many problems encountered in machine learning and clustering are known to be
computationally infeasible. Finding a low error linear classifier over a
binary-labeled set of vectors, and K-means clustering are common tasks that
fall
in that category. Just the same, such tasks are routinely being carried out
even
over large and high dimensional data sets. One possible explanation to this
mis-match between theory and practice is that naturally occurring inputs are
structured in a way that makes them easier to handle than worst-case inputs.
This work aims to provide a possible theoretical justification to that claim.
We propose a notion of input stability and prove that there exists polynomial
time algorithms, for such inputs, solve the linear classification problem and
many clustering tasks.