Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > MEMBERSHIP QUERY:
Reports tagged with membership query:
TR08-091 | 10th September 2008
Vitaly Feldman

On The Power of Membership Queries in Agnostic Learning

Revisions: 1

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

TR09-005 | 7th December 2008
Emanuele Viola

Bit-Probe Lower Bounds for Succinct Data Structures

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

ISSN 1433-8092 | Imprint