In 1978, Schaefer considered a subclass of languages in NP and proved a ``dichotomy theorem'' for this class. The subclass considered were problems expressible as ``constraint satisfaction problems'', and the ``dichotomy theorem'' showed that every language in this class is either in P, or is NP-hard. This result is in ... more >>>

We consider the $K$-clustering problem with the $\ell_2^2$ distortion measure, also known as the problem of optimal fixed-rate vector quantizer design. We provide a deterministic approximation algorithm which works for all dimensions $d$ and which, given a data set of size $n$, computes in time ${\rm poly}(K)(d/\ep)^{O(d)} n \log \log ... more >>>

There are two approaches to solving a new supervised learning task: either analyze the task independently or reduce it to a task that has already been thoroughly analyzed. This paper investigates the latter approach for classification problems. In addition to obvious theoretical motivations, there is fairly strong empirical evidence that ... more >>>

P. Gopalan, P. G. Kolaitis, E. N. Maneva and C. H. Papadimitriou studied in [Gopalan et al., ICALP2006] connectivity properties of the solution-space of Boolean formulas, and investigated complexity issues on connectivity problems in Schaefer's framework [Schaefer, STOC1978]. A set S of logical relations is Schaefer if all relations in ... more >>>