Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Christino Tamon:

TR98-076 | 13th November 1998
Nader Bshouty, Jeffrey J. Jackson, Christino Tamon

Attribute Efficient PAC Learning of DNF with Membership Queries under the Uniform Distribution

We study attribute efficient learning in the PAC learning model with
membership queries. First, we give an {\it attribute efficient}
PAC-learning algorithm for DNF with membership queries under the
uniform distribution. Previous algorithms for DNF have sample size
polynomial in the number of attributes $n$. Our algorithm is the
first ... more >>>

TR96-009 | 17th January 1996
Francesco Bergadano, Nader Bshouty, Christino Tamon, Stefano Varricchio

On Learning Branching Programs and Small Depth Circuits

This paper studies the learnability of branching programs and small depth
circuits with modular and threshold gates in both the exact and PAC learning
models with and without membership queries. Some of the results extend earlier
works in [GG95,ERR95,BTW95]. The main results are as follows. For
branching programs we ... more >>>

TR95-032 | 6th April 1995
Nader Bshouty, Christino Tamon

On the Fourier spectrum of monotone functions

ISSN 1433-8092 | Imprint