Seminar on Theory of Computing - Seminář z teoretické informatiky

Organizers: Ondřej Čepek, Pavel Hubáček, Petr Kolman, Michal Koucký, Jiří Sgall, Pavel Veselý

Contact: <koucky@iuuk.mff.cuni.cz>

Lecture code: NTIN102 - 0/2 Z

Time: Tue 12:00-14:00

Place: S8, Malá Strana

A seminar presenting ongoing research projects of participants and related recent progress within theoretical computer science. Attendees are expected to present their research or some (recent) exciting results, and follow-up discussion is expected. The seminar starts with pizza at 12:00, which will be provided for the participants, followed by the actual talk at 12:20.

Past years are here.

Summer semester 2025

This semester, we plan again a mix of talks on new results of the participants and expositions of recent papers in TCS by students. The first seminar will take place on February 25th, 2024.

20. 5. 2025

Vít Jelínek: The hierarchy of hereditary sorting operators

I will consider the following general model of sorting: we first fix a set of permutations C, which corresponds to the operations that we allow to perform in a single step. We then obtain as input a permutation P of the set [n]={1,2,...,n}. In every step, we pick a permutation S of length n from C, and rearrange the current permutation of numbers by composing it with S. The goal is to transform P into the sorted sequence 1,2,...,n in as few steps as possible. The minimum number of steps needed to sort P is the C-sorting time of P, and the maximum C-sorting time over all permutations P of [n] is the worst-case C-sorting time, denoted wst(C;n).

The goal is to classify the possible asymptotic behaviors of wst(C;n) when C is a hereditary permutation class (that is, a set of permutations closed under taking subpermutations), and understand which structural properties of C affect the asymptotics of wst(C;n).

The talk will be based on my joint work with Michal Opler and Jakub Pekárek.

13. 5. 2025

Jamie Fravel: Integer programming and redistricting

I will talk about using integer programming for redistricting, proving idealness of rectangle packing formulations, and continuous equality knapsack.

6. 5. 2025

Petr Gregor: Generating all invertible matrices by row operations

We show that all invertible n x n matrices over any finite field Fq can be generated in a Gray code fashion. More specifically, there exists a listing such that (1) each matrix appears exactly once, and (2) two consecutive matrices differ by adding or subtracting one row from a previous or subsequent row, or by multiplying or dividing a row by the generator of the multiplicative group of Fq. This even holds in the more general setting where the pairs of rows that can be added or subtracted are specified by an arbitrary transition tree that has to satisfy some mild constraints. Moreover, we can prescribe the first and the last matrix if n>=3, or n=2 and q>2. In other words, the corresponding flip graph on all invertible n x n matrices over Fq is Hamilton connected if it is not a cycle. This solves yet another special case of Lovász conjecture on Hamiltonicity of vertex-transitive graphs.

Joint work with Hung Hoang, Arturo Merino and Ondřej Mička.

22. 4. 2025

Hanna Komlos (NYU): History Independence in Data Structures with Applications to External-Memory Dictionaries

A data structure is history independent if its internal representation reveals nothing about the history of operations beyond what can be determined from the current contents of the data structure. History independence has a rich history of study as a security guarantee, with the intent being to minimize risks incurred by a breach or audit. We will begin with an overview of history independence and its properties. Then, we will discuss recent work on producing history-independent versions of external-memory dictionaries. Because of the tension between amortization of work and history independence, such data structures have historically suffered from degraded bounds or employed complex workarounds. We identify the primitive underlying this issue -- dynamic partitioning -- and solve it directly to achieve intuitive constructions with optimal bounds. This paper appeared at PODS 2024 and is joint work with Michael Bender, Martin Farach-Colton, and Michael Goodrich.

15. 4. 2025

Daniel Skýpala presents: Gerth Stølting Brodal and Casper Moldrup Rysgaard: Pure Binary Finger Search Trees

We present dynamic binary search trees where each node only stores a value and pointers to its parent and its children. We denote such binary search trees pure binary search trees. Our structure supports finger searches in worst-case O(lg d) time, where d is the rank difference between the node given by the finger and the node found by the search. Inserting a new node with a successor or predecessor value for a node pointed to by a finger and deleting a node in the tree pointed to by a finger are supported in amortized O(1) time and worst-case O(lg n) time, where n is the number of nodes in the tree. The temporary working space during the operations is O(1) words. The result is obtained by an alternative representation of the red-black trees by Guibas and Sedgewick [FOCS 1978] that encodes bits of information in the tree structure, generalizing the encoding of 2-3-trees by Brown [IPL 1979], and rearranging the nodes in a red-black tree (“folding” left and right paths) such that the predecessor and successor of a node can always be found in worst-case constant time. The same time bounds can easily be obtained by, say, red-black trees and AVL trees augmented with pointers to the predecessor and successor of each node. The novelty of our result is that we store no extra information than the binary tree structure. The structure can be represented by two pointers per value, i.e., the same representation as a doubly linked list.

8. 4. 2025

Juraj Belohorec: On Extractability of the KZG Family of Polynomial Commitment Schemes

We present a unifying framework for proving the knowledge soundness of KZG-like polynomial commitment schemes, encompassing both univariate and multivariate variants. By conceptualizing the proof technique of Lipmaa, Parisella, and Siim for the univariate KZG scheme (EUROCRYPT 2024), we present tools and falsifiable hardness assumptions that permit black-box extraction of the multivariate KZG scheme. Central to our approach is the notion of a canonical Proof-of-Knowledge of a Polynomial (PoKoP) of a polynomial commitment scheme, which we use to capture the extractability notion required in constructions of practical zk-SNARKs. We further present an explicit polynomial decomposition lemma for multivariate polynomials, enabling a more direct analysis of interpolating extractors and bridging the gap between univariate and multivariate commitments. Our results provide the first standard-model proofs of extractability for the multivariate KZG scheme and many of its variants under falsifiable assumptions.

