# 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: 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.

## 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.

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].

## 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.