Trevisan and Vadhan [TV00] first constructed seedless extractors for distributions samplable by poly-size circuits under the very strong complexity theoretic hardness assumption that $E=DTIME(2^{O(n)})$ is hard for exponential size circuits with oracle access to $\Sigma_6^{P}$. Their construction works when the distribution has large min-entropy $k=(1-\gamma) \cdot n$, for small constant ... more >>>

Itsykson and Sokolov identified resolution over parities, denoted by $\text{Res}(\oplus)$, as a natural and simple fragment of $\text{AC}^0[2]$-Frege for which no super-polynomial lower bounds on size of proofs are known. Building on a recent line of work, Efremenko and Itsykson proved lower bounds of the form $\text{exp}(N^{\Omega(1)})$, on the size ... more >>>

A property of functions is called location-invariant (or symmetric) if it can be characterized in terms of the frequencies in which each value occurs in the function, regardless of the locations in which each value occurs.
It is known that the (query) complexity of testing location-invariant properties of functions ... more >>>