This is joint work with Pavel Dvořák, Charlotte Hoffmann, Pavel Hubáček, Kristýna Mašková, and Martin Pastyřík.

1. 4. 2025

Ian Mertz: The Tree Evaluation Problem

We introduce the Tree Evaluation Problem, give context for its introduction and intuition as a hard problem for space, and recap last week's discussion of how it was used by Williams in his recent breakthrough result. We then discuss a recent algorithm by James Cook and me for solving TEP in low space.

25. 3. 2025

Petr Chmel presents: Ryan Williams: Simulating Time in Square-Root Space

We show that for all functions t(n) >= n, every multitape Turing machine running in time t can be simulated in space only O(sqrt(t log t)). This is a substantial improvement over Hopcroft, Paul, and Valiant's simulation of time t in O(t/log t) space from 50 years ago [FOCS 1975, JACM 1977]. Among other results, our simulation implies that bounded fan-in circuits of size s can be evaluated on any input in only sqrt(s) * poly(log s) space, and that there are explicit problems solvable in O(n) space which require n^(2-epsilon) time on a multitape Turing machine for all epsilon>0, thereby making a little progress on the P versus PSPACE problem.

Our simulation reduces the problem of simulating time-bounded multitape Turing machines to a series of implicitly-defined Tree Evaluation instances with nice parameters, leveraging the remarkable space-efficient algorithm for Tree Evaluation recently found by Cook and Mertz [STOC 2024].

18. 3. 2025

Dmitri Maslov (Google): What is worth solving on a quantum computer?

Quantum computing offers an asymptotic advantage in solving certain kinds of computational problems.  But which problems are these and how large a quantum computer needs to be to solve a classically untractable instance of such a problem?  The answer is less obvious than it may seem.  In this talk, I will discuss two problems.  Both were shown to likely be difficult for a classical computer via complexity-theoretic reductions.  The first is a type of instantaneous quantum polynomial time computation which was believed to be impractical to simulate classically but turned out to be simulable by classical means.  I will focus on discussing the classical simulation.  The second is an instance of a Hamiltonian dynamics simulation problem.  For this problem, I will discuss how to choose an ensemble of problems likely containing classically intractable instances while minimizing the quantum resources used to solve those on a quantum computer.

11. 3. 2025

Sudatta Bhattacharya: Embeddings on string similarity measures

This talk combines results from two papers on metric embeddings between string similarity measures—namely, Hamming, edit, and indel distances. Although the edit and indel metrics are very similar, while many algorithms exist for edit distance, much less is known for indel distance. A good transformation from edit to indel would allow the extensive algorithmic toolkit for edit distance to be applied to indel distance as well. While Tiskin provided a simple embedding from edit to indel, the opposite embedding—from indel to edit—remained unknown. Motivated by this gap, we demonstrate a transformation from indel to edit distance, and we also show that problems over arbitrary alphabets can be reduced to the binary setting.

Building on these insights, we construct an isometric embedding from the n-dimensional Hamming space to the N-dimensional edit space with a constant rate by leveraging synchronization strings from insertion-deletion coding. This result improves lower bounds for several problems in the edit metric, including the closest pair, discrete 1-center, clustering, and Steiner tree problems. By using our novel framework, based on misaligners, we have improved the rate to 1/8 and may even lead to embeddings with rates as high as 1/5 with further computational advances.

4. 3. 2025

Pavel Veselý: SplineSketch: Even More Accurate Quantiles with Error Guarantees

We focus on streaming algorithms, or data sketches, for characterizing the data distribution by approximating ranks and quantiles. We highlight the theoretical advancements that have led to optimal or near-optimal algorithms, such as the KLL sketch. However, practitioners often use other sketches that perform significantly better in practice despite lacking error guarantees. Most notably, t-digest has been widely adopted by major tech companies and open source projects, although its accuracy can degrade arbitrarily on adversarial data. Drawing inspiration from both theoretical and practical approaches, we present a new quantile summary, called SplineSketch, that achieves the best of both worlds: It provides near-optimal error guarantees in both streaming and distributed settings, while significantly outperforming all other quantile sketches on synthetic and real-world datasets.

25. 2. 2025

Onřej Čepek: Minimal representations of Horn Boolean functions

CNF representations of Boolean functions play an important role in many areas of computer science. Given a CNF, a natural optimization problem
(sometimes called Boolean minimization problem) is to find a shortest CNF which represents the same Boolean function. This problem is computationally
intractable in general, and it is hard even for many subclasses of Boolean functions. In this talk we will first survey known results about the complexity
of Boolean minimization for the class of Horn functions. We will study several ways how the size of the representation can be measured and concentrate on a 
measure which is not natural for CNFs but comes from the representation of Horn functions as directed hypergraphs or equivalently as implication systems.
For this measure the Horn minimization problem is known to be solvable in polynomial time. In the main part of the talk we will present new structural
results concerning this specific Horn minimization problem.

Winter semester 2024

This semester, we plan again a mix of talks on new results of the participants and expositions of recent papers in TCS by students. The first seminar will take place on October 8, 2024.

7. 1. 2025

Jiří Fink: Generating combinatorial objects online using linear programming

Recently, Arturo Merino and Torsten Mütze presented a new framework that exploits combinatorial optimization for efficiently generating a large variety of combinatorial objects based on graphs, matroids, posets, and polytopes. Their method is based on a simple and versatile algorithm for computing a Hamilton path on the skeleton of a 0/1-polytope conv(X), where X \subseteq { 0, 1}^n. The algorithm uses as a black box any algorithm that solves a variant of the classical linear optimization problem min{ w x | x \in X} , and the resulting delay, i.e., the running time per visited vertex on the Hamilton path, is larger than the running time of the optimization algorithm only by a factor of log n.

When X encodes a particular class of combinatorial objects, then traversing the skeleton of the polytope conv(X) along a Hamilton path corresponds to listing the combinatorial objects by local change operations; i.e., we obtain Gray code listings. As concrete results of their general framework, they obtained efficient algorithms for generating all (c-optimal) bases and independent sets in a matroid; (c-optimal) spanning trees, forests, matchings, maximum matchings, and c-optimal matchings in a graph; vertex covers, minimum vertex covers, c-optimal vertex covers, stable sets, maximum stable sets, and c-optimal stable sets in a bipartite graph; as well as antichains, maximum antichains, c-optimal antichains, and c-optimal ideals of a poset. Specifically, the delay and space required by these algorithms are polynomial in the size of the matroid ground set, graph, or poset, respectively.

Furthermore, all of these listings correspond to Hamilton paths on the corresponding combinatorial polytopes, namely the base polytope, matching polytope, vertex cover polytope, stable set polytope, chain polytope, and order polytope, respectively. As another corollary, they obtained an O(t_{LP} log n) delay algorithm for the vertex enumeration problem on 0/1-polytopes { x \in R^n | Ax <= b} where t_{LP} is the time needed to solve the linear program min{ w  x | Ax <= b}. This improves upon the 25-year-old O(t_{LP} n) delay algorithm due to Bussieck and Luebbecke.

In my talk, I will show you how to further improve the running time of the algorithm by Merino and Mütze by a log(n) factor. That is, we obtain an O(t_{LP}) delay algorithm for the vertex enumeration. For a set of combinatorial objects X, we only need to run the optimization algorithm four times to visit one object of X.

17. 12. 2024

Václav Rozhoň (INSAIT, Sofia): Beyond-worst-case graph algorithms and data structures

We will discuss some recent progress on fundamental problems in graph algorithms like the problem of ordering vertices by their distance from the source. We will design algorithms with strong beyond-worst-case guarantees by running classical algorithms with beyond-worst-case heaps. 

This motivates the problem of constructing the best possible beyond-worst-case heap and we will discuss some recent progress there. 

Joint work with Bernhard Haeupler, Richard Hladík, John Iacono, Robert Tarjan, Jakub Tětek.

10. 12. 2024

Michal Koucký: Nearly Optimal List Labeling

The list-labeling problem captures the basic task of storing a dynamically changing set of up to n elements in sorted order in an array of size m = (1+Θ(1))n. The goal is to support insertions and deletions while moving around elements within the array as little as possible. In this talk I will present an algorithm with amortized expected cost O(log n polyloglog n). This improves on the recent breakthrough of Bender et al. (2022) who gave an algorithm with amortized expected cost O(log^3/2 n). The amortized expected cost almost matches the Ω(log n) lower bound of Bulánek et al. (2013) for randomized algorithms.

Joint work with Michael Bender, Alex Conway, Martín Farach-Colton, Hanna Komlós, William Kuszmaul and Mike Saks.

3. 12. 2024

Martin Koutecký: What's New in (Block-Structured) Integer Programming

