Given an integer-valued function $f:\{0,1\}^n\rightarrow \{0,1,\dots, m-1\}$ that is mildly hard to compute on instances drawn from some distribution $D$ over $\{0,1\}^n$, we show that the function $g(x_1, \dots, x_t) = f(x_1) + \dots + f(x_t)$ is strongly hard to compute on instances $(x_1, \dots, x_t)$ drawn from the product ... more >>>

This note gives an in-depth discussion on feasible mathematics and bounded arithmetic with a focus on Cook's theory PV (STOC'75). We present an informal characterization of PV based on three intuitive postulates and formulate the Feasible Mathematics Thesis, which asserts the equivalence between this informal framework and the formal system ... more >>>

We show that the GCD of two univariate polynomials can be computed by (piece-wise) algebraic circuits of constant depth and polynomial size over any sufficiently large field, regardless of the characteristic. This extends a recent result of Andrews \& Wigderson who showed such an upper bound over fields of zero ... more >>>