Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Judy Goldsmith:

TR03-039 | 19th May 2003
Judy Goldsmith, Robert H. Sloan, Balázs Szörényi, György Turán

Theory Revision with Queries: Horn, Read-once, and Parity Formulas

A theory, in this context, is a Boolean formula; it is
used to classify instances, or truth assignments. Theories
can model real-world phenomena, and can do so more or less
The theory revision, or concept revision, problem is to
correct a given, roughly correct concept.
This problem is ... more >>>

TR96-011 | 29th January 1996
Stephen A. Bloch, Jonathan F. Buss, Judy Goldsmith

Sharply Bounded Alternation within P

We define the sharply bounded hierarchy, SBHQL, a hierarchy of
classes within P, using quasilinear-time computation and
quantification over values of length log n. It generalizes the
limited nondeterminism hierarchy introduced by Buss and Goldsmith,
while retaining the invariance properties. The new hierarchy has
several alternative characterizations.

We define ... more >>>

ISSN 1433-8092 | Imprint