Seminar on Theory of Computing - Seminář z teoretické informatiky
Ondřej Čepek, Pavel Hubáček, Petr Kolman, Michal Koucký, Jiří Sgall, Pavel Veselý
<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.
Fall/Winter semester 2023/2024
This semester, we plan 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 3, 2023. The current schedule is located at this page.Spring/Summer semester 2022/2023
This semester we plan talks on our own research. The seminar will start at 12:00 by pizza and the actual talk will start at 12:20. The seminar takes place in S8. The first seminar will take place on February 21.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.
Fall/Winter semester 2022/2023
This semester we plan talks on our own research. The seminar will start at 12:00 by pizza and the actual talk will start at 12:20. The seminar takes place in S8.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.
Based on joint work with Charlotte Hoffmann, Chethan Kamath, Karen Klein, and Krzysztof Pietrzak.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:
We will survey some known examples of qualitative superiority of quantum communication, try to classify the problems that have been used to demonstrate those separations and discuss the remaining open problems.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:
A distribution is k-incompressible if no efficient compression scheme compresses it to less than k bits, Yao [FOCS ’82]. While being a natural measure, its relation to other computational analogs of entropy such as pseudoentropy of Hastad, Impagliazzo, Levin, and Luby [SICOMP 99], and to other cryptographic hardness assumptions, was unclear.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ý.
Spring/Summer semester 2021/2022
This semester we plan talks on our own research. The seminar will start at 12:00 by pizza and the actual talk will start at 12:20. The seminar takes place in S8. The first seminar will take place on February 22nd.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.
Fall/Winter semester 2021/2022
This semester we plan talks on our own research. The seminar will start at 12:00 by pizza and the actual talk will start at 12:20. The seminar takes place in S1 but you can also participate via Zoom (passcode: SToC). The first seminar will take place on October 5th.
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.
Spring semester 2020/2021
This semester we plan talks on our own research. The seminar will start at 12:00 by your own lunch and the actual talk will start at 12:20. The first seminar will ta ke place on March 9th.
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].
Fall semester 2020/2021
This semester we plan talks on our own research. The seminar will start at 12:00 by your own lunch and the actual talk will start at 12:20. The first seminar will take place on October 13.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.