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

Deterministic Polynomial Identity Testing

algebraic complexity derandomization

PIT (Polynomial Identity Testing) asks whether a polynomial given by an arithmetic circuit is identically zero. The Schwartz–Zippel lemma gives a natural randomized algorithm that runs in polynomial time — just evaluate the circuit at a random point — but a deterministic polynomial-time algorithm remains out of reach. This problem is tightly connected to the question of lower bounds. Indeed, such an algorithm would imply circuit lower bounds (this is a result by Kabanets & Impagliazzo in 2004): derandomizing PIT forces either \(\text{NEXP} \not\subseteq \text{P/poly}\) or that the permanent has no polynomial-size arithmetic circuits. In other words, a fast deterministic PIT algorithm cannot exist without proving a strong lower bound — which is part of why the problem is so hard.

While the general case is out of reach (for now), there are some restricted classes of circuits for which deterministic polynomial-time algorithms are known.

Question. Can we find a deterministic polynomial-time algorithm for PIT for other restricted, but more general, classes of circuits?

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?