I will survey some old and new results about integer programming, especially my recent results about scaling algorithms [submitted], and algorithms which can handle large coefficients [SODA '24], with a particular emphasis on open problems. Joint work with Christoph Hunkenschröder, Asaf Levin, and Tung Anh Vu [scaling], Jana Cslovjecsek, Adam Polak, Alexandra Lassota, and Michal Pilipczuk [coefficients].

26. 11. 2024

Ian Mertz: Catalytic Computing: A Primer

Can memory be useful even when it's already full? In the catalytic computing model (Buhrman et al. 2014), we consider a space bounded Turing machine with additional access to a much larger hard drive, with the caveat that the initial contents of this extra space must be restored after any computation. Despite this restriction, catalytic computation gains surprising power over ordinary space-bounded computation, even above and beyond resources such as randomness and non-determinism.

In this talk we will survey the field of catalytic computation. We will cover the base catalytic model and where it fits into traditional complexity theory; variants of the model, such as lossy, non-uniform, and randomized catalytic computation; known techniques, such as register programs and compress-or-random approaches; applications of catalytic ideas to other computing models; and potential directions for the future of the field.

19. 11. 2024

Pavel Dvořák: Exponential Separation Between Powers of Regular and General Resolution Over Parities

Proving super-polynomial lower bounds on the size of proofs of unsatisfiability of Boolean formulas using resolution over parities has recently received a lot of attention. Efremenko, Garlík, and Itsykson [STOC '24] proved the first exponential lower bounds on the size of ResLin proofs that were additionally restricted to be bottom-regular. We show that there are formulas for which such regular ResLin proofs of unsatisfiability continue to have exponential size even though there exist short proofs of their unsatisfiability in ordinary, non-regular resolution. This is the first super-polynomial separation between the power of general ResLin and that of regular ResLin for any natural notion of regularity.

This is joint work with Sreejata Bhattacharya and Arkadev Chattopadhyay.

12. 11. 2024

Josef Tkadlec: Fixation times of the Moran process

Moran process is a classic random process that models the competition of two types of individuals on a network-structured population. The individuals reproduce, the offspring migrate along the edges of the network, and they replace the neighbors. In the absence of mutation, one of the types eventually triumphs over the whole network. We survey the existing results on the time (that is, the number of steps of the Moran process) until this occurs. We consider various regimes (directed vs. undirected networks, neutral vs. strong selection, Birth-death vs. death-Birth updating) and highlight some outstanding open questions.

5. 11. 2024

Hongxun Wu (UC Berkeley): Relative error streaming quantiles via resizable sketches

Given a stream of elements arriving online with total order, how can we approximate the rank of an element x in this stream with an multiplicative error of eps*rank(x), while maintaining only a small number of elements in memory at any time? This problem, known as the relative error streaming quantiles problem, has numerous applications in areas like database systems, network measurement, and beyond.

In this work, we investigate the optimal space complexity for this problem. The state-of-the-art algorithm by (Cormode, Karnin, Liberty, Thaler, Veselý, 2021) requires storing (log^1.5 (eps * n)) / eps elements in memory, while the trivial lower bound is (log (eps * n)) / eps . We close this gap (up to lower-order factors)  by designing an algorithm that nearly matches the trivial lower bound. Interestingly, a key innovation in our paper is the use of resizable sketches, which dynamically adjust their space usage based on demand. This flexibility allows us to adaptively compress and expand different components of the algorithm, significantly reducing overall space consumption.

29. 10. 2024

CANCELED: Kids school break

22. 10. 2024

Aleksander Łukasiewicz: Invitation to noisy searching

The classical binary search can be interpreted as an optimal solution for the following game: the adversary comes up with an unknown number $x$ from $1$ to $n$ (think of it as an index in a sorted array) and we have to find $x$ using questions of the form “is $x \leq k$?”. The proposed setting becomes more interesting (and challenging) when we allow some of the answers to be faulty (noisy). Different kinds of faults in different contexts can be considered. The first questions of this kind were posed by Alfréd Rényi in 1961 and were later independently rediscovered by Ulam (1976). Since then a long and wide
line of work has followed - however, even after several decades of research, we do not fully understand the entire landscape.

In this talk I will focus on searching in the sorted array and on a related problem of searching for an unknown vertex in a graph. We will consider a model where each reply is faulty independently and with probability $0 \leq p < 1/2$. Since the algorithms in that area tend to be rather simple and the main challenge usually lies in the analysis (which can become very technical), I will mainly cover general techniques and intuitions that arise in the design of noisy searching algorithms. To that end, I will talk about both classical results and more modern ones, including techniques developed in the papers I 
co-authored in the last few years.

If time permits, I will briefly touch on other models of faults, such as permanent stochastic noise, as well as other related problems, like noisy sorting. I will also share some of the open problems I am aware of.

15. 10. 2024

Jakub Tětek (INSAIT): Testing Identity of Continuous Distributions in Polylogarithmic Space

Suppose we have a sample from a distribution $D$ and we want to test whether $D = D^*$ for a fixed distribution $D^*$. Specifically, we want to reject with constant probability, if the distance of $D$ from $D^*$ is $\geq \eps$ in a given metric. In the case of continuous distributions, this has been studied thoroughly in the statistics literature. Namely, for the well-studied Kolmogorov--Smirnov metric a test is known that uses the optimal $O(1/\eps^2)$ samples.

However, this test naively uses also space $O(1/\eps^2)$, and previous work improved this to $O(1/\eps)$. In this paper, we show that much less space suffices -- we give an algorithm that uses space $O(\log^4 \eps^{-1})$ in the streaming setting while also using an asymptotically optimal number of samples. This is in contrast with the standard total variation distance on discrete distributions for which such space reduction is known to be impossible.

In the paper, we state 9 related open problems that we hope will spark interest in this and related problems. These open problems are especially suitable for students as they do not require extensive background knowledge.

8. 10. 2024

Petr Kolman: O(\Delta \log^{3/2} n)-approximation of the Spanning Tree Congestion

The Spanning Tree Congestion problem is an easy-to-state NP-hard problem: given a graph G, construct a spanning tree T of G minimizing its maximum edge congestion where the congestion of an edge e \in T is the number of edges uv in G such that the unique path between u and v in T passes through e; the optimum value for a given graph G is denoted \STC(G).

It is known that every spanning tree is an n/2-approximation but no o(n)-approximation algorithm is known for the problem. In the talk we will describe a new simple O(\Delta \log^{3/2} n)-approximation where \Delta is the maximum degree of the graph.

Our main tool for the analysis of the algorithm is a new lower bound on the spanning tree congestion which is of independent interest. We prove that for every graph G, \STC(G) \geq \Omega(hb(G)/\Delta) where hb(G) denotes the maximum bisection width over all subgraphs of G.

Spring semester 2024

This semester, we plan again a mix of talks on new results of the participants and expositions of recent papers in TCS by students. The first seminar will take place on February 20, 2024.

Next program

Papers to be covered

Calvin Beideman, Karthekeyan Chandrasekaran, Weihang Wang: Approximate minimum cuts and their enumeration. SOSA 2023.

Li Chen, Rasmus Kyng, Maximilian Probst Gutenberg, Sushant Sachdeva: A Simple Framework for Finding Balanced Sparse Cuts via APSP. SOSA 2023.

Joakim Blikstad, Ola Svensson, Radu Vintan, David Wajc: Simple and Asymptotically Optimal Online Bipartite Edge Coloring. SOSA 2024.

Alexander Golovnev, Siyao Guo, Spencer Peters, Noah Stephens-Davidowitz: Revisiting Time-Space Tradeoffs for Function Inversion. CRYPTO 2023.

Previous program

7. 5. 2024

Josef Minařík: Speed-robust scheduling revisited

Speed-robust scheduling is the following two-stage problem of scheduling $n$ jobs on $m$ uniformly related machines. In the first stage, the algorithm receives the value of $m$ and the processing times of $n$ jobs; it has to partition the jobs into $b$ groups called bags. In the second stage, the machine speeds are revealed and the bags are assigned to the machines, i.e., the algorithm produces a schedule where all the jobs in the same bag are assigned to the same machine. The objective is to minimize the makespan (the length of the schedule). The algorithm is compared to the optimal schedule and it is called $\rho$-robust, if its makespan is always at most $\rho$ times the optimal one.

Our main result is an improved bound for equal jobs in case $b=m$. We give an upper bound of $1.6$. This improves previous bound of $1.8$ and it is almost tight in the light of previous lower bound of $1.58$. Second, for infinitesimally small jobs, we give tight upper and lower bounds for the case when $b\geq m$. This generalizes and simplifies the previous bounds for $b=m$. Finally, we introduce a new special case with relatively small jobs for which we give an algorithm whose robustness is close to that of infinitesimal jobs and thus gives better than $2$-robust for a large class of inputs.

Joint work with Jiří Sgall.

30. 4. 2024

Michael A. Bender, Martín Farach-Colton, John Kuszmaul, William Kuszmaul: Modern Hashing Made Simple. SOSA 2024.
Presented by Tung Anh Vu

23. 4. 2024

Or Zamir: The Wrong Direction of Jensen's Inequality Is Algorithmically Right.ICALP 2023.
Presented by Petr Chmel

Let 𝒜 be an algorithm with expected running time e^X, conditioned on the value of some random variable X. We construct an algorithm A' with expected running time O (e^𝖤[X]), that fully executes 𝒜. In particular, an algorithm whose running time is a random variable T can be converted to one with expected running time O (e^𝖤[ln T]), which is never worse than O(𝖤[T]). No information about the distribution of X is required for the construction of 𝒜'.

16. 4. 2024

Foivos Fioravantes (FIT ČVUT): Parameterised complexity of forming coalitions of small size

Imagine we want to split a group of agents into teams in the most efficient way, considering that each agent has their own preferences about their teammates. This scenario is modeled by the extensively studied Coalition Formation problem. Here, we study a version of this problem where each team must additionally be of bounded size.

We conduct a systematic algorithmic study, providing several intractability results as well as multiple exact algorithms that scale well as the input grows (FPT), which could prove useful in practice. Our main contribution is an algorithm that deals efficiently with tree-like
structures (bounded treewidth) for "small" teams. We complement this result by proving that our algorithm is asymptotically optimal. Particularly, even considering star-like structures (bounded vertex cover number) cannot result in an algorithm with a better running time, under reasonable theoretical assumptions.

Joint work with Harmender Gahlawat and Nikolaos Melissinos.

9. 4. 2024

Pavel Hrubeš (Czech Academy of Sciences): Sum-of-squares composition formulas

A classical problem of Hurwitz asks for a characterisation of identities of the form (x_1^2+..+x_n^2)(y_1^2+...+y_m^2)= f_1^2+...+f_s^2, where f_1,...,f_s are bilinear in x and y. I will overview several aspects of this problem, including the elegant Hurwitz-Radon theorem, and discuss its connection to complexity theory

2. 4. 2024

Petr Kolman: Approximating Spanning Tree Congestion on Graphs with Polylog Degree

Given a graph $G$ and a spanning tree $T$ of $G$, the congestion of an edge $e\in E(T)$, with respect to $G$ and $T$, is the number of edges $uv$ in $G$ such that the unique path in $T$ connecting the vertices $u$ and $v$ traverses the edge $e$. Given a connected graph $G$, the {\em spanning tree congestion} problem is to construct a spanning tree $T$ that minimizes its maximum edge congestion.

It is known that the problem is NP-hard, and that {\em every} spanning tree is an $n/2$-approximation, but it is not even known whether an $o(n)$-approximation is possible in polynomial time; by $n$ we denote the number of vertices in the graph $G$.

We consider the problem on graphs with maximum degree bounded by $polylog(n)$ and describe an $o(n)$-approximation algorithm; note that even on this restricted class of graphs the spanning tree congestion can be of order $n\cdot polylog(n)$.

26. 3. 2024

Ian Mertz (Warwick University): How to Reuse Space

Space and time are two of the oldest and most fundamental resources in computer science, both in theory and in practice. However, the relationship between space and time efficiency—known in the language of complexity as L and P, respectively—has stood unresolved since the beginnings of the field.

The central candidate for showing the weakness of L, known as Tree Evaluation, relies on an idea known as composition: the intuitive belief that memory cannot serve two different purposes, such as storage and computation, at once. This strategy, of showing that two unrelated tasks are no easier done together than separately, is a long-standing technique in designing hard functions, and continues to be an active area of study in many different contexts.

In this talk we show that this logic fails in the world of space: memory can be used for both storage and computation at the same time, and thus, contrary to expectations, Tree Evaluation can in fact be solved nearly in L. We explore this new paradigm, which we term "reusing space", from existing techniques to potential connections throughout theoretical computer science.

19. 3. 2024

Vishwas Bhargava (University of Waterloo): Multivariate Multipoint Evaluation over Finite Fields

Polynomials are widely used throughout computer science, ranging from heavily applied algorithms in signal processing to purely theoretical endeavors in complexity theory. What makes polynomials so applicable across domains, and what are the fundamental problems linked with them? In this talk, we will address these questions.

The main focus of this talk is on Multivariate Multipoint Evaluation (MME), tackling the question: How can we efficiently evaluate a multivariate polynomial with N coefficients at N different points? A straightforward quadratic (N^2 time) algorithm involves iteratively evaluating the polynomial at each input. Obtaining faster algorithms than the naive approach (ideally nearly linear, i.e., N^{1+o(1)} time) for this problem is a natural problem in computational algebra and is a direct generalization of the Discrete Fourier Transform! Furthermore, fast algorithms for multipoint evaluation have implications for polynomial factorization, matrix rigidity, and modular composition. We will discuss recent progress, including a complete resolution of the MME problem over finite fields.

We will conclude by providing a broad overview of the exciting applications of polynomials in various domains and exploring some interesting research directions related to the theme of algebraic methods.

12. 3. 2024

Richard Hladík (ETH): Universal optimality in graph problems via beyond-worst-case heaps

In this talk, we will discuss how beyond-worst-case heaps lead to new insights about decades-old graph problems. We first consider the problem of sorting a set of items having an unknown total order by doing binary comparisons of the items, given the outcomes of some pre-existing comparisons. We present a simple algorithm with a running time of O(m + n + lg T), where n, m, and T are the number of items, the number of pre-existing comparisons, and the number of total orders consistent with the outcomes of the pre-existing comparisons, respectively. The algorithm does O(lg T) comparisons. Our time and comparison bounds are the best possible up to constant factors. The best previous algorithm with a bound of O(lg T) on the number of comparisons has a time bound of O(n^2.5 + lg T) and is much more complicated. Our algorithm uses heaps with a certain beyond-worst-case property, analogous to the working set property of splay trees.

We then shift our attention to Dijkstra's algorithm and the problem of listing vertices of a weighted graph in the order of their distance from a source vertex. Using the exact same techniques, we show that Dijkstra's algorithm paired with a heap with the working set property is universally optimal for this problem. Universal optimality is a powerful beyond-worst-case performance guarantee for graph algorithms that informally states that a single algorithm performs as well as possible for every single graph topology. Our first result can also be viewed through this lens.

Joint work with Bernhard Haeupler, John Iacono, Václav Rozhoň, Robert Tarjan, Jakub Tětek.

5. 3. 2024

Péter Hajnal, Zhihao Liu, György Turán: Nearest neighbor representations of Boolean functions. Information and Computation, vol. 285,  Part B, May 2022.
presented by Jelena Glišić

A nearest neighbor representation of a Boolean function is a set of positive and negative prototypes in Rnsuch that the function has value 1 on an input iff the closest prototype is positive. For k-nearest neighbor representation the majority classification of the kclosest prototypes is considered. The nearest neighbor complexity of a Boolean function is the minimal number of prototypes needed to represent the function. We give several bounds for this measure. Separations are given between the cases when prototypes can be real or are required to be Boolean. The complexity of parity is determined exactly. An exponential lower bound is given for mod 2 inner product, and a linear lower bound is given for its k-nearest neighbor complexity. The results are proven using connections to other models such as polynomial threshold functions over {1, 2}. We also discuss some of the many open problems arising.

27. 2. 2024

Josef Tkadlec: Amplifiers of selection for both Birth-death and death-Birth updating

Moran process is a classic discrete-time random process that models how entities such as opinions or viruses propagate through graphs. In each step, the current vertex coloring is updated according to a certain random rule. There are two versions of the Moran process called Birth-death updating and death-Birth updating. The two versions behave very differently. For example, under Birth-death updating many graphs function as so-called "amplifiers of selection", whereas for death-Birth updating only a handful of amplifiers are known. Curiously, none of those few death-Birth amplifiers are
amplifiers under Birth-death updating. In this work, we identify a new family of graphs that function as amplifiers under both versions of the Moran process.
Joint work with Jakub Svoboda, Soham Joshi, and Krishnendu Chatterjee.

20. 2. 2024

Jiří Fink: Matchings extend to long cycles in hypercubes

In 1993, Ruskey and Savage conjectured that every matching of the hypercube can be extended into a Hamilton cycle. The conjecture is known to be true if the matching is perfect or it has size at most a quadratic in the dimension. It is also known that every matching can be extended into a 2-factor. We will discuss how to extend a matching into a single cycle visiting at least 2/3-fraction of all vertices of the hypercube. The proof uses induction where the base case is computer assisted.
Joint work with Torsten Mütze

16. 1. 2024

Václav Rozhoň (ETH and MIT): Work-Efficient Parallel Derandomization: Chernoff-like Concentrations via Pairwise Independence

We present a novel technique for work-efficient parallel derandomization, for algorithms that rely on the concentration of measure bounds such as Chernoff, Hoeffding, and Bernstein inequalities. Our method increases the algorithm's computational work and depth by only polylogarithmic factors. Before our work, the only known method to obtain parallel derandomization with such strong concentrations was by the results of [Motwani, Naor, and Naor FOCS'89; Berger and Rompel FOCS'89], which perform a binary search in a $k$-wise independent space for $k=\poly(\log n)$. However, that method blows up the computational work by a high $\poly(n)$ factor and does not yield work-efficient parallel algorithms. Their method was an extension of the approach of [Luby FOCS'88], which gave a work-efficient derandomization but was limited to algorithms analyzed with only pairwise independence. Pushing the method from pairwise to the higher $k$-wise analysis resulted in the $\poly(n)$ factor computational work blow-up. Our work can be viewed as an alternative extension from the pairwise case, which yields the desired strong concentrations while retaining work efficiency up to logarithmic factors.

Our approach works by casting the problem of determining the random variables as an iterative process with $\poly(\log n)$ iterations, where different iterations have independent randomness. This is done so that for the desired concentrations, we need only pairwise independence inside each iteration. In particular, we model each binary random variable as a result of a gradual random walk, and our method shows that the desired Chernoff-like concentrations about the endpoints of these walks can be boiled down to some pairwise analysis on the steps of these random walks in each iteration (while having independence across iterations). Hence, we can fix the randomness of each iteration efficiently before proceeding to the next.

Joint work with Mohsen Ghaffari, Christoph Grunau (FOCS 2023).

9. 1. 2024

Dmytro Gavinski (Czech Academy of Sciences): Patterned non-determinism in communication complexity

19. 12. 2023

Chakraborty, Vinodchandran, Meel: Distinct Elements in Streams: An Algorithm for the (Text) Book. ESA 2022.
presented by Nicolaos Matsakis

Given a data stream A=⟨a_1,a_2,…,a_m⟩ of m elements where each a_i∈[n], the Distinct Elements problem is to estimate the number of distinct elements in A.Distinct Elements has been a subject of theoretical and empirical investigations over the past four decades resulting in space optimal algorithms for it. All the current state-of-the-art algorithms are, however, beyond the reach of an undergraduate textbook owing to their reliance on the usage of notions such as pairwise independence and universal hash functions. We present a simple, intuitive, sampling-based space-efficient algorithm whose description and the proof are accessible to undergraduates with the knowledge of basic probability theory.

12. 12. 2023

Ninad Rajgopal (U. of Warwick): On the Power of Interactive Proofs for Learning

We study interactive proof systems for verifying the results of agnostic learning tasks, which was recently initiated by Goldwasser, Rothblum, Shafer and Yehudayoff [GRSY21], as PAC-verification. Here, for a given target hypothesis class H and for any unknown n-variate Boolean function f, the verifier who only gets random example access to f (over the uniform distribution) interacts with an untrusted prover who has query access to f, to output a hypothesis that is as close to f as an optimal hypothesis from H, up to a small error. Such proof systems enable a verifier to delegate an agnostic learning task to an untrusted prover, with the goal being one of verification using much fewer random examples and/or running time, than actually performing learning (using queries) from scratch. Typically, we require such interactive proofs to be doubly efficient, where the honest prover is also an efficient algorithm.

In this paper, we study delegation of learning for certain Boolean hypothesis classes that are central to learning theory. Firstly, we show an interactive proof for learning all the \eps-heavy Fourier coefficients of a function using poly(1/\eps) many examples (i.e., Goldreich-Levin theorem), whereas the prover uses poly(n/\eps) many membership queries, giving a verification speed-up that is independent of the input length n. We also show a similar input-independent separation for the hypothesis class of all k-Juntas. Next, we show such interactive proofs for learning the class AC^0[2] building on the work by Carmosino-Impagliazzo-Kabanets-Kolokolova [CIKK17], where the verifier uses quasi-polynomially many random examples. In contrast, this class has been notoriously resistant beyond trivial brute force learning, even for constructing realisable learners (without a prover) using random examples. Finally, we show that if we do not insist on doubly-efficient proof systems, then the model becomes trivial; even P/Poly can be learnt using O(1) many examples.

This is joint work with Tom Gur, Mohammad Mahdi Jahanara, Mohammad Mahdi Khodabandeh, Bahar Salamatian, and Igor Shinkar.

5. 12. 2023

Tomáš Hons: Structural limits and inverse problems
The theory of graph convergence and limits was developed for study of large graphs. Inspired by analysis, the idea is to assign a certain limit object to a sequence of growing graphs that captures important properties of the sequence. However, when seeking the right definition of the limit object, the following inverse problem needs to be considered: given a limit object L (i.e. satisfying the definition), is there a sequence of graphs that converges to L? In the talk, we introduce several notions of graph convergence, the corresponding limit objects, and the state of their inverse problem. Moreover, we mention a certain simplified question that deals with approximation of vertices within a limit instead of the limit itself.

David Mikšaník: Coloring graphs with bounded clique number
A well-known theorem of Brooks states that a graph G of maximum degree Delta≥3 can be colored by Delta colors unless G contains a clique of size Delta+1. It is natural to ask what additional assumptions guarantee that G can be colored with Delta-1 colors. Borodin and Kostochka (1976) conjectured that when Delta≥9, it is sufficient to assume only that G does not contain a clique of size Delta. In 1999, Reed showed that this conjecture holds for graphs with maximum degree at least 10^14.
In this talk, I will suggest possible ways to improve Reed's result by decreasing the constant 10^14 to hundreds or lower. This topic is part of my dissertation thesis and this year's GAUK grant proposal, both under the supervision of Zdeněk Dvořák.

28. 11. 2023

Max Deppert, Matthias Kaul, Matthias Mnich: A (3/2 + ε)-Approximation for Multiple TSP with a Variable Number of Depots. ESA 2023.
presented by Petr Martínek

One of the most studied extensions of the famous Traveling Salesperson Problem (TSP) is the Multiple TSP: a set of m ≥ 1 salespersons collectively traverses a set of n cities by m non-trivial tours to minimize the total length of their tours. This problem can also be considered to be a variant of Uncapacitated Vehicle Routing, where the objective is to minimize the sum of all tour lengths. When all m tours start from and end at a single common depot, then the metric Multiple TSP can be approximated equally well as the standard metric TSP, as shown by Frieze (1983). The metric Multiple TSP becomes significantly harder to approximate when there is a set D of d ≥ 1 depots that form the starting and end points of the m tours. This paper gives the first efficient approximation algorithm for Multiple TSP with a variable number d of depots that yields a better-than-2 approximation. Their algorithm runs in time (1/ε)^O(dlog d) ⋅ n^O(1), and produces a (3/2+ε)-approximation with constant probability. For the graphic case, they obtain a deterministic 3/2-approximation in time 2^d ⋅ n^O(1).

21. 11. 2023

Arturo Merino (U. Saarland): Traversing combinatorial polytopes via optimization

We present a new framework that exploits combinatorial optimization for efficiently generating a large variety of combinatorial objects based on graphs, matroids, posets, and polytopes. Our method relies on a simple and versatile algorithm for computing a Hamilton path on the skeleton of any 0/1-polytope conv(X), where X ⊆ {0,1}^n. The algorithm uses as a black box any algorithm that solves the classical linear optimization problem, and the resulting delay, i.e., the running time per visited vertex on the Hamilton path, is only a polylogarithmic factor larger than the running time of the optimization algorithm. When X encodes a particular class of combinatorial objects, then traversing the skeleton of the polytope conv(X) along a Hamilton path corresponds to listing the combinatorial objects by local change operations, i.e., we obtain Gray code listings.

As a concrete example application of our framework, we obtain an O(T⋅log n) delay algorithm for the vertex enumeration problem on 0/1 polytopes, where T is the time needed to solve a linear program and n is the dimension of the polytope. This improves upon the 25-year-old O(T⋅n) delay algorithm due to Bussieck and Lübbecke.

This is joint work with Torsten Mütze (U. of Warwick).

14. 11. 2023

Emmett Breen, Renee Mirka, Zichen Wang, David P. Williamson: Revisiting Garg's 2-Approximation Algorithm for the k-MST Problem in Graphs. SOSA 2023.
presented by Josef Matějka

Garg (STOC'05) gave a polynomial-time 2-approximation algorithm for finding a Minimum Spanning Tree spanning k vertices (k-MST). This paper greatly simplifies the algorithm to achieve Garg's result.

7. 11. 2023

Charlotte Hoffmann (ISTA): Certifying Giant Nonprimes

GIMPS and PrimeGrid are large-scale distributed projects dedicated to searching giant prime numbers, usually of special forms like Mersenne and Proth primes. The numbers in the current search-space are millions of digits large and the participating volunteers need to run resource-consuming primality tests. Once a candidate prime N has been found, the only way for another party to independently verify the primality of N used to be by repeating the expensive primality test. To avoid the need for a second recomputation of each primality test, these projects have recently adopted certifying mechanisms that enable efficient verification of performed tests. However, the mechanisms presently in place only detect benign errors and there is no guarantee against adversarial behavior: a malicious volunteer can mislead the project to reject a giant prime as being non-prime.

In this talk, I will present a practical, cryptographically-sound mechanism for certifying the non-primality of Proth numbers. That is, a volunteer can – parallel to running the primality test for N – generate an efficiently verifiable proof at a little extra cost, certifying that N is not prime.

Joint work with Pavel Hubáček, Chethan Kamath, and Krzysztof Pietrzak.

31. 10. 2023

Pavel Veselý (CUNI): Massively Parallel Algorithms for Clustering in High Dimension

We discuss algorithms for k-Median and k-Means clustering in high-dimensional Euclidean spaces that run in the Massively Parallel Computation (MPC) model, which captures key aspects of MapReduce-style frameworks. In MPC, we have a set of machines, each with a local memory that is sublinear in the input size, and computation proceeds in alternating rounds of communication and sequential (but local) computation. We focus on the fully scalable case in which the local memory may be substantially smaller than the number of clusters k. We present new algorithms that take O(1) rounds and achieve O(1)-bicriteria approximation (meaning we output O(k) clusters), improving upon a polylogarithmic approximation. Our approach relies on a connection between k-clustering and Facility Location, for which we design an MPC O(1)-round O(1)-approximation.

Joint work with Artur Czumaj, Guichen Gao, Shaofeng H.-C. Jiang, and Robert Krauthgamer.

24. 10. 2023

Tomasz Kociumaka, Adam Polak: Bellman-Ford Is Optimal for Shortest Hop-Bounded Paths. ESA 2023.
presented by Jelena Glišić

This paper is about the problem of finding a shortest s-t path using at most h edges in edge-weighted graphs. The Bellman-Ford algorithm solves this problem in O(hm) time, where m is the number of edges. We show that this running time is optimal, up to subpolynomial factors, under popular fine-grained complexity assumptions. More specifically, we show that under the APSP Hypothesis the problem cannot be solved faster already in undirected graphs with nonnegative edge weights. This lower bound holds even restricted to graphs of arbitrary density and for arbitrary h ∈ O(√m). Moreover, under a stronger assumption, namely the Min-Plus Convolution Hypothesis, we can eliminate the restriction h ∈ O(√m). In other words, the O(hm) bound is tight for the entire space of parameters h, m, and n, where n is the number of nodes. Our lower bounds can be contrasted with the recent near-linear time algorithm for the negative-weight Single-Source Shortest Paths problem, which is the textbook application of the Bellman-Ford algorithm.

17. 10. 2023 - CANCELLED

10. 10. 2023

Petr Kučera (CUNI): Binary Constraint Trees and Structural Decomposability

A binary constraint tree (BCT, Wang and Yap 2022) is a normalized binary CSP whose constraint graph is a tree. A BCT constraint is a constraint represented with a BCT where some of the variables may be hidden (i.e. existentially quantified and used only for internal representation). Structured decomposable negation normal forms (SDNNF) were introduced by Pipatsrisawat and Darwiche (2008) as a restriction of decomposable negation normal forms (DNNF). Both DNNFs and SDNNFs were studied in the area of knowledge compilation. In this paper we show that the BCT constraints are polynomially equivalent to SDNNFs. In particular, a BCT constraint can be represented with an SDNNF of polynomial size and, on the other hand, a constraint that can be represented with an SDNNF, can be represented as a BCT constraint of polynomial size. This generalizes the result of Wang and Yap (2022) that shows that a multivalued decision diagram (MDD) can be represented with a BCT. Moreover, our result provides a full characterization of binary constraint trees using a language that is well studied in the area of knowledge compilation. It was shown by Wang and Yap (2023) that a CSP on n variables of domain sizes bounded by d that has treewidth k can be encoded as a BCT on O(n) variables with domain sizes O(d^{k+1}). We provide an alternative reduction for the case of binary CSPs. This allows us to compile any binary CSP to an SDNNF of size that is parameterized by d and k.

3. 10. 2023

Luca Trevisan (Bocconi U.): Approximating Boolean Constraint Satisfaction Problems in Random, Semi-Random, and Worst-Case Instances

We know several techniques to round Semidefinite Programming relaxations of graph optimization problems and of Boolean constraint satisfaction problems in which each constraint involves at most two variables, and these rounding techniques lead to good approximation algorithms. For problems involving hyper-graphs, for Boolean constraint satisfaction problems with three or more variables per constraints, and for polynomial optimization problems with polynomials of degree higher than two, we lack techniques to round Semidefinite Programs (or other convex relaxations) or to analyze their average-case performance.
We present two new techniques to analyze random, semi-random and worst-case instances of problems such as Max 3SAT, Max 3XOR, and degree 3 polynomial optimization. One technique gives new bounds to certify unsatisfiability of random 3SAT and certified upper bounds for random Max 3XOR and for random instances of degree 3 polynomial optimization, and it extends to a certain semi-random generative model (in which instances are produced with a mix of random choices and worst- case choices). The other technique provides a new rounding scheme for worst-case instances of Max 3XOR and homogeneous degree 3 polynomial optimization.

Joint work with Tommaso D’Orsi, Tim Hsieh, Pravesh Kothari, and Lucas Pesenti