Vitaly Feldman

We study the properties of the agnostic learning framework of Haussler (1992)and Kearns, Schapire and Sellie (1992). In particular, we address the question: is there any situation in which membership queries are useful in agnostic learning?

Our results show that the answer is negative for distribution-independent agnostic learning and positive ... more >>>

Emanuele Viola

We prove lower bounds on the redundancy necessary to

represent a set $S$ of objects using a number of bits

close to the information-theoretic minimum $\log_2 |S|$,

while answering various queries by probing few bits. Our

main results are:

\begin{itemize}

\item To represent $n$ ternary values $t \in

\zot^n$ in ...
more >>>