12 papers · ranked by Valyu relevance
Bruno Grenet
The works presented in this habilitation concern the algorithmics of polynomials. This is a central topic in computer algebra, with numerous applications both within and outside the field—cryptography, error-correcting codes, etc. For many problems, extremely efficient algorithms have been developed since the 1960s.…
Panagiotis Charalampopoulos, Taha El Ghazi, Jonas Ellert, Paweł Gawrychowski + 1 more
Many string processing problems can be phrased in the streaming setting, where the input arrives symbol by symbol and we have sublinear working space. The area of streaming algorithms for string processing has flourished since the seminal work of Porat and Porat [FOCS 2009]. Unfortunately, problems with efficient…
J.J. Dai, Mohsen Ghaffari, Julian Portmann
We present a randomized algorithm that computes a constant approximation of a graph's arboricity, using O˜(n/λ) queries to adjacency lists and in the same time bound. Here, n and λ denote the number of nodes and the graph's arboricity, respectively. The O˜(n/λ) query complexity of our algorithm is nearly optimal. Our…
Rome, Hayden, Lynch, Jayson + 6 more
Algorithm research focuses primarily on how many operations processors need to do (time complexity). But for many problems, both the runtime and energy used are dominated by memory accesses. In this paper, we present the first broad survey of how algorithmic progress has improved memory usage (space complexity). We…
Peyman Afshani, Rezaul Chowdhury, Inge Li Gørtz, Mayank Goswami + 2 more
This paper addresses the Counting Long Aggregated Visits problem, which is defined as follows. We are given users and regions, where each user spends some time visiting some regions. For a parameter and a query consisting of a subset of regions, the task is to count the number of distinct users whose aggregate time…
Dominik Kempa, Tomasz Kociumaka
In this work, we study limits of compressed data structures, i.e., data structures that support various queries on the input text T ∈ Σ n in space proportional to the size of T in compressed form. On the upper bound side, currently nearly all fundamental queries can be efficiently supported in O(δ(T)log O (1) n) space…
Ryosuke Yamano, Tetsuo Shibuya
We study exact algorithms for Equal-Subset-Sum in the worst-case setting: given a set $S$ of $n$ integers, find two distinct subsets $A,B\subseteq S$ whose sums are equal. We establish a new state-of-the-art bound for this problem by improving the fastest known algorithm, due to Randolph and Węgrzycki (STOC 2026), from…
Daniel Dadush, James B. Orlin, Aaron Sidford, László A. Végh
We provide faster strongly polynomial time algorithms solving maximum flow in structured n-node m-arc networks. Our results imply an n ω +o(1)-time strongly polynomial time algorithms for computing a maximum bipartite b-matching where ω is the matrix multiplication constant. Additionally, they imply an m1+o(1)W-time…
Karl Bringmann, Nick Fischer, Yanheng Wang
The subgraph isomorphism problem and its generalizations such as conjunctive queries, where some nodes are projected, are among the most fundamental problems in graph algorithms and database theory. In this paper, we study the listing and enumeration variants of these problems and present two main results. (1) We…
William Kuszmaul, Aaron Putterman, Tingqiang Xu, Hangrui Zhou + 1 more
A dynamic retrieval data structure encodes a function $f:K \rightarrow [2^v]$ for a set $K \subseteq [U]$, while supporting queries $f(x)$ for $x\in K$, insertions \texttt{Insert}$(x, f(x))$ for $x \notin K$, and deletions \texttt{Delete}$(x)$ for $x \in K$. Given an upper bound $N$ on $|K|$, it is known how to solve…
Márk Hunor Juhász, Péter Madarasi
We study maximum matching problems in temporal graphs whose underlying graph is a tree. We consider two temporal models. In a $Δ$-matching, selected time edges sharing an endpoint must have time ticks differing by at least $Δ$. In a $γ$-matching, the selected objects are blocks of $γ$ consecutive appearances of the…
Duncan Adamson, Paul G Spirakis
Temporal graphs are a generalisation of (static) graphs, defined by a sequence of snapshots, each a static graph defined over a common set of vertices. Exploration problems are one of the most fundamental and most heavily studied problems on temporal graphs, asking if a set of m agents can visit every vertex in the…