An $n$-variate polynomial $g$ of degree $d$ is a $(n,d,t)$ design polynomial if the degree of the gcd of every pair of monomials of $g$ is at most $t-1$. The power symmetric polynomial $\mathrm{PSym}_{n,d} := \sum_{i=1}^{n} x^d_i$ and the sum-product polynomial $\mathrm{SP}_{s,d} := \sum_{i=1}^{s}\prod_{j=1}^{d} x_{i,j}$ are instances of design polynomials ... more >>>

A long-standing open problem dating back to the 1960s is whether there exists a search-to-decision reduction for the time-bounded Kolmogorov complexity problem - that is, the problem of determining whether the length of the shortest time-$t$ program generating a given string $x$ is at most $s$.

In this work, we ... more >>>

Recently, Pasarkar, Papadimitriou, and Yannakakis (ITCS 2023) have introduced the new TFNP subclass called PLC that contains the class PPP; they also have proven that several search problems related to extremal combinatorial principles (e.g., Ramsey’s theorem and the Sunflower lemma) belong to PLC. This short paper shows that the class ... more >>>