We study extractors computable in uniform \mathrm{AC}^0 and uniform \mathrm{NC}^1.

For the \mathrm{AC}^0 setting, we give a construction such that for every k \ge n/ \mathrm{poly} \log n, \eps \ge 2^{-\mathrm{poly} \log n}, it can extract (1-\gamma)k randomness from an (n, k) source for an arbitrary constant ... more >>>

In the Minmax Set Cover Reconfiguration problem, given a set system \mathcal{F} over a universe and its two covers \mathcal{C}^\mathrm{start} and \mathcal{C}^\mathrm{goal} of size k, we wish to transform \mathcal{C}^\mathrm{start} into \mathcal{C}^\mathrm{goal} by repeatedly adding or removing a single set of \mathcal{F} while covering the universe in any intermediate state. ... more >>>

We initiate an in-depth proof-complexity analysis of polynomial calculus (Q-PC) for Quantified Boolean Formulas (QBF). In the course of this we establish a tight proof-size characterisation of Q-PC in terms of a suitable circuit model (polynomial decision lists). Using this correspondence we show a size-degree relation for Q-PC, similar in ... more >>>