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:** S1, 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.

**23. 3. 2021**

**Pavel Veselý: TBA**

**Abstract:**
TBA

**16. 3. 2021**

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

**Abstract:**
etwork 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.