Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-Feedprevious PreviousNext next

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


TR04-076 | 17th September 2004
Oliver Giel, Ingo Wegener

Searching Randomly for Maximum Matchings

Many real-world optimization problems in, e.g., engineering
or biology have the property that not much is known about
the function to be optimized. This excludes the application
of problem-specific algorithms. Simple randomized search
heuristics are then used with surprisingly good results. In
order to understand the working principles behind such
more >>>


TR04-075 | 21st July 2004
Michael Schmitt

Some dichotomy theorems for neural learning problems

The computational complexity of learning from binary examples is
investigated for linear threshold neurons. We introduce
combinatorial measures that create classes of infinitely many
learning problems with sample restrictions. We analyze how the
complexity of these problems depends on the values for the measures.
... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint