Theory of Computation Student Seminar 2025-2026

I will talk about novel algorithms for sequence (time series) prediction based on ideas from stringology. These algorithms are computationally efficient and satisfy mistake bounds related to particular stringological complexity measures of the sequence. One such measure is the size of the smallest straight-line program that produces the sequence. Closely related is the (more restrictive) minimal number of states in an automaton that computes tokens from their time indices. Reversing the order in which the automaton reads the index motivates the dual notion of “zipline program”, which leads to more complexity measures and associated algorithms. A third class comes from the notion of “ambiline programs” that unifies the previous two. Prior research in combinatorics on words shows that there are rich classes of sequences of low complexity according to these measures, implying that these prediction algorithms are quite versatile.

The unprecedented empirical success of deep learning raises major theoretical challenges: training modern networks requires solving large-scale optimization problems which are neither convex nor smooth, and classical statistical wisdom further suggests that they are too complex to generalize meaningfully.

In this talk, I will give a brief overview of some major questions in the field without assuming special background, and will present some recent advancements from a very biased perspective (i.e., mostly my own work).

We present a new result proving that, up to subpolynomial factors, there is no tradeoff between preprocessing time, query time, and size of exact distance oracles for planar graphs.

Namely, we show how given an n-vertex weighted directed planar graph G, one can compute in n^{1+o(1)} time and space a representation of G from which one can extract the exact distance between any two vertices of G in polylogarithmic time.

We initiate the study of combinatorial algorithms for Triangle Detection in H-free graphs. The goal is to decide if a graph that forbids a fixed pattern H as a subgraph contains a triangle, using only “combinatorial” methods that notably exclude fast matrix multiplication. Our work aims to classify which patterns admit a subcubic speedup, working towards a dichotomy theorem. On the lower bound side, we show that if H is not 3-colorable or contains more than one triangle, the complexity of the problem remains unchanged, and no combinatorial speedup is likely possible. On the upper bound side, we develop an embedding approach that results in a strongly subcubic, combinatorial algorithm for a rich class of “embeddable” patterns. Specifically, for an embeddable pattern of size k, our algorithm runs in $\tilde{O}(n^{3− 1/2^{k−3}})$ time, where $\tilde{O}$ hides polylogarithmic factors. This algorithm also extends to listing all the triangles within the same time bound. We supplement this main result with two generalizations: 

• A generalization to patterns that are embeddable up to a single obstacle that arises from a triangle in the pattern. This completes our classification for small patterns, yielding a dichotomy theorem for all patterns of size up to eight. 

• An H-sensitive algorithm for embeddable patterns, which runs faster when the number of copies of H is significantly smaller than the maximum possible Ω(n^k). Finally, we focus on the special case of odd cycles. We present specialized Triangle Detection algorithms that are very efficient: 

• A combinatorial algorithm for C_{2k+1}-free graphs that runs in \tilde{O}(m+n^{1+2/k}) time for every k ≥ 2, where m is the number of edges in the graph. 

• A combinatorial C_5-sensitive algorithm that runs in \tilde{O}(n^2 + n^{4/3} t^{1/3}) time, where t is the number of 5-cycles in the graph.

Based on joint work with Amir Abboud and Ron Safier.