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

Organizers: Ondřej Čepek, Pavel Hubáček, Petr Kolman, Michal Koucký, Jiří Sgall, Pavel Veselý

Contact: <sgall@iuuk.mff.cuni.cz>

Lecture code: NTIN102 - 0/2 Z

Time: Tue 12:00-14:00

Place: S8, Malá Strana

A seminar presenting ongoing research projects of participants and related recent progress within theoretical computer science. Attendees are expected to present their research or some (recent) exciting results, and follow-up discussion is expected. The seminar starts with pizza at 12:00, which will be provided for the participants, followed by the actual talk at 12:20.

Fall/Winter semester 2023/2024

This semester, we plan a mix of talks on new results of the participants and expositions of recent papers in TCS by students. The first seminar will take place on October 3, 2023.

Next program

5. 12. 2023

David Mikšaník: Coloring graphs with bounded clique number
A well-known theorem of Brooks states that a graph G of maximum degree Delta≥3 can be colored by Delta colors unless G contains a clique of size Delta+1. It is natural to ask what additional assumptions guarantee that G can be colored with Delta-1 colors. Borodin and Kostochka (1976) conjectured that when Delta≥9, it is sufficient to assume only that G does not contain a clique of size Delta. In 1999, Reed showed that this conjecture holds for graphs with maximum degree at least 10^14.
In this talk, I will suggest possible ways to improve Reed's result by decreasing the constant 10^14 to hundreds or lower. This topic is part of my dissertation thesis and this year's GAUK grant proposal, both under the supervision of Zdeněk Dvořák.

Tomáš Hons: Structural limits and inverse problems
The theory of graph convergence and limits was developed for study of large graphs. Inspired by analysis, the idea is to assign a certain limit object to a sequence of growing graphs that captures important properties of the sequence. However, when seeking the right definition of the limit object, the following inverse problem needs to be considered: given a limit object L (i.e. satisfying the definition), is there a sequence of graphs that converges to L? In the talk, we introduce several notions of graph convergence, the corresponding limit objects, and the state of their inverse problem. Moreover, we mention a certain simplified question that deals with approximation of vertices within a limit instead of the limit itself.

12. 12. 2023

Ninad Rajgopal (U. of Warwick): On the Power of Interactive Proofs for Learning

We study interactive proof systems for verifying the results of agnostic learning tasks, which was recently initiated by Goldwasser, Rothblum, Shafer and Yehudayoff [GRSY21], as PAC-verification. Here, for a given target hypothesis class H and for any unknown n-variate Boolean function f, the verifier who only gets random example access to f (over the uniform distribution) interacts with an untrusted prover who has query access to f, to output a hypothesis that is as close to f as an optimal hypothesis from H, up to a small error. Such proof systems enable a verifier to delegate an agnostic learning task to an untrusted prover, with the goal being one of verification using much fewer random examples and/or running time, than actually performing learning (using queries) from scratch. Typically, we require such interactive proofs to be doubly efficient, where the honest prover is also an efficient algorithm.

In this paper, we study delegation of learning for certain Boolean hypothesis classes that are central to learning theory. Firstly, we show an interactive proof for learning all the \eps-heavy Fourier coefficients of a function using poly(1/\eps) many examples (i.e., Goldreich-Levin theorem), whereas the prover uses poly(n/\eps) many membership queries, giving a verification speed-up that is independent of the input length n. We also show a similar input-independent separation for the hypothesis class of all k-Juntas. Next, we show such interactive proofs for learning the class AC^0[2] building on the work by Carmosino-Impagliazzo-Kabanets-Kolokolova [CIKK17], where the verifier uses quasi-polynomially many random examples. In contrast, this class has been notoriously resistant beyond trivial brute force learning, even for constructing realisable learners (without a prover) using random examples. Finally, we show that if we do not insist on doubly-efficient proof systems, then the model becomes trivial; even P/Poly can be learnt using O(1) many examples.

This is joint work with Tom Gur, Mohammad Mahdi Jahanara, Mohammad Mahdi Khodabandeh, Bahar Salamatian, and Igor Shinkar.

Papers to be covered

Calvin Beideman, Karthekeyan Chandrasekaran, Weihang Wang: Approximate minimum cuts and their enumeration. SOSA 2023.

Li Chen, Rasmus Kyng, Maximilian Probst Gutenberg, Sushant Sachdeva: A Simple Framework for Finding Balanced Sparse Cuts via APSP. SOSA 2023.

Or Zamir: The Wrong Direction of Jensen's Inequality Is Algorithmically Right. ICALP 2023.
(possibly Petr Chmel in Spring 2024)

Previous program

28. 11. 2023

Max Deppert, Matthias Kaul, Matthias Mnich: A (3/2 + ε)-Approximation for Multiple TSP with a Variable Number of Depots. ESA 2023.
presented by Petr Martínek

One of the most studied extensions of the famous Traveling Salesperson Problem (TSP) is the Multiple TSP: a set of m ≥ 1 salespersons collectively traverses a set of n cities by m non-trivial tours to minimize the total length of their tours. This problem can also be considered to be a variant of Uncapacitated Vehicle Routing, where the objective is to minimize the sum of all tour lengths. When all m tours start from and end at a single common depot, then the metric Multiple TSP can be approximated equally well as the standard metric TSP, as shown by Frieze (1983). The metric Multiple TSP becomes significantly harder to approximate when there is a set D of d ≥ 1 depots that form the starting and end points of the m tours. This paper gives the first efficient approximation algorithm for Multiple TSP with a variable number d of depots that yields a better-than-2 approximation. Their algorithm runs in time (1/ε)^O(dlog d) ⋅ n^O(1), and produces a (3/2+ε)-approximation with constant probability. For the graphic case, they obtain a deterministic 3/2-approximation in time 2^d ⋅ n^O(1).

21. 11. 2023

Arturo Merino (U. Saarland): Traversing combinatorial polytopes via optimization

We present a new framework that exploits combinatorial optimization for efficiently generating a large variety of combinatorial objects based on graphs, matroids, posets, and polytopes. Our method relies on a simple and versatile algorithm for computing a Hamilton path on the skeleton of any 0/1-polytope conv(X), where X ⊆ {0,1}^n. The algorithm uses as a black box any algorithm that solves the classical linear optimization problem, and the resulting delay, i.e., the running time per visited vertex on the Hamilton path, is only a polylogarithmic factor larger than the running time of the optimization algorithm. When X encodes a particular class of combinatorial objects, then traversing the skeleton of the polytope conv(X) along a Hamilton path corresponds to listing the combinatorial objects by local change operations, i.e., we obtain Gray code listings.

As a concrete example application of our framework, we obtain an O(T⋅log n) delay algorithm for the vertex enumeration problem on 0/1 polytopes, where T is the time needed to solve a linear program and n is the dimension of the polytope. This improves upon the 25-year-old O(T⋅n) delay algorithm due to Bussieck and Lübbecke.

This is joint work with Torsten Mütze (U. of Warwick).

14. 11. 2023

Emmett Breen, Renee Mirka, Zichen Wang, David P. Williamson: Revisiting Garg's 2-Approximation Algorithm for the k-MST Problem in Graphs. SOSA 2023.
presented by Josef Matějka

Garg (STOC'05) gave a polynomial-time 2-approximation algorithm for finding a Minimum Spanning Tree spanning k vertices (k-MST). This paper greatly simplifies the algorithm to achieve Garg's result.

7. 11. 2023

Charlotte Hoffmann (ISTA): Certifying Giant Nonprimes

GIMPS and PrimeGrid are large-scale distributed projects dedicated to searching giant prime numbers, usually of special forms like Mersenne and Proth primes. The numbers in the current search-space are millions of digits large and the participating volunteers need to run resource-consuming primality tests. Once a candidate prime N has been found, the only way for another party to independently verify the primality of N used to be by repeating the expensive primality test. To avoid the need for a second recomputation of each primality test, these projects have recently adopted certifying mechanisms that enable efficient verification of performed tests. However, the mechanisms presently in place only detect benign errors and there is no guarantee against adversarial behavior: a malicious volunteer can mislead the project to reject a giant prime as being non-prime.

In this talk, I will present a practical, cryptographically-sound mechanism for certifying the non-primality of Proth numbers. That is, a volunteer can – parallel to running the primality test for N – generate an efficiently verifiable proof at a little extra cost, certifying that N is not prime.

Joint work with Pavel Hubáček, Chethan Kamath, and Krzysztof Pietrzak.

31. 10. 2023

Pavel Veselý (CUNI): Massively Parallel Algorithms for Clustering in High Dimension

We discuss algorithms for k-Median and k-Means clustering in high-dimensional Euclidean spaces that run in the Massively Parallel Computation (MPC) model, which captures key aspects of MapReduce-style frameworks. In MPC, we have a set of machines, each with a local memory that is sublinear in the input size, and computation proceeds in alternating rounds of communication and sequential (but local) computation. We focus on the fully scalable case in which the local memory may be substantially smaller than the number of clusters k. We present new algorithms that take O(1) rounds and achieve O(1)-bicriteria approximation (meaning we output O(k) clusters), improving upon a polylogarithmic approximation. Our approach relies on a connection between k-clustering and Facility Location, for which we design an MPC O(1)-round O(1)-approximation.

Joint work with Artur Czumaj, Guichen Gao, Shaofeng H.-C. Jiang, and Robert Krauthgamer.

24. 10. 2023

Tomasz Kociumaka, Adam Polak: Bellman-Ford Is Optimal for Shortest Hop-Bounded Paths. ESA 2023.
presented by Jelena Glišić

This paper is about the problem of finding a shortest s-t path using at most h edges in edge-weighted graphs. The Bellman-Ford algorithm solves this problem in O(hm) time, where m is the number of edges. We show that this running time is optimal, up to subpolynomial factors, under popular fine-grained complexity assumptions. More specifically, we show that under the APSP Hypothesis the problem cannot be solved faster already in undirected graphs with nonnegative edge weights. This lower bound holds even restricted to graphs of arbitrary density and for arbitrary h ∈ O(√m). Moreover, under a stronger assumption, namely the Min-Plus Convolution Hypothesis, we can eliminate the restriction h ∈ O(√m). In other words, the O(hm) bound is tight for the entire space of parameters h, m, and n, where n is the number of nodes. Our lower bounds can be contrasted with the recent near-linear time algorithm for the negative-weight Single-Source Shortest Paths problem, which is the textbook application of the Bellman-Ford algorithm.

17. 10. 2023 - CANCELLED

10. 10. 2023

Petr Kučera (CUNI): Binary Constraint Trees and Structural Decomposability

A binary constraint tree (BCT, Wang and Yap 2022) is a normalized binary CSP whose constraint graph is a tree. A BCT constraint is a constraint represented with a BCT where some of the variables may be hidden (i.e. existentially quantified and used only for internal representation). Structured decomposable negation normal forms (SDNNF) were introduced by Pipatsrisawat and Darwiche (2008) as a restriction of decomposable negation normal forms (DNNF). Both DNNFs and SDNNFs were studied in the area of knowledge compilation. In this paper we show that the BCT constraints are polynomially equivalent to SDNNFs. In particular, a BCT constraint can be represented with an SDNNF of polynomial size and, on the other hand, a constraint that can be represented with an SDNNF, can be represented as a BCT constraint of polynomial size. This generalizes the result of Wang and Yap (2022) that shows that a multivalued decision diagram (MDD) can be represented with a BCT. Moreover, our result provides a full characterization of binary constraint trees using a language that is well studied in the area of knowledge compilation. It was shown by Wang and Yap (2023) that a CSP on n variables of domain sizes bounded by d that has treewidth k can be encoded as a BCT on O(n) variables with domain sizes O(d^{k+1}). We provide an alternative reduction for the case of binary CSPs. This allows us to compile any binary CSP to an SDNNF of size that is parameterized by d and k.

3. 10. 2023

Luca Trevisan (Bocconi U.): Approximating Boolean Constraint Satisfaction Problems in Random, Semi-Random, and Worst-Case Instances

We know several techniques to round Semidefinite Programming relaxations of graph optimization problems and of Boolean constraint satisfaction problems in which each constraint involves at most two variables, and these rounding techniques lead to good approximation algorithms. For problems involving hyper-graphs, for Boolean constraint satisfaction problems with three or more variables per constraints, and for polynomial optimization problems with polynomials of degree higher than two, we lack techniques to round Semidefinite Programs (or other convex relaxations) or to analyze their average-case performance.
We present two new techniques to analyze random, semi-random and worst-case instances of problems such as Max 3SAT, Max 3XOR, and degree 3 polynomial optimization. One technique gives new bounds to certify unsatisfiability of random 3SAT and certified upper bounds for random Max 3XOR and for random instances of degree 3 polynomial optimization, and it extends to a certain semi-random generative model (in which instances are produced with a mix of random choices and worst- case choices). The other technique provides a new rounding scheme for worst-case instances of Max 3XOR and homogeneous degree 3 polynomial optimization.

Joint work with Tommaso D’Orsi, Tim Hsieh, Pravesh Kothari, and Lucas Pesenti