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

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