We prove the existence of a $poly(n,m)$-time computable pseudorandom generator which ``$1/poly(n,m)$-fools'' DNFs with $n$ variables and $m$ terms, and has seed length $O(\log^2 nm \cdot \log\log nm)$. Previously, the best pseudorandom generator for depth-2 circuits had seed length $O(\log^3 nm)$, and was due to Bazzi (FOCS 2007). It follows ... more >>>

We give near-optimal constructions of extractors secure against quantum bounded-storage adversaries. One instantiation gives the first such extractor to achieve an output length Theta(K-b), where K is the source's entropy and b the adversary's storage, depending linearly on the adversary's amount of storage, together with a poly-logarithmic seed length. Another ... more >>>

We study the power of non-uniform attacks against one-way functions and pseudorandom generators. Fiat and Naor show that for every function $f: [N]\to [N]$ there is an algorithm that inverts $f$ everywhere using (ignoring lower order factors) time, space and advice at most $N^{3/4}$. We show that an algorithm using ... more >>>

We give an $O(N\cdot \log N\cdot 2^{O(\log^*N)})$ algorithm for multiplying two $N$-bit integers that improves the $O(N\cdot \log N\cdot \log\log N)$ algorithm by Sch\"{o}nhage-Strassen. Both these algorithms use modular arithmetic. Recently, F\"{u}rer gave an $O(N\cdot \log N\cdot 2^{O(\log^*N)})$ algorithm which however uses arithmetic over complex numbers as opposed to modular ... more >>>