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-013 | 14th February 1996
Mitsunori Ogihara

The PL Hierarchy Collapses

It is shown that the PL hierarchy defined in terms of the
standard Ruzzo-Simon-Tompa relativization collapses to PL.

more >>>

TR96-012 | 14th December 1995
Giuseppe Ateniese, Carlo Blundo, Alfredo De Santis, Douglas R. Stinson

Visual Cryptography for General Access Structures

A visual cryptography scheme for a
set $\cal P $ of $n$ participants is a method to encode a secret
image $SI$ into $n$ shadow images called shares, where each participant in
$\cal P$ receives one share. Certain qualified subsets of participants
can ``visually'' recover the secret image, but
other, ... 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 >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint