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

TR00-014 | 16th February 2000
Matthias Krause, Stefan Lucks

On Learning versus Distinguishing and the Minimal Hardware Complexity of Pseudorandom Function Generators

\begin{abstract}
A set $F$ of $n$-ary Boolean functions is called a pseudorandom function generator
(PRFG) if communicating
with a randomly chosen secret function from $F$ cannot be
efficiently distinguished from communicating with a truly random function.
We ask for the minimal hardware complexity of a PRFG. This question ... more >>>


TR00-013 | 14th February 2000
Daniel Král

Algebraic and Uniqueness Properties of Parity Ordered Binary Decision Diagrams and their Generalization

Ordered binary decision diagrams (OBDDs) and parity ordered binary
decision diagrams have proved their importance as data structures
representing Boolean functions. In addition to parity OBDDs we study
their generalization which we call parity AOBDDs, give the algebraic
characterization theorem and compare their minimal size to the size
more >>>


TR00-012 | 14th February 2000
Ke Yang

Integer Circuit Evaluation is PSPACE-complete

In this paper, we address the problem of evaluating the
Integer Circuit (IC), or the $\{\cup, \times, +\}$-circuit over
the set of natural numbers. The problem is a natural extension
to the integer expression by Stockmeyer and Mayer, and is also studied
by Mckenzie, Vollmer and Wagner in ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint