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.

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