
PreviousNext
We examine the power of Boolean functions with low L_1 norms in several
settings. In large part of the recent literature, the degree of a polynomial
which represents a Boolean function in some way was chosen to be the measure of the complexity of the Boolean function.
However, some functions ...
more >>>
A pseudo-random function is a fundamental cryptographic primitive
that is essential for encryption, identification and authentication.
We present a new cryptographic primitive called pseudo-random
synthesizer and show how to use it in order to get a
parallel construction of a pseudo-random function.
We show an $NC^1$ implementation of synthesizers ...
more >>>
We introduce the model of conservative one-way multiparty complexity
and prove lower and upper bounds on the complexity of pointer jumping.
The pointer jumping function takes as its input a directed layered
graph with a starting node and layers of nodes, and a single edge ...
more >>>
PreviousNext