All reports by Author Shai Ben-David:

__
TR98-021
| 7th April 1998
__

Shai Ben-David, Anna Gringauze.#### On the Existence of Propositional Proof Systems and Oracle-relativized Propositional Logic.

Revisions: 1

__
TR96-059
| 12th November 1996
__

Shai Ben-David, Nader Bshouty, Eyal Kushilevitz#### A Composition Theorem for Learning Algorithms with Applications to Geometric Concept Classes

Shai Ben-David, Anna Gringauze.

We investigate sufficient conditions for the existence of

optimal propositional proof systems (PPS).

We concentrate on conditions of the form CoNF = NF.

We introduce a purely combinatorial property of complexity classes

- the notions of {\em slim} vs. {\em fat} classes.

These notions partition the ...
more >>>

Shai Ben-David, Nader Bshouty, Eyal Kushilevitz

This paper solves the open problem of exact learning

geometric objects bounded by hyperplanes (and more generally by any constant

degree algebraic surfaces) in the constant

dimensional space from equivalence queries only (i.e., in the on-line learning

model).

We present a novel approach that allows, under ...
more >>>