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

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