Sanjeev Khanna, Madhu Sudan

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 >>>

Michelle Effros, Leonard Schulman

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

more >>>

Alina Beygelzimer, Varsha Dani, Tom Hayes, John Langford

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 >>>

Kazuhisa Makino, Suguru Tamaki, Masaki Yamamoto

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 >>>

Daniel Kane, Roi Livni, Shay Moran, Amir Yehudayoff

This work introduces a model of distributed learning in the spirit of Yao's communication complexity model. We consider a two-party setting, where each of the players gets a list of labelled examples and they communicate in order to jointly perform some learning task. To naturally fit into the framework of ... more >>>