
[Points: 8; Issued: 2004/03/04; Deadline: 2004/04/28; Tutor:
Stefan Klampfl; Infohour: 2004/04/26, 12:0013:00,
Seminarraum IGI; Einsichtnahme: 2004/05/17, 12:0013:00,
Seminarraum IGI; Download: pdf; ps.gz]
Construct a probability measure on
for which you can prove
that there exists a hypothesis
with the
following properties:
 can be defined by a
threshold circuit consisting of more than one gate.

is less
than the true error
of every
hypothesis defined by
a single threshold gate.
The proof should be clearly structured and consist of complete
sentences.
