Open Problems

A collection of questions I find interesting — some are concrete research problems, others are vague directions. Problems marked internship 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

DegSLP for depth-3 circuits

internship 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}\).

Compression algorithms

Pre-editing in compression algoritms

internship data compression algorithms

Some compression algorithms are not robust to small perturbations. For example, in LZ78, modifying a single bit of a compressible file can make it incompressible, a phenomenon known as a one-bit catastrophe.

The goal is to flip this logic: given a budget of \(k\) edits, can we efficiently find a \(w'\) that minimizes the new compressed size? The naive search takes \(\Omega(n^{k+1})\) time. For LZ77, an \(\varepsilon\)-approximation algorithm exists, which runs in time \(O(f(k, \varepsilon) \cdot n^{\lceil 2k/3 \rceil + 1})\) for an ugly function \(f\).

Questions. Can we improve this algorithm? Can we prove hardness results (NP-hard, W[1]-hard)? What about algorithms for others compression schemes?