Ondřej Čepek, Andreas Feldmann, Pavel Hubáček, Petr Kolman, Michal Koucký, Jiří Sgall
`<koucky@iuuk.mff.cuni.cz>`

NTIN102 - 0/2 Z

**Time:** Tue 12:00-14:00.
**Place:** S8, Malá Strana.

A seminar that aims to refer on ongoing research projects of participants and related issues within the scope of theoretical computer science. Attendees are expected to present their research, follow-up discussion is expected. The seminar starts by pizza which will be provided for the participants.

**16. 5. 2023**

**Torsten Mütze (Charles U./Warwick U.): Kneser graphs are Hamiltonian**

**Abstract:**
For integers k>=1 and n>=2k+1, the Kneser graph K(n,k) has as vertices all k-element subsets of an n-element ground set, and an edge between any two disjoint sets. It has been conjectured since the 1970s that all Kneser graphs admit a Hamilton cycle, with one notable exception, namely the Petersen graph K(5,2). This problem received considerable attention in the literature, including a recent solution for the sparsest case n=2k+1. The main contribution of our work is to prove the conjecture in full generality. We also extend this Hamiltonicity result to all connected generalized Johnson graphs (except the Petersen graph). The generalized Johnson graph J(n,k,s) has as vertices all k-element subsets of an n-element ground set, and an edge between any two sets whose intersection has size exactly s. Clearly, we have K(n,k)=J(n,k,0), i.e., generalized Johnson graphs include Kneser graphs as a special case. Our results imply that all known families of vertex-transitive graphs defined by intersecting set systems have a Hamilton cycle, which settles an interesting special case of Lovász’ conjecture on Hamilton cycles in vertex-transitive graphs from 1970. Our main technical innovation is to study cycles in Kneser graphs by a kinetic system of multiple gliders that move at different speeds and that interact over time, reminiscent of the gliders in Conway’s Game of Life, and to analyze this system combinatorially and via linear algebra.

This is joint work with my students Arturo Merino (TU Berlin) and Namrata (Warwick).

**9. 5. 2023**

**Jan Kratochvíl: Where Topology Meets Computer Science, and Simple Means Difficult**
*(invited keynote talk at WALCOM 2023)*

**Abstract:**
Graph covers are locally bijective homomorphisms of graphs. The notion stems from topological graph theory, but it has found computer
science applications in models of local computation. We will review recent results on the computational complexity of graph covers and
comment on open problems and related mathematical questions. The punchline of the talk is how mathematical and computer science aspects
of this notion influence each other and inspire new open questions. The most prominent example is that complexity questions are leading
to considering generalization of snarks, a notion well known from and intensively studied in graph coloring.

**2. 5. 2023**

**Nick Matsakis: Better Approximations for Shortest Superstrings**

**Abstract:**
The Shortest Superstring problem is an NP-hard problem, in which given as
input a set of strings, we are looking for a string of minimum length that
contains all input strings as substrings. The Greedy Conjecture (Tarhio and
Ukkonen, 1988) states that the Greedy algorithm which repeatedly merges the
two strings of maximum overlap is 2-approximate. It has been shown by
Englert et al. (STOC 2022) that the approximation factor of Greedy is at
most 3.425. Beforehand, the best established upper bound for this was 3.5 by
Kaplan and Shafrir (IPL 2005), which improved upon the upper bound of 4 by
Blum et al. (STOC 1991). To derive their result, Englert et al. established
two incomparable upper bounds on the overlap sum of all cycle-closing edges
in an optimal cycle cover and utilized lemmas of Blum et al. Moreover, their
result implied an approximation guarantee of 2.475 for the Shortest
Superstring problem, improving upon the previously best guarantee of 2.478
by Mucha (SODA 2013).

We improve the two upper bounds of Englert et al. by establishing a further distinction of cycles according to an overlap to length ratio. This implies slightly improved approximation guarantees for both Greedy and the Shortest Superstring problem.

**25. 4. 2023**

**NO SEMINAR - Spring school**

**18. 4. 2023**

**Gilbert Maystre (EPFL): TFNP: Collapses, separations and characterisations**

