Moni Naor, Omer Reingold

Luby and Rackoff showed a method for constructing a pseudo-random

permutation from a pseudo-random function. The method is based on

composing four (or three for weakened security) so called Feistel

permutations each of which requires the evaluation of a pseudo-random

function. We reduce somewhat the complexity ...
more >>>

Bodo Manthey, RĂ¼diger Reischuk

Binary search trees are one of the most fundamental data structures. While the

height of such a tree may be linear in the worst case, the average height with

respect to the uniform distribution is only logarithmic. The exact value is one

of the best studied problems in average case ...
more >>>

Noga Alon, Shachar Lovett

A family of permutations in $S_n$ is $k$-wise independent if a uniform permutation chosen from the family maps any distinct $k$ elements to any distinct $k$ elements equally likely. Efficient constructions of $k$-wise independent permutations are known for $k=2$ and $k=3$, but are unknown for $k \ge 4$. In fact, ... more >>>

Emanuele Viola

A map $f:[n]^{\ell}\to[n]^{n}$ has locality $d$ if each output symbol

in $[n]=\{1,2,\ldots,n\}$ depends only on $d$ of the $\ell$ input

symbols in $[n]$. We show that the output distribution of a $d$-local

map has statistical distance at least $1-2\cdot\exp(-n/\log^{c^{d}}n)$

from a uniform permutation of $[n]$. This seems to be the ...
more >>>

Sourav Chakraborty, Chandrima Kayal, Manaswi Paraashar

The role of symmetry in Boolean functions $f:\{0,1\}^n \to \{0,1\}$ has been extensively studied in complexity theory.

For example, symmetric functions, that is, functions that are invariant under the action of $S_n$ is an important class of functions in the study of Boolean functions.

A function $f:\{0,1\}^n \to \{0,1\}$ ...
more >>>