Open Problems

A collection of questions I find interesting — some are concrete research problems, others are vague directions. Problems marked stage are potential internship topics; feel free to get in touch.

This page is very fresh, I will be adding more problems over time.

Algebraic Complexity

The degree of straight-line programs (DegSLP) for depth-3 circuits

algebraic complexity algorithms

DegSLP is the algorithmic problem of computing the degree of a multivariate polynomial given by an arithmetic circuit. The complexity gap for this problem is currently a shame: the best known upper bound is \(\text{coRP}^{\text{PP}}\) (Kayal, 2010), while the best lower bound is P-hard under logspace reductions (Koiran & Perifel, 2007).

A natural approach to finding a better algorithm is to tackle restricted classes, such as univariate depth-3 circuits (\(\Sigma\Pi\Sigma\)). One of the first instance for which the problem becomes hard is for polynomials of the form \((\prod_{i=1}^{n}(\alpha_i X^{e_{i}}+\beta_{i})) - A \cdot X^N\)

Question. Can we compute the degree of these restricted depth-3 circuits in polynomial time? Or prove better hardness results?

Real roots of \(f \cdot g + 1\) and the real \(\tau\)-conjecture

algebraic complexity

Consider two sparse polynomials \(f, g \in \mathbb{R}[x]\) with \(t_f\) and \(t_g\) non-zero terms. While Descartes’ Rule of Signs gives a quadratic bound of \(O(t_f \times t_g)\), it is conjectured that the number of real roots is much smaller.

Question. Is the number of real roots of \(f \cdot g + 1\) bounded by \(O(t_f + t_g)\)? Or at least by \(o(t_f \times t_g)\)?

This problem is a “toy case” of Koiran’s real \(\tau\)-conjecture. The general conjecture states that the number of real roots of a sum of \(k\) products of \(m\) sparse polynomials should be bounded by a polynomial in \(k, m\) and the sparsity. A positive answer would be an interesting step toward \(\text{VP} \neq \text{VNP}\).