We present the first approximation schemes for minimizing weighted flow time
on a single machine with preemption. Our first result is an algorithm that
computes a $(1+\eps)$-approximate solution for any instance of weighted flow
time in $O(n^{O(\ln W \ln P/\eps^3)})$ time; here $P$ is the ratio ... more >>>

Factoring integers is the most established problem on which
cryptographic primitives are based. This work presents an efficient
construction of {\em pseudorandom functions} whose security is based
on the intractability of factoring. In particular, we are able to
construct efficient length-preserving pseudorandom functions where
each evaluation requires only a ... more >>>

We consider the problem of determining whether a given
function f : {0,1}^n -> {0,1} belongs to a certain class
of Boolean functions F or whether it is far from the class.
More precisely, given query access to the function f and given
a distance parameter epsilon, we would ... more >>>