The groundbreaking paper `Short proofs are narrow - resolution made simple' by Ben-Sasson and Wigderson (J. ACM 2001) introduces what is today arguably the main technique to obtain resolution lower bounds: to show a lower bound for the width of proofs. Another important measure for resolution is space, and in ... more >>>

We study how to extract randomness from a $C$-interleaved source, that is, a source comprised of $C$ independent sources whose bits or symbols are interleaved. We describe a simple approach for constructing such extractors that yields:

(1) For some $\delta>0, c > 0$,
explicit extractors for $2$-interleaved sources on $\{ ... more >>>

Reconstruction of arithmertic circuits has been heavily studied in the past few years and has connections to proving lower bounds and deterministic identity testing. In this paper we present a polynomial time randomized algorithm for reconstructing $\Sigma\Pi\Sigma(2)$ circuits over $\R$, i.e. depth$-3$ circuits with fan-in $2$ at the top addition ... more >>>