The celebrated Ore-DeMillo-Lipton-Schwartz-Zippel (ODLSZ) lemma asserts that $n$-variate non-zero polynomial functions of degree $d$ over a field $\mathbb{F}$, are non-zero over any ``grid'' (points of the form $S^n$ for finite subset $S \subseteq \mathbb{F}$) with probability at least $\max\{|S|^{-d/(|S|-1)},1-d/|S|\}$ over the choice of random point from the grid. In particular, ... more >>>

In a seminal work, Buhrman et al. (STOC 2014) defined the class $CSPACE(s,c)$ of problems solvable in space $s$ with an additional catalytic tape of size $c$, which is a tape whose initial content must be restored at the end of the computation. They showed that uniform $TC^1$ circuits are ... more >>>

Trevisan and Vadhan (FOCS 2000) introduced the notion of (seedless) extractors for samplable distributions. They showed that under a very strong complexity theoretic hardness assumption (specifically, that there exists a problem in $\E=\DTIME(2^{O(n)})$ that cannot be computed by size $2^{\Omega(n)}$ circuits that have an oracle to $\Sigma_6^{\P}$) there are extractors ... more >>>