Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with classification:
TR96-028 | 9th April 1996
Sanjeev Khanna, Madhu Sudan

The Optimization Complexity of Constraint Satisfaction Problems

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

TR04-050 | 13th June 2004
Michelle Effros, Leonard Schulman

Deterministic clustering with data nets

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

TR04-077 | 17th July 2004
Alina Beygelzimer, Varsha Dani, Tom Hayes, John Langford

Reductions Between Classification Tasks

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

TR07-029 | 20th January 2007
Kazuhisa Makino, Suguru Tamaki, Masaki Yamamoto

A Dichotomy Theorem within Schaefer for the Boolean Connectivity Problem

Revisions: 1

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

TR17-177 | 16th November 2017
Daniel Kane, Roi Livni, Shay Moran, Amir Yehudayoff

On Communication Complexity of Classification Problems

Revisions: 1

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

ISSN 1433-8092 | Imprint