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

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

NTIN102 - 0/2 Z

Time: Wen 12:00-14:00.
Place: S4, Malá Strana. Zoom: https://cesnet.zoom.us/j/93807351394 Passcode: SToC

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 a lunch.

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.