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