**Abstract:**
In light of the surprising result CLS = PLS ∩ PPAD by Fearnley et. al. (STOC'21), one may wonder whether
further such collapses between TFNP subclasses are possible. In this talk, I will survey two recent sets of results
regarding that question. The first establishes in an elementary black-box manner that the collapse progresses even
further: it turns out that EOPL (a subclass of CLS) actually equals PLS ∩ PPAD too. A similar construction yields SOPL
= PLS ∩ PPADS. The second investigates barriers to such collapses, i.e. ruling out black-box reductions. By
characterising query-analogues of TFNP subclasses by proof systems, we show oracle separations between all classical
TFNP subclasses, eventually completing the picture initiated by Beame et al. (JCSS'98). Those separations also extend
to the newer class UEOPL (a subclass of EOPL), further showing that PLS ∩ PPAD does not reduce to UEOPL in a black-box
fashion and “stopping” the collapse.

Joint work with Mika Göös, Alexandros Hollender, Siddhartha Jain, William Pires, Robert Robere and Ran Tao.

**11. 4. 2023**

**Rump session**

**Abstract:**
Everyone is welcome to briefly present his favorite open problem, new result or idea.

**4. 4. 2023 - CANCELLED - rescheduled to 16. 5. 2023 **

**Torsten Mütze (Charles U./Warwick U.): Kneser graphs are Hamiltonian**

**28. 3. 2023**

**Milan Hladik: Theory of interval computing**

**Abstract:**
Interval computation means, roughly speaking, solving problems with interval input data. Interval data naturally appear in many
practical situations and they range from very tiny intervals (caused by roundoff errors), via medium-sized intervals (e.g., measurement
errors, various kinds of uncertainty) to very large intervals (constraint programming or global optimization). The paradigm of interval
computations is to take into account all possible values from the intervals and to provide mathematically rigorous and numerically safe
bounds and various properties checking.

In the lecture, we focus on selected problems from interval linear algebra, mostly interval linear equations. We discuss certain concepts of solutions and their applications. We present the characterization of the solution set, computational complexity results and highlight the mathematical techniques behind.

**21. 3. 2023**

**Ben Moore: On the strong nine dragon tree conjectures**

**Abstract:**
I'll discuss various progress on the strong nine dragon tree conjectures, and some possible applications to constant factor approximations to ATSP and Jaegers weak modulo orientation conjecture.

**14. 3. 2023**

**Pavel Hubáček: On Cryptographic Cheap Talk with Smart Contracts**

**Abstract:**
Protocols for implementing correlated equilibria without trusted mediation were studied extensively in both game
theoretical and cryptographic literature since the seminal work of Bárány (Math. Oper. Res. 1992). In my talk, I will
survey the known results in this area and present a novel simplified approach for implementing correlated equilibria
exploiting smart contracts on blockchains such as Ethereum.

Based on joint work with Michelle Yeo.

**7. 3. 2023**

**Pavel Veselý: Theory meets practice at textual k-mer set representations**

**Abstract:**
In this talk, we will discuss old and new approaches to representing a set of k-mers, which are k-long substrings contained within a biological sequence. In particular, I will present a new framework, called masked superstring of k-mers, based on the shortest superstring problem and unifying the previously developed concepts. We evaluate the framework from the lens of theory (computational complexity) and practice (efficient heuristics and their performance on real-world data). Based on joint work with Ondřej Sladký (MFF UK) and Karel Břinda (INRIA).

**28. 2. 2023**

**Zdeněk Dvořák: On a generalization of Alon-Tarsi method**

**Abstract:**
Alon-Tarsi method is a useful heuristic that can be used to prove that a graph can be colored from any assignment of lists of given size, when certain monomials appear with non-zero coefficients in the graph polynomial. A downside is that if the answer is negative, the method does not provide any further information (e.g., a list assignment from which the graph cannot be colored). I will show a generalization of Alon-Tarsi method that partially mitigates this issue, and present results of its practical evaluation.

**21. 2. 2023**

**Michal Koucký: Locally consistent decomposition of strings with applications to
edit distance sketching**

**Abstract:**
I will present a new decomposition of strings which preserves edit distance of strings.
This has applications to sketching of edit distance. Based on a joint work with Sudatta Bhattacharya.

**20. 12. 2022**

**Pavel Dvořák (TIFR/MFF): Sliding window algorithm for weighted matching**

**Abstract:**
I will talk about the maximum weighted matching problem in the streaming sliding window model. In this model, an algorithm receives the edges of a graph one by one. When an edge arrives,
the algorithm should output an approximation of the maximum weighted matching in a graph spanned by the last L edges, where L is a known parameter. The goal is to design an algorithm with
a small approximation factor using as small memory as possible. I will present two algorithms, a 3-approximation using O(n polylog n) memory and a 2-approximation using O(sqrt(nL))
memory.
This is joint work with Cezar-Mihail Alexandru, Christian Konrad, and Kheeran K. Naidu.

**13. 12. 2022**

**Pavel Pudlák (Math. Institute): On the problem of constructing tree codes**

**Abstract:**
In 1993 L. J. Schulman defined tree codes as a means for interactive communication. He proved the existence, but an explicit construction is still eluding. In this talk I will mention approaches based on constructing special matrices which would produce linear tree codes. I will present a property of matrices that suffices for a construction of tree codes and such that random matrices over polynomial size fields satisfy this property.

**6. 12. 2022**

**Pavel Hubáček: On Statistically Secure Proofs of Exponentiation in Arbitrary Groups**

**Abstract:**
Exponentiation of the form x^{2^T} in a group of unknown order serves as a source of *sequential* hardness in various modern cryptographic protocols. Roughly speaking, it is believed that
evaluating x^{2^T} without the knowledge of the order of the group takes at least T sequential multiplications irrespective of the available parallelism. Recent independent results by
Pietrzak (ITCS 2019) and Wesolowski (J. Cryptol. 2020) demonstrated interactive proof systems for correctness of such modular exponentiation with verification time O(log(T)) and O(1)
multiplications in specific groups or under some additional computational hardness assumptions (respectively). In this talk, I will explain the interactive proof of exponentiation of
Pietrzak and show how to extend it in order to achieve a statistical security guarantee, i.e., without relying on any computational hardness assumptions, in arbitrary group.

**29. 11. 2022**

**Matej Lieskovský: A graph burning algorithm**

**Abstract:**
In the graph burning problem, we are given a graph and are looking for the shortest possible sequence of vertices v_0, v_1, ... such that the balls B(v_i,i) (where the i-th ball is centered on v_i and has radius i) cover all vertices of the graph. This comes up, for example, in spreading information through a network. We present a randomized 2.314+epsilon-approximation algorithm, a significant improvement over the previous 3-approximation algorithm.

**22. 11. 2022**

**Dima Gavinsky (Math. Institute): Quantum vs. classical communication complexity: Some results and open problems**

**Abstract:**

**15. 11. 2022**

**Michal Koucký: Simple algorithms for Dyck edit distance**

**Abstract:**
Edit distance is a measure of similarity of two strings whereas Dyck edit distance measures the number of changes one needs to make to a parenthesized expression
to fix mismatched parenthesis. This comes up for example in parser error-recovery. It turns out there is an easy reduction of edit distance to Dyck edit distance.
In this talk I will show a relationship the other way around: I will show an approximate reduction of Dyck edit distance to edit distance. Based on a joint work with Mike Saks.

**8. 11. 2022**

**Pavel Veselý: Streaming Facility Location in High Dimension via Geometric Hashing**

**Abstract:**
We consider algorithms for dynamic geometric streams. In this setting, the input is a set of points from the Euclidean space R^d presented as a sequence of insertions and deletions. A streaming algorithm must process this stream of updates in a few passes (ideally just one) using polylogarithmic memory. We focus on the high-dimensional setting, in which the algorithm's space usage must be polynomial (and certainly not exponential) in dimension d.

We present a new algorithmic technique for Uniform Facility Location that breaks the barrier of logarithmic approximation using poly(d) space. Our approach relies on a geometric hashing scheme that maps points in R^d into buckets of bounded diameter, with the key property that every point set of small-enough diameter is hashed into at most poly(d) distinct buckets.

Joint work with Artur Czumaj, Shaofeng H.-C. Jiang, Robert Krauthgamer, and Mingwei Yang.

**1. 11. 2022**

**Petr Kolman: Length-bounded cuts and related problems: a report on stalled progress**

**Abstract:**
Given a graph G=(V,E) with two distinguished vertices s, t in V
and an integer parameter L>0, an *L-bounded cut* is a subset F of
edges such that every path between s and t in (V,E \ F) has
length at least L. The task is to find an L-bounded cut of minimum
cardinality.

This problem was first studied around 1970 but to this day is not well understood. For L >= 4, it is known to be NP-hard; the best known approximation, in terms of n=|V|, is O(n^{2/3}), while the strongest hardness result is \Omega(1) only.

In the talk, I plan to survey the main known results, explain connections of the problem to other optimization problems (length-bounded flow, hitting set, submodular function maximization) and sketch a few possible approaches to tackling the problem (divide and conquer, linear relaxation and clustering), which have not, however, yet been fruitful.**25. 10. 2022**

**Noam Mazor (Tel-Aviv University): Incompressiblity and Next-Block Pseudoentropy**

**Abstract:**

We advance towards a better understating of this notion, showing that a k-incompressible distribution has (k-2) bits of next-block pseudoentropy, a refinement of pseudoentropy introduced by Haitner, Reingold, and Vadhan [SICOMP ’13]. We deduce that a samplable distribution X that is (H(X) + 2)-incompressible, implies the existence of one-way functions.

Joint work with Iftach Haitner and Jad Silbak.

**18. 10. 2022**

**Libor Barto: Combinatorial Gap Theorem**

**Abstract:**
A value of a CSP instance is typically defined as a fraction of constraints that can be simultaneously met. We propose an alternative definition of a value of an instance and
show that, for purely combinatorial reasons, a value of an unsolvable instance is bounded away from one; we call this fact a gap theorem. We show that the gap theorem implies NP-hardness
of a gap version of the Layered Label Cover Problem. The same result can be derived from the PCP Theorem, but a full, self-contained proof of our reduction is quite short and the result
can still provide PCP–free NP–hardness proofs for numerous problems. The simplicity of our reasoning also suggests that weaker versions of UniqueGames-type conjectures, e.g., the d-to-1
conjecture, might be accessible and serve as an intermediate step for proving these conjectures in their full strength

This is a joint work with M. Kozik.

**11. 10. 2022**

**Zdeněk Dvořák: Representation of short distances in structurally sparse graphs**

**Abstract:**
A partial orientation H of a graph G is a weak r-guidance system if for any two
vertices at distance at most r in G, there exists a shortest path P between
them such that H directs all but one edge in P towards this edge. In case that
H has bounded maximum outdegree Delta, this gives an efficient representation
of shortest paths of length at most r in G: For any pair of vertices, we can
either determine the distance between them or decide the distance is more than
r, and in the former case, find a shortest path between them, in time
O(Delta^r). We show that graphs from many natural graph classes admit such
weak guidance systems, and study the algorithmic aspects of this notion. We
also apply the notion to obtain approximation algorithms for distance variants
of the independence and domination number in graph classes that admit weak
guidance systems of bounded maximum outdegree.

**4. 10. 2022**

**Cornelius Brand (TU Wien): A Polyhedral Perspective on Min,+ Convolutions**

**Abstract:**
(Min,+) convolution is a well-studied algorithmic primitive in
fine-grained complexity. In this talk, I will report on a connection between
polyhedral formulations and (min,+) convolution, through which one can
arrive at a combinatorial dual variant of (min,+) convolution. Further, I
will sketch how this dual operation is subquadratically equivalent to primal
convolutions, introduce some related polyhedra and talk about some of their
basic properties.

This is joint work in progress with Alexandra Lassota (EPFL) and Martin Koutecký.

**10. 5. 2022**

**Jakub Bulín: Finer complexity landscape of CSPs, and trees**

**Abstract:**
The CSP dichotomy theorem states that for every template A, CSP(A) is either in P or
NP-complete and provides a clear structural boundary between the two cases. We will discuss
the conjectured, equally nice finer classification of fixed template CSPs from the point of
view of computational complexity (membership in L and in NL, and mod_p L-hardness) and
descriptive complexity (co-definability in Datalog, linear Datalog, and linear symmetric
Datalog).

We will then focus on CSP(H) where H is a digraph (also known as the H-coloring problem) and, in particular, an orientation of a tree. We will discuss mathematical as well as experimental results towards confirming the L and NL conjectures for trees, and a conjectured collapse of the hierarchy: Is it true that tractable trees lack the ability to count?

The new results are recent joint work with Manuel Bodirsky, Florian Starke, and Michael Wernthaler.

**3. 5. 2022**

**No seminar due to Spring School**

**26. 4. 2022**

**Lukáš Ondráček: Cache-Oblivious Representation of Partially Dynamic Bounded-Arity Trees**

**Abstract:**
We present a data structure for storing rooted trees
with all leaves at the same depth
and vertices of arity between chosen constants a and b
in a cache-oblivious way.
It provides operations for inserting an a-ary subtree of forced depth
under a vertex of degree at most (b-1)
or removing a subtree under a vertex of degree at least (a+1).
The tree contains pointers to children, not parents,
and allows searching with an optimal I/O complexity O(\log_B N),
where N is the size of the tree.
Inserting and removing subtree of size S
is possible in an amortized time O(S⋅\log^2 N + \log N ⋅ \log\log N)
with amortized I/O complexity O({S⋅\log^2 N\over B} + \log_B N ⋅ \log\log N + 1).
The space requirements are linear in the number of vertices.
Internally, we use van Embde Boas layout in Packed Memory Array.

It is joint work with Ondřej Mička and Matěj Lieskovský.

**19. 4. 2022**

**No seminar**

**12. 4. 2022**

**Petr Kučera: Propagation Complete and Unit Refutation Complete Encodings**

**Abstract:**
In this talk, we investigate CNF encodings, for which unit propagation
is strong enough to derive a contradiction if the encoding is not consistent
with a partial assignment of the variables (unit refutation complete or URC
encoding) or additionally to derive all implied literals if the encoding is
consistent with the partial assignment (propagation complete or PC encoding). In
both cases we consider two types of encodings depending on whether we allow
using existentially quantified auxiliary variables or not. We prove an
exponential separation between the sizes of PC and URC encodings without
auxiliary variables and strengthen the known results on their relationship to
the PC and URC encodings that can use auxiliary variables. Besides of this, we
prove that the sizes of any two irredundant PC formulas representing the same
function differ at most by a factor polynomial in the number of the variables
and present an example of a function demonstrating that a similar statement is
not true for URC formulas.

This is a joint work with Petr Savický.

**5. 4. 2022 @ 14:00 on Zoom: https://cesnet.zoom.us/j/93807351394 Passcode: SToC **

**Nicole Wein (Rutgers University): Online List Labeling: Breaking the $\log^2 n$ Barrier **

**Abstract:**
The online list-labeling problem is a basic algorithmic primitive in data structures. The goal is to store a dynamically-changing set of $n$ items in an array of $m$ slots, while keeping the elements in sorted order, and minimizing the relabeling cost, defined to be the number of items that are moved per insertion/deletion. For the linear regime, where $m = Cn$ for some constant $C>1$, an upper bound of $O(\log^2 n)$ on the relabeling cost has been known since 1981. There is a matching lower bound for deterministic algorithms, but for randomized algorithms, the best known lower bound is $\Omega(\log n)$, leaving a gap between upper and lower bounds. In this paper, we improve the upper bound, providing a randomized data structure with expected relabeling cost of $O(\log^{3/2} n)$ per operation.

**29. 3. 2022**

**Navid Talebanfard (Inst. of Math.): A variant of the VC-dimension with applications to depth-3 circuits**

**Abstract:**
We introduce a new analogue of the well-known VC-dimension. We show that for this concept, the corresponding Sauer-Shelah bound can be significantly beaten. We will show a few
applications of this in Valiant's program regarding depth-3 circuit lower bounds.

This is joint work with Peter Frankl and Svyatoslav Gryaznov.

**22. 3. 2022**

**Matej Lieskovský: Better Algorithms for Online Bin Stretching via Computer Search**

**Abstract:**
Online Bin Stretching, introduced by Azar and Regev, is an assignment problem similar to Online Bin Packing. A sequence of
items of size between 0 and 1 arrive and each must be assigned a bin before processing the next item. We are assured that the
items fit into m bins of size 1. We must also use at most m bins but we get to increase their size to what is known as the
stretching factor α.

We present an algorithm for computing upper bounds for the Online Bin Stretching Problem with a small number of bins and the resulting upper bounds for 4, 5 and 6 bins. This both demonstrates the possibility of using computer search for a fundamentally real-valued online problem and improves upon the best bounds known so far, some of which have remained unchanged since 2001.

**15. 3. 2022**

**Martin Koutecký: Liquid Democracy for Cumulative Ballots**

**Abstract:**
Liquid Democracy is a form of delegative democracy which promises more direct participation and dynamic representation. Because it has only recently become realistic with the use of modern technologies, it has been coming into the focus of research. We propose a model of liquid democracy in the context of participatory budgeting and more generally cumulative ballots. A common issue in the context of liquid democracy is the resolution of delegation cycles -- if the vote of A depends on B, which depends on C, which depends on A, how should they vote? We define several natural notions of proportionality and show that delegations in our model can always be satisfactorily resolved.

Next, we turn to the computational aspects of our model. By known results, the complexity of finding a proportional delegation belongs to the class PPAD. Rather than showing completeness or tighter containment (in classes such as PLS, CLS etc.), we ask the practical question: is it possible to efficiently resolve delegations in "real-world" instances? We design a (meta)algorithm which seems to perform well. In the absence of real-world instances, we also devise a framework to compute hard instances; this framework might be of independent interest.

**8. 3. 2022**

**Tung Anh Vu: Generalized k-Center: Distinguishing Doubling and Highway Dimension
**

**Abstract:**
We consider generalizations of the k-Center problem in graphs of low doubling and highway dimension. For the Capacitated k-Supplier with Outliers (CkSwO) problem, we show an efficient parameterized approximation scheme when the parameters are k, the number of outliers and the doubling dimension of the supplier set. On the other hand, we show that for the Capacitated k-Center problem, which is a special case of CkSwO, obtaining an efficient parameterized approximation scheme is W[1]-hard when the parameters are k and highway dimension. This is the first known example of a problem for which it is hard to obtain an efficient parameterized approximation scheme for highway dimension, while simultaneously admitting an efficient parameterized approximation scheme for doubling dimension. This is a joint work with Andreas Emil Feldmann.

**1. 3. 2022**

**Pavel Veselý: Improved Approximation Guarantees for Shortest Superstrings using Cycle Classification by Overlap to Length Ratios**

**Abstract:**
In the Shortest Superstring problem, we are given a set of strings and we are asking for a common superstring, having the minimum number of characters. This problem is NP-hard and several constant-factor approximation algorithms are known. Of particular interest is the Greedy algorithm which repeatedly merges two strings of maximum overlap until one string remains.

We outline ideas behind a new bound on the approximation factor of Greedy. Our techniques also improve the best known approximation guarantee for the problem. This is a joint work with Matthias Englert and Nick Matsakis.

**22. 2. 2022**

**Andreas Feldmann: The Parameterized Complexity of the Survivable Network Design Problem**

**Abstract:**
For the well-known Survivable Network Design Problem (SNDP) we are given an undirected graph G with edge costs, a set R of terminal vertices, and an integer demand d_{s,t} for every
terminal pair s, t ∈ R. The task is to compute a subgraph H of G of minimum cost, such that there are at least d_{s,t} disjoint paths between s and t in H. Depending on the type of
disjointness we obtain several variants of SNDP that have been widely studied in the literature.
In this work we shed light on the parameterized complexity of those problems.

This is joint work with Anish Mukherjee and Erik Jan van Leeuwen.

*
*

**4. 1. 2022**

**No seminar**

**14. 12. 2021**

**Pavel Veselý: Relative Error Streaming Quantiles**

**Abstract:**
We discuss approximating quantiles and distributions using
streaming algorithms that process the input in one pass and maintain a small
data structure, called sketch. We focus on providing the relative error
guarantee, which helps to understand the tails of the input distribution as
it allows one to estimate percentiles such as 99, 99.9, 99.99, etc., with
increasing accuracy. We describe a new algorithm with a close-to-optimal
space requirement.

Based on joint work with Graham Cormode, Zohar Karnin, Edo Liberty, and Justin Thaler.

**7. 12. 2021**

**Jakub Tětek (U. of Copenhagen): Better Sum Estimation via Weighted Sampling**

**Abstract:**
Given a large set U where each item a∈ U has weight w(a), we want to estimate the total weight W=∑_{a∈U} w(a) to within factor of
1 ± ε with some constant probability >1/2. Since n=|U| is large, we want to do this without looking at the entire set U.
In the traditional setting in which we are allowed to sample elements from U uniformly, sampling Ω(n) items is necessary to
provide any non-trivial guarantee on the estimate. Therefore, we investigate this problem in different settings: in the
proportional setting we can sample items with probabilities proportional to their weights, and in the hybrid setting we can
sample both proportionally and uniformly.
Sum estimation in the proportional and hybrid setting has been considered before by Motwani, Panigrahy, and Xu [ICALP, 2007].
In their paper, they give both upper and lower bounds in terms of n. Their bounds are near-matching in terms of n, but not in
terms of ε. In our paper, we improve both their upper and lower bounds.
Our bounds are matching up to constant factors in both settings, in terms of both n and ε. No lower bounds with dependency on ε
were known previously. In the proportional setting, we improve their Õ(√n/ε^{7/2}) algorithm to O(√n/ε). In the hybrid setting, we
improve Õ(n^{1/3}/ε^{9/2}) to O(n^{1/3}/ε^{4/3}).

We also investigate the previously unexplored setting where n is unknown to the algorithm. Finally, we show how our techniques apply to the problem of edge counting in graphs.

Based on joint work with Lorenzo Beretta.

**30. 11. 2021**

**Martin Loebl: Critical Distribution System**

**Abstract:**
I will introduce a market mechanism for distributing a sparse commodity in a crisis, and present an auction-based
efficient algorithm for finding an approximate equilibrium.

**23. 11. 2021**

**Jan Kofron: Interpolation-based Software Verification**

**Abstract:**
Reliability of computer systems becomes more and more important with emerging
technologies such as IoT, various smart cyber-physical systems and last but
not least, control systems, e.g., in aircrafts. Symbolic techniques for
software verification have recently become one of the main topics of related
research. They attempt to address the drawbacks of explicit verification
approaches, such as explicit model checking, suffering from the state space
explosion problem. The talk will discuss techniques of symbolic software
verification, particularly interpolation-based model checking, where source
code is represented by a system of algebraic equations, whose satisfiability
(corresponding to presence or reachability of an error) is verified using an
SMT solver, such as Z3 and OpenSMT2.

**16. 11. 2021**

**Martin Böhm (U. of Wrocław): Submodularity Gaps for Selected Network Design and Matching Problems**

**Abstract:**
Several techniques that allow developing approximation
algorithms for problems with submodular cost function have been
proposed. One can therefore ask whether it is possible to approximate
the actual cost function of a studied problem with a proxy submodular
function. Existence of such submodular approximations would allow to
reduce various problems to submodular optimisation.

We answer this question in the negative for two major problems in metric optimization, namely Steiner Tree and Uncapacitated Facility Location. We do so by proving super-constant lower bounds on the submodularity gap for these problems. Our bounds build on strong lower bounds for the online variants of these two problems. Additionally, we show that the problem Maximum Bipartite Matching does not exhibit a submodularity gap, in contrast with its online variant being only (1−1/e)-competitive in the randomized setting.

Joint work with Jarosław Byrka, Mateusz Lewandowski and Jan Marcinkowski.

**9. 11. 2021**

**Michelle Yeo (IST): Private and efficient route discovery in payment channel networks**

**Abstract:**
Layer 2 solutions like payment channel networks are a promising approach to improve the scalability of cryptocurrencies. An
important problem in payment channel networks in the route discovery problem: given any two users (say Alice and Bob), what is
the cheapest path for a fixed payment amount from Alice to Bob? In two of my recent works, I explore techniques which aim to
perform route discovery in payment channel networks in private and efficient ways.

In the first setting, we combine private information retrieval and hub labelling to perform efficient and private route discovery. We also use a heuristic that leverages the highway dimension of the Lightning Network to further reduce the hub set sizes, which makes our technique more efficient. In the second setting, we consider an almost private payment channel network topology and present solutions which gossip exploratory path-discovery messages from both sender and receiver. When a node in the middle receives both sender and receiver messages, a path is found. I will also present improvements to prevent overwhelming the network with these exploratory messages.

Based on joint work with Krzysztof Pietrzak, Stefan Schmid, Iosif Salem, Mahsa Bastankhah, and Zeta Avarikioti.

**2. 11. 2021**

**Petr Gregor: Compression of Hamilton cycles in highly symmetric graphs**

**Abstract:**
Assume that G is a Hamiltonian graph with a "rich" automorphism group. What is the largest k such that G has a
Hamilton cycle that is preserved by some automorphism of order k (in Aut(G))? Such k-symmetric Hamilton cycles can be
compressed by factor k, up to the size of the automorphism. We fully answer this question for hypercubes, almost optimally for
permutahedra, and we obtain several bounds for other highly symmetric graphs. We also discuss connection to balanced Gray codes
and propose several open problems.

This is a recent work with Arturo Merino and Torsten Mütze.

**26. 10. 2021**

**Martin Pastyřík: Evaluating the Threat of Relay Attacks to Decentralized Contact Tracing**

**Abstract:**
We will discuss relay attacks on decentralized contact tracing schemes based on Bluetooth Low Energy proximity estimation (e.g., the Czech system eRouška) and the possible methods of
preventing them while preserving the privacy of the users participating in such systems. Finally, we will introduce a data-driven model for quantifying the threat of relay attacks to
decentralized contact tracing systems as well as to the healthcare systems reliant on them.

Based on joint work with Pavel Hubáček, Chethan Kamath, and Josef Tkadlec.

**19. 10. 2021**

**No seminar due to a workshop**

**12. 10. 2021**

**Matin Koutecký: Optimal Preconditioners to Bounded Treedepth**

**Abstract:**
The main three currently known tractable classes of integer programs (IPs) are totally unimodular, fixed-dimension,
and bounded treedepth IPs. A natural question to ask is whether a given IP with a constraint matrix A is row-equivalent to an
IP with a constraint matrix A' which falls into one of those classes. This is the same as asking for a so-called left
preconditioner, which is a regular matrix P such that PA = A'. Finding a preconditioner (or deciding there is none) is easy if
we want A' to be fixed-dimension, and is possible by known results if we want A' to be TU.

We show that finding a preconditioner to A' with primal or dual treedepth k is FPT(k,ec(A')) (here, ec(A') denotes the *"entry
complexity"* of A', which is the largest absolute value in A'). This is done exploting a connection to recently introduced
matroid parameters deletion-depth and contraction-depth, respectively. Moreover, we connect another parameter,
contraction-deletion-depth, to finding preconditioners to bounded incidence treedepth and give some preliminary results.

Another important question is finding right preconditioners, which corresponds to not row but column operations. Here, we also give some preliminary structural and algorithmic results.

This is recent joint work with Marcin Briański, Dan Kráľ, Kristýna Pekárková, and Felix Schröder

**5. 10. 2021**

**Damir Dzhafarov (Charles U./UCONN): Reverse mathematics and computable combinatorics**

**Abstract:**
I will give a talk in three parts. The first part will be a basic
introduction to the program of reverse mathematics, with several classical
examples. The second will be a survey of some key results over the past ten
years, highlighting the central role in the subject of combinatorics. The
third part will focus on some recent developments and trends, including open
problems. No background beyond some elementary knowledge of logic and computability theory will be assumed.

**1. 6. 2021 - In person (in S4) + zoom, pizza will be served!**

**Vašek Chvátal: A self-centered look at cutting planes**

**Abstract:**
I will survey the birth and early development of the notion of cutting-plane proofs.

Video recording. (The audio starts only at 2min and 30 sec.)

Slides with minor corrections; slide 136: "𝛼(𝐺)≤𝑘", and slide 153: "0≥1".

**25. 5. 2021**

**Leah Epstein (U. of Haifa): On the price of clustering**

**Abstract:**
We discuss a recently introduced concept, called the price of
clustering, for one-dimensional variants of the bin packing problem. Input
items have sizes, and they also belong to a certain number of types. The new
concept deals with the comparison of optimal solutions for the cases where
items of distinct types can and cannot be packed together, respectively. The
problem is related to greedy bin packing algorithms and batched bin packing,
and we discuss some of those concepts as well for the different variants.

**18. 5. 2021**

**Debarati Das (U. of Copenhagen): Approximating the Median under the Ulam Metric**

**Abstract:**
We study approximation algorithms for variants of the ''median string'' problem, which asks for a string that minimizes the sum of edit distances from a
given set of $m$ strings of length $n$. Only the straightforward $2$-approximation is known for this NP-hard problem. This problem is motivated e.g. by
computational biology, and belongs to the class of median problems (over different metric spaces), which are fundamental tasks in data analysis.

Our main result is for the Ulam metric, where all strings are permutations over $[n]$ and each edit operation moves a symbol (deletion plus insertion). We devise for this problem an algorithms that breaks the $2$-approximation barrier, i.e., computes a $(2-\delta)$-approximate median permutation for some constant $\delta>0$ in time $\tilde{O}(nm^2+n^3)$. We further use these techniques to achieve a $(2-\delta)$ approximation for the median string problem in the special case where the median is restricted to length $n$ and the optimal objective is large $\Omega(mn)$.

We also design an approximation algorithm for the following probabilistic model of the Ulam median: the input consists of $m$ perturbations of an (unknown) permutation $x$, each generated by moving every symbol to a random position with probability (a parameter) $\epsilon>0$. Our algorithm computes with high probability a $(1+o(1/\epsilon))$-approximate median permutation in time $O(mn^2+n^3)$. This is a joint work with Diptarka Chakraborty and Robert Krauthgamer.

**11. 5. 2021**

**Václav Rozhoň (ETHZ): Distributed Algorithms, Finitary Factors, and Descriptive Combinatorics**

**Abstract:**
We will discuss an intimate connection between the following three fields: (a) distributed local algorithms: coming from the area of computer science, (b)
finitary factors of iid processes: coming from the area of analysis of randomized processes, (c) descriptive combinatorics: coming from the area of combinatorics
and measure theory. We will talk mostly about joint work with Jan Grebík aimed at formalizing the connection. This is motivated by a recent insightful paper of
Bernshteyn who showed that results from (a) can automatically imply results in (c).

**4. 5. 2021**

**Veronika Slívová: A Subexponential algorithm for arrival**

**Abstract:**
I will present a subexponential algorithm for Arrival problem by Bernd
Gärtner, Sebastian Haslebacher and Hung P. Hoang.

**27. 4. 2021**

**Rob van Stee (U. of Siegen): Buffer Minimization with Conflicts on a Line**

**Abstract:**
In the buffer minimization in multiprocessor systems with
conflicts or simply buffer minimization problem, a multi-processor system is modelled as an undirected graph. A conflict occurs if two processors are connected by
an edge. Conflicting processors can not run at the same time. At any time, load may arrive on one or more processors.
Incoming workload is stored in an input buffer and a machine that is
running reduces its workload at a constant rate. The goal is to find a
schedule that minimizes the maximum workload over all machines. We
consider the special case where the graph is a path and give bounds on
the competitive ratio for small graph sizes, including a tight bound of
9/4 for a path with 4 nodes. We give a general lower bound of 12/5. We
also consider online algorithms that have resource augmentation on their
speed, and give a (1 + epsilon)-speed (1/epsilon + 3)-competitive algorithm.

**20. 4. 2021**

**Michal Opler: Hardness of C-Permutation Pattern Matching**

**Abstract:**
Deciding if a permutation tau contains a permutation pi (a problem called Permutation Pattern Matching) is known to be NP-complete [Bose et al., Inform. Process.
Lett. 1998]. This general hardness result motivated the study of parameterized and restricted variants. In this work, we investigate the C-Permutation Pattern
Matching (C-PPM) which is PPM where both tau and pi belong to a fixed permutation class C. Jelínek and Kynčl [SODA '17] showed that C-PPM is NP-complete whenever
C is taken to be the class of all permutations avoiding some fixed pattern sigma of length at least 10.

We resolve the hardness of C-PPM for almost all classes C defined by a single avoiding pattern. In fact, we show that C-PPM is NP-complete whenever C is a certain type of so-called generalized grid class and that all but one class avoiding pattern sigma of length at least five contains such a subclass. Moreover, we show that unless ETH fails, C-PPM in any of the hard cases cannot be solved in time 2^{o(n/log(n))}. On the positive side, we show that C-PPM is solvable in polynomial time whenever C is a monotone grid class.

This is joint work with Vít Jelínek and Jakub Pekárek.

**13. 4. 2021**

**Karel Král: Sorting Short Integers**

**Abstract:**
We build boolean circuits of size O(nm^2) and depth O(log(n) + m log(m)) for
sorting n integers each of m-bits.
We build also circuits that sort n integers each of m-bits according to
their first k bits that are of size O(nmk (1 + log*(n) - log*(m))) and depth
O(log^{3} n).
This improves on the results of Asharov et al. and resolves some of their
open questions.

**6. 4. 2021**

**Navid Talebanfard (MI AS CR): Super strong ETH is true for PPSZ with small resolution width**

**Abstract:**
We construct hard instances for PPSZ the best known k-SAT algorithm showing
that its running time is as predicted by Super Strong ETH. The construction
involves interesting combinatorics including tools from graph
homomorphism theory.

**30. 3. 2021**

**Jan Václavek: On Search Complexity of Discrete Logarithm**

**Abstract:**
We will discuss the discrete logarithm problem in the context of TFNP - the
complexity class of search problems with a syntactically guaranteed
existence of solutions for all instances. Our main results show that
suitable variants of the discrete logarithm problem are complete for the
complexity class PPP, respectively PWPP - complexity classes capturing total
search problems with a solution guaranteed by the pigeonhole principle,
respectively the weak pigeonhole principle. Our completeness results answer
an open problem from the recent work of Sotiraki, Zampetakis, and Zirdelis
[FOCS’18].

Our reductions also provide new structural insights into the complexity class PWPP by establishing two additional PWPP-complete problems. First, the problem Dove, a relaxation of the PPP-complete problem Pigeon, which is the first PWPP-complete problem not defined in terms of an explicitly shrinking function. Second, the problem Claw, a total search problem capturing the computational complexity of breaking claw-free permutations. In the context of TFNP, the PWPP-completeness of Claw matches the known intrinsic relationship between collision-free hash functions and claw-free permutations established in the cryptographic literature.

Joint work with Pavel Hubáček.

**23. 3. 2021**

**Pavel Veselý (U. of Warwick/Charles U.): Streaming Algorithms for Geometric Steiner Forest**

**Abstract:**
In this talk, we focus on geometric algorithms in the streaming setting, where the input is presented as a stream of insertions and deletions of points from a
Euclidean space. The algorithm must process the stream in one pass and use a small amount of memory, sublinear in the number of points. Previous works have
designed algorithms that estimate, for example, the cost of the minimum spanning tree (MST) or a clustering cost (e.g. Facility Location or k-median).

I will describe our recent progress in this line of work, namely, a new streaming algorithm for Steiner forest in the Euclidean plane with an approximation ratio arbitrarily close to the Steiner ratio alpha_2, which is the worst-case ratio between the costs of MST and Steiner tree (currently, 1.1547 <= alpha_2 <= 1.214). Our approach relies on a novel combination of streaming techniques, like sampling and linear sketching, with the classical dynamic-programming framework for geometric optimization problems, which usually requires large memory and has so far not been applied in the streaming setting.

We also discuss how to prove lower bounds for geometric streaming problems. In particular, we show how to rule out 1+epsilon approximation for MST or TSP in high-dimensional Euclidean spaces.

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

**16. 3. 2021**

**Pavel Dvořák: Network Coding Conjecture implies Data Structure Lower Bounds**

**Abstract:**
Network coding conjecture (NCC) by Li and Li asserts that network coding for undirected graphs does not bring any advantage over multicommodity flows. Recently,
NCC was used to prove a conditional lower bound for sorting algorithms with external memory [Farhadi et al., STOC 2019], circuits for multiplication [Afshani et
al., ICALP 2019], and circuits for sorting [Asharov et al., SODA 2021]. We use a technique of Farhadi et al. to prove an NCC-based lower bound for non-adaptive
data structures for function inversion, polynomial evaluation and polynomial interpolation.
This is joint work with Michal Koucký, Karel Král and Veronika Slívová.

**9. 3. 2021**

**Martin Koutecký: Beyond Parameterized Algorithms for IPs of Small Treedepth**

**Abstract:**
Recently, a long line of research culminated by showing an algorithm which solves integer programs (IPs) in time g(a,d)poly(n), where a is the largest coefficient
of the constraint matrix, and d is its sparsity measure, specifically the primal or dual treedepth of the constraint matrix. Further work has so far focused on
improving algorithm complexities, making them strongly polynomial, showing lower bounds, etc.

I will review some recent work which takes a different direction. One, we ask what happens when we allow some variables to take on real values, i.e., what is the complexity of Mixed Integer Programs (MIPs) with constraint matrices of small treedepth? We show that the same complexity classification holds for MIPs as for IPs if the objective function is linear. Our technique has other nice consequences, e.g. implying new bounds on the proximity of solutions as the set of real coordinates changes.

On the other hand and quite surprisingly, we show that if we allow real right hand sides or if we allow separable convex objectives, there are some MIPs with a very simple constraint matrix (of constant treedepth and coefficients) for which the problem is NP-hard. This contradicts the "common wisdom" that "separable convex optimization is not much harder than linear optimization" [Hochbaum and Shanthikumar, JACM 1990].

Another line of work we explore is when the sparse structure of the constraint matrix is "hidden" -- it is not visible in the structure of non-zeroes of the matrix, but it is contained in the row matroid of the matrix. We show that IPs and MILPs whose matrix has small branch-depth can be solved efficiently.

The part on MILPs is joint work with Cornelius Brand and Sebastian Ordyniak [AAAI 2021]; the part on branch-depth is joint work with Timothy F.N. Chan, Jacob W. Cooper, Daniel Kráľ, Kristýna Pekárková [ICALP 2020].

**5. 1. 2021**

**No seminar: Happy New Year**

**15. 12. 2020**

**Vibha Sahlot: Structural Parameterisation Without Modulator**

**Abstract:**
Many NP hard problems like Vertex Cover, Feedback Vertex Set and Odd Cycle Transversal are polynomial time solvable in the class of chordal graphs. We consider
these problems in a graph that has at most $k$ vertices whose deletion results in a chordal graph, when parameterized by $k$. Here we assume that the deletion set
is not given. In this talk, we shall discuss $2^{\mathcal{O}(k)}n^{\mathcal{O}(1)}$ time algorithms for these problems which can't be obtained by directly using
current best known algorithms to compute, approximate or fpt approximate Chordal Vertex Deletion set.

Our algorithms do not compute a chordal vertex deletion set (or even an approximate solution). Instead, we construct a tree decomposition of the given graph in time $2^{\mathcal{O}(k)}n^{\mathcal{O}(1)}$ where each bag is a union of four cliques and $\mathcal{O}(k)$ vertices. We then apply standard dynamic programming algorithms over this special tree decomposition. Our algorithms are adaptive (robust) in the sense that given an integer $k$, they detect whether the graph has a chordal vertex deletion set of size at most $k$ or output the special tree decomposition and solve the problem.

This is joint work with Ashwin Jacob, Venkatesh Raman and Fahad Panolan.

**8. 12. 2020**

**Cornelius Brand: An algebraic perspective on representative sets**

**Abstract:**
The method of representative sets goes back to work of Lovász from the 70s, and was lately made algorithmic by Fomin et al. (JACM 2016), producing the best known deterministic running
times for a variety of parameterized problems on graphs (such as finding certain subgraphs of a fixed size in large host graphs).

It uses the idea of computing a solution iteratively through a sequence of smaller partial solutions, and retaining only a so-called representative set of the partial solutions in each step. This set has the property that any possible partial solution can be extended to a solution of the desired final size if and only if one of the retained partial solutions can be extended to a full solution. The method invokes heavy combinatorial machinery, and is seemingly unrelated to more recent algebraic approaches to subgraph problems.

In this talk, I will give a gentle introduction to the method and phrase it in algebraic instead of the usual combinatorial terms. Then, I will show up the connections of the methods to recent algebraic approaches, and avenues to potentially refine the method further.

Part of the work I report on is joint with Kevin Pratt from CMU.

**1. 12. 2020**

**Chethan Kamath: Builder-Pebbler game and its applications to cryptography**

**Abstract:**
We will discuss the “Builder-Pebbler” game, a two-player combinatorial game played on graphs. The game finds its motivation in cryptography as bounds on success probability of
its player strategies translate to limits on provable security of certain cryptographic protocols.
Based on joint work with Karen Klein, Krzysztof Pietrzak and Michael Walter (IST Austria)

**24. 11. 2020**

**Parth Mittal: Delta-vertex coloring in graph streams**

**Abstract:**
The celebrated Brooks' theorem in graph theory states that
every connected graph which is not a clique or an odd-cycle can be
Delta-colored (where Delta is the maximum degree). We will present an
O(n^7/4) space algorithm for Delta-coloring graphs after a single pass
over the edges. Based on joint work with Sepehr Assadi and Pankaj
Kumar.

**10. 11. 2020**

**Andreas Feldmann: Polynomial time approximation schemes for clustering in low highway dimension graphs**

**Abstract:**
We study clustering problems such as k-Median, k-Means, and Facility Location in graphs of low highway dimension, which is a graph parameter modeling transportation networks. It was previously shown that approximation schemes for these problems exist, which either run in quasi-polynomial time (assuming constant highway dimension) [Feldmann et al. SICOMP 2018] or run in FPT time (parameterized by the number of clusters k, the highway dimension, and the approximation factor) [Becker et al. ESA 2018, Braverman et al. 2020]. In this paper we show that a polynomial-time approximation scheme (PTAS) exists (assuming constant highway dimension). We also show that the considered problems are NP-hard on graphs of highway dimension 1. This is joint work with David Saulpic.

**3. 11. 2020**

**Pavel Dvořák: Barrington plays cards**

**Abstract:**
I will show you how to securely compute a boolean function using regular playing cards. We will establish which functions have efficient card based protocols.

**27. 10. 2020**

**Jaroslav Nešetřil: Three Aspects of Structural Graph Theory**

**Abstract:**
I will provide an introduction to the area of my current interest - structural graph theory.

**20. 10. 2020**

**Veronika Slívová: On Average-Case Hardness in TFNP from One-Way Functions**

**Abstract:**
Recently, lower bounds for the computational complexity of important total search problems
(captured by the class TFNP) were demonstrated under various cryptographic assumptions. We
study the limitations of this methodology and show that one-way functions are not
sufficiently structured to give rise to hard distributions of problems in TFNP in a black-box way.
Based on joint work with Pavel Hubáček, Chethan Kamath, and Karel Král.

**13. 10. 2020**

**Ondřej Čepek: Switch-List Representations in a Knowledge Compilation Map**

**Abstract:**
In this talk I will look at a less usual way to represent Boolean functions, namely representing them by switch-lists and the usage of this representation in knowledge compilation.