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

TR96-010 | 9th February 1996
Christoph Meinel, Anna Slobodova

An Adequate Reducibility Concept for Problems Defined in Terms of Ordered Binary Decision Diagrams

Revisions: 1

Reducibility concepts are fundamental in complexity theory.
Usually, they are defined as follows: A problem P is reducible
to a problem S if P can be computed using a program or device
for S as a subroutine. However, in the case of such restricted
models as ... 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 >>>


TR96-008 | 22nd January 1996
F. Bergadano, N.H. Bshouty, Stefano Varricchio

Learning Multivariate Polynomials from Substitution and Equivalence Queries

It has been shown in previous recent work that
multiplicity automata are predictable from multiplicity
and equivalence queries. In this paper we generalize
related notions in a matrix representation
and obtain a basis for the solution
of a number of open problems in learnability theory.
Membership queries are generalized ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint