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

TR98-040 | 24th July 1998
Madhu Sudan, Luca Trevisan

Probabilistically checkable proofs with low amortized query complexity

The error probability of Probabilistically Checkable Proof (PCP)
systems can be made exponentially small in the number of queries
by using sequential repetition. In this paper we are interested
in determining the precise rate at which the error goes down in
an optimal protocol, and we make substantial progress toward ... more >>>


TR98-039 | 14th July 1998
Christoph Meinel, Thorsten Theobald

Ordered Binary Decision Diagrams and Their Significance in Computer-Aided Design of VLSI Circuits - a Survey

Many problems in computer-aided design of highly integrated circuits
(CAD for VLSI) can be transformed to the task of manipulating objects
over finite domains. The efficiency of these operations depends
substantially on the chosen data structures. In the last years,
ordered binary decision diagrams (OBDDs) have ... more >>>


TR98-038 | 9th July 1998
Marek Karpinski

On the Computational Power of Randomized Branching Programs

We survey some upper and lower bounds established recently on
the sizes of randomized branching programs computing explicit
boolean functions. In particular, we display boolean
functions on which randomized read-once ordered branching
programs are exponentially more powerful than deterministic
or nondeterministic read-$k$-times branching programs for ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint