Assuming that the class TAUT of tautologies of propositional logic has no almost optimal algorithm, we show that every algorithm $\mathbb A$ deciding TAUT has a polynomial time computable sequence witnessing that $\mathbb A$ is not almost optimal. The result extends to every $\Pi_t^p$-complete problem with $t\ge 1$; however, we ... more >>>

Decomposition theorems in classical Fourier analysis enable us to express a bounded function in terms of few linear phases with large Fourier coefficients plus a part that is pseudorandom with respect to linear phases. The Goldreich-Levin algorithm can be viewed as an algorithmic analogue of such a decomposition as it ... more >>>

We show that there are families of polynomials having small depth-two arithmetic circuits that cannot be expressed by algebraic branching programs of width two. This clarifies the complexity of the problem of computing the product of a sequence of two-by-two matrices, which arises in several
settings.

more >>>