Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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

TR96-059 | 12th November 1996
Shai Ben-David, Nader Bshouty, Eyal Kushilevitz

A Composition Theorem for Learning Algorithms with Applications to Geometric Concept Classes

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

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

ISSN 1433-8092 | Imprint