We study the problem of computing the number of distinct k-mers (strings of length k) in labelled graphs. We show that in general graphs, it is #P-complete, even on connected, deterministic DAGs. Fortunately, in the restricted class of deterministic Wheeler graphs (Gagie, Manzini, and Sirèn, TCS 2017) we show that the distinct k-mers of such a graph W=(V, E) can be counted in O((|V|+|E|)k) time or O(|V|^4log k) time. As an application, we show how to build a succint data structure to navigate the de Bruijn graph of the k-mers in output-sensitive time, without needing to pay Ω(k) time per k-mer. This outperforms previous construction methods for large values of k.

Tree compression is a well-studied area that aims at reducing the size of tree representations by exploiting different forms of repetition. While the underlying theory is well understood, there is still significant room for experimental investigation, particularly in the design of compressed representations that efficiently support navigational queries.

In this work, we address the problem of designing, engineering, and experimentally evaluating a compression technique for unlabeled binary trees based on repeated subtrees, yielding the minimal Directed Acyclic Graph (DAG) of the input tree. We show how this representation can be computed in linear time and space directly from a succinct encoding of the tree, and how it can be augmented with compact auxiliary data structures to support Lowest Common Ancestor (LCA) queries.

When the input tree is the Cartesian tree of an array, LCA queries can be used to answer Range Minimum Queries (RMQs) on the underlying array. This is particularly relevant in the encoding model, where the array is not accessible at query time, and a space lower bound of $2n-O(\log n)$ bits is known. Given the numerous applications of RMQs, we use this problem as a case study for our experimental evaluation, testing our implementation on $11$ real-world datasets. Our experiments show that, on almost every dataset, our implementation is the most space-efficient, using as few as $0.11n$ bits, while still delivering practical query times.

A central question in algebraic complexity theory is understanding the behaviour of polynomial computation models under basic algebraic operations. While closure under addition and multiplication holds for most of the standard models like algebraic circuits, closure under factorisation remains subtle. In this talk, we will discuss a new result which proves that the well-studied model called read-once oblivious algebraic branching programs (ROABPs) is not closed under factoring. This result offers a contrasting perspective to recent breakthrough work that gave a unified framework for proving closure under factorisation in other regimes. We will also discuss similar non-closure properties of ROABPs under other natural operations such as powering and symmetric composition.

This is based on joint work with Andrews, Armand, Hansen, Limaye, Srinivasan, and Tavenas. [https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.9]

Atserias and Müller (FOCS, 2019) proved that for every unsatisfiable CNF formula F, the Resolution proof system does not have subexponential-size refutations of the formula Ref(F) stating that “F has small Resolution refutations”. On the other hand, when F is satisfiable, Pudlák (TCS, 2003) showed that there are polynomial-size Resolution refutations of Ref(F). Pudlák's upper bound builds a refutation around an explicit satisfying assignment of F. A question that had remained open is: do all short Resolution refutations of Ref(F) explicitly leak a satisfying assignment of F?

We answer this question affirmatively: we provide a polynomial-time algorithm that given a short Resolution refutation of Ref(F) always succeeds in extracting a satisfying assignment for F. The algorithm follows from a new feasibly constructive proof of the Atserias-Müller lower bound. We show that this new proof is formalizable in Cook's theory PV of bounded arithmetic, which further implies that Extended Frege has polynomial-size proofs of a suitable encoding of the statement that automating Resolution is NP-hard.

Motivated by this algorithm we introduce a new meta-computational problem relating proofs and computation: the Proof Analysis Problem (PAP). For a proof system Q, the problem PAP_Q asks, given a CNF formula F and a Q-proof of the Resolution lower bound statement ¬Ref(F) whether F is satisfiable. In contrast with the algorithm that analyzes Resolution refutations, we prove that the Proof Analysis Problem for Extended Frege (EF) is NP-complete. In particular, EF can prove Resolution lower bounds on satisfiable formulas without necessarily revealing a satisfying assignment.

Based on joint work with Albert Atserias, Susanna F. de Rezende and Erfan Khaniki.

We present a dynamic data structure that maintains a tree decomposition of width at most 9k+8 of a dynamic graph with treewidth at most k, which is updated by edge insertions and deletions. The amortized update time of our data structure is 2^O(k) log n, where n is the number of vertices. The data structure also supports maintaining any "dynamic programming scheme" on the tree decomposition, providing, for example, a dynamic version of Courcelle's theorem with O_k(log n) amortized update time; the O_k(⋅) notation hides factors that depend on k. This improves upon a result of Korhonen, Majewski, Nadara, Pilipczuk, and Sokołowski [FOCS 2023], who gave a similar data structure but with amortized update time 2^k^O(1) n^o(1). Furthermore, our data structure is arguably simpler. Our main novel idea is to maintain a tree decomposition that is "downwards well-linked", which allows us to implement local rotations and analysis similar to those for splay trees.

This talk is based on https://arxiv.org/abs/2504.02790.

The region connection calculus with 5 or 8 basic relations (RCC-5/8) and Allen's interval algebra (IA) are two well-known NP-hard spatial-temporal qualitative reasoning problems. They are solvable in $2^{O(n \log n)}$ time, where $n$ is the number of variables, and IA is additionally known to be solvable in $o(n)^n$ time. However, no improvement over exhaustive enumeration is known for RCC, and if they are also solvable in single exponential time $2^{O(n)}$ is unknown. We make two significant algorithmic contributions based on dynamic programming. The first algorithm runs in $4^n$ time and is applicable to a non-trivial, NP-hard fragment of IA, which includes the well-known interval graph sandwich problem (Golumbic and Shamir, 1993). For the richer RCC-8 problem we use a more sophisticated approach which asymptotically matches the $o(n)^n$ bound for IA.

The disk intersection graph of a set of disks has the disks as vertices, with an edge between two disks if and only if they intersect. A (1+ε)-spanner of a graph is a sparse subgraph that preserves all pairwise shortest-path distances up to a multiplicative factor of (1+ε).

We maintain a (1+ε)-spanner over the disk intersection graph of a dynamic set of disks. We restrict all disks to have their diameter in [4,Ψ] for some fixed and known Ψ. The resulting (1+ε)-spanner has size O(n ε^{-2} log(Ψ) log (ε^{-1})), where n is the present number of disks. Our approach requires O(ε^{-2} n log^4(n) log Ψ) space and has an O((Ψ/ε)^2 log^4(n) log^2(Ψ) log^2 (ε^{-1})) expected amortised update time. For constant ε and Ψ, this spanner has near-linear size, uses near-linear space and has polylogarithmic update time.

We compare the power of monotone circuits and general circuits with small depth. In the algebraic setting, we construct an n-variate polynomial $P$ computed by a depth-3 circuit of size $n^{O(1)}$ such that any monotone circuit computing $P$ has size at least $2^{\Omega(n)}. This is an asymptotically optimal separation between monotone and general algebraic circuits, improving all previously known separations including the seminal work of Valiant (1980) and recent results by Chattopadhyay, Datta, and Mukhopadhyay (2021). We then boot-strap this result to prove strong monotone separations for polynomials of constant degree, which solves an open problem from the survey of Shpilka and Yehudayoff (2010). 

In the Boolean setting, we improve known separations between the NC-hierarchy and monotone circuits, and also solve an open problem by Jukna and Seiwert (2020) regarding the relative powers of greedy and pure dynamic programming algorithms.

This is a joint work with Bruno Pasqualotto Cavalar, Partha Mukhopadhyay, Srikanth Srinivasan, and Amir Yehudayoff. The paper is available at https://eccc.weizmann.ac.il/report/2025/219/.

In this talk, we discuss our new PCP (Probabilistic Checkable Proofs) protocol from the paper "Ideals, Gröbner Bases, and PCPs", and how it leads to a new proof of the PCP theorem.

All known proofs of the PCP theorem rely on multiple "composition'' steps, where PCPs over large alphabets are turned into PCPs over much smaller alphabets at a (relatively) small price in the soundness error of the PCP. Algebraic proofs, starting with the work of Arora, Lund, Motwani, Sudan, and Szegedy use at least 2 such composition steps, whereas the ``Gap amplification'' proof of Dinur uses $\Theta(\log n)$ such composition steps. In this work, we present the first PCP construction using just one composition step. The key ingredient, missing in previous work and finally supplied in this paper,  is a basic PCP of size $2^{n^\varepsilon}$, for any $\varepsilon > 0$, that makes $\mathcal{O}_\varepsilon(1)$ queries.

Based on joint work with Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan & Madhu Sudan

Correlation clustering is a well-studied problem, first proposed by Bansal, Blum, and Chawla [Mach. Learn. '04]. The input is an unweighted, undirected graph. The problem is to cluster the vertices so as to minimize the number of edges between vertices in different clusters and missing edges between vertices inside the same cluster. This problem has a wide application in data mining and machine learning. We introduce a general framework that transforms existing static correlation clustering algorithms into fully-dynamic ones that work against an adaptive adversary. 

We show how to apply our framework to known efficient correlation clustering algorithms, starting from the classic 3-approximate Pivot algorithm from Ailon, Charikar and Newman [JACM'08]. Applied to the most recent sublinear 1.485-approximation algorithm from Cao, Cohen-Addad, Lee, Li, Lolck, Newman, Thorup, Vogl, Yan and Zhang [STOC'25], we get an 1.485-approximation fully-dynamic algorithm that works with worst-case constant update time. The original static algorithm gets its approximation factor with constant probability, and we get the same against an adaptive adversary in the sense that for any given update step, not known to our algorithm, our solution is an 1.485-approximation with constant probability when we reach this update.

Most of previous dynamic algorithms, including the celebrated result from Behnezhad, Charikar, Ma and Tan [FOCS'19], had approximation factors around $3$ in expectation, and they could only handle an oblivious adversary. A recent algorithm by Braverman, Dharangutte, Pai, Shah, and Wang [AISTATS'25] handles an adaptive adversary, but it has a large unspecified constant approximation ratio. This contrasts with our general transformation, which works with all the best approximation factors known for the static case.

We study the minimum s-t cut in a graph in the context of computer vision from both a theoretical and a practical point of view. Specifically, we revisit a minimum s-t cut algorithm that is widely used in computer vision: the Boykov-Kolmogorov (BK) algorithm [Boykov, Kolmogorov, PAMI 2004]. We improve the analysis of the time complexity of the BK algorithm to O(mn|C|) and propose a variant of the algorithm with a time complexity of O(m|C|), where n is the number of vertices, m is the number of edges, and |C| is the capacity of the cut. We additionally propose a highly memory-efficient graph representation and use it to implement our algorithm. Our implementation can compute minimum s-t cuts faster and on larger graphs than previous implementations of the BK algorithm. Joint work with Inge Li Gørtz, Vedrana A. Dahl, Philip Bille, and Anders B. Dahl.

The Fréchet distance is a popular distance measure between trajectories or curves in space, or between walks in graphs. We study computing the Fréchet distance between walks in the d-dimensional grid graphs, i.e. ℤ^d where points share an edge if they differ by one in one coordinate.

We give an algorithm, that for two simple paths on n vertices,  (1+ε)-approximates the Fréchet distance in time Õ((n/ε)^{2-2/d}). We complement this by a near-matching fine-grained lower bound: for constant dimensions d≥3, there is no O((ε^{2/d} (n/ε)^{2-2/d})^{1-δ}) algorithm for any δ>0 unless the Orthogonal Vector Hypothesis fails. Thus, our results are tight up to a factor ε^{2/d} and log(n)-factors.

We introduce spiky rank, a new matrix parameter that enhances blocky rank by combining the combinatorial structure of the latter with linear-algebraic flexibility. A spiky matrix is block-structured with diagonal blocks that are arbitrary rank-one matrices, and the spiky rank of a matrix is the minimum number of such matrices required to express it as a sum. This measure extends blocky rank to real matrices and is more robust for problems with both combinatorial and algebraic character.

Our conceptual contribution is as follows: we propose spiky rank as a well-behaved candidate matrix complexity measure and demonstrate its potential through applications. We show that large spiky rank implies high matrix rigidity, and that spiky rank lower bounds yield lower bounds for depth-2 ReLU circuits, the basic building blocks of neural networks. On the technical side, we establish tight bounds for random matrices and develop a framework for explicit lower bounds, applying it to Hamming distance matrices and spectral expanders. Finally, we relate spiky rank to other matrix parameters, including blocky rank, sparsity, and the gamma-2 norm.

Based on joint work with Lianna Hambardzumyan, Konstantin Myasnikov, Artur Riazanov, and Adi Shraibman, to appear at ICALP 2026.

We present a generic way to obtain level lower bounds for (promise) CSP hierarchies from degree lower bounds for algebraic proof systems. More specifically, we show that pseudo-reduction operators in the sense of Alekhnovich and Razborov [Proc. Steklov Inst. Math. 2003] can be used to fool the cohomological -consistency algorithm. As applications, we prove optimal level lower bounds for  vs. -coloring for all , and give a simplified proof of the lower bounds for lax and null-constraining CSPs of Chan and Ng [STOC 2025].