Program and abstracts

(The times below are Romanian times. Subtract 7 for EST, etc.) 

Miercuri/ Wednesday Iulie/July 19, 2023

15:20-15:30 Opening remarks

15:30-15:55  Speaker: Nina Balcan.  Title: Machine learning for algorithm design with provable guarantees

Abstract: The classic textbook approach to designing and analyzing algorithms assumes worst-case instances of the problem, about which the algorithm designer has absolutely no information at all. While highly desirable when achievable, such worst-case guarantees are often too weak for many algorithmic problems. To address this issue, in recent years, machine learning components have been brought into algorithm design. A major question is what provable guarantees do these learning augmented algorithmic techniques enjoy.  In this talk, I will describe recent work in my group that helps put data-driven algorithm design on firm foundations. I will describe both specific case studies and general principles applicable broadly to a variety of combinatorial problems.

15:55-16:20  Speaker: Carol Zamfirescu. Title: On a conjecture of Grünbaum and K_2-hypohamiltonian graphs

Abstract: Motivated by a conjecture of Grünbaum and a problem of Katona, Kostochka, Pach, and Stechkin, the talk will mainly deal with K_2-hypohamiltonian graphs: these are non-hamiltonian graphs in which the removal of any pair of adjacent vertices yields a hamiltonian graph. We present an algorithm which generates all pairwise non-isomorphic K_2-hypohamiltonian graphs of a given order. We introduce new bounding criteria especially designed for K_2-hypohamiltonian graphs. Using our algorithm, we improve upon earlier computational results. For instance, we characterise the orders for which K_2-hypohamiltonian graphs exist. If time permits, related problems for planar graphs will also be discussed.

16:20 -16:50 Break 

16:50-17:15 Speaker: Rares Buhai. Title: Algorithms approaching the threshold for semi-random planted clique

Abstract: We design new polynomial-time algorithms for recovering planted cliques in the semi-random graph model introduced by Feige and Kilian. The previous best algorithms for this model succeed if the planted clique has size at least n^(2/3) in a graph with n vertices. Our algorithms work for planted-clique sizes approaching n^(1/2) — the information-theoretic threshold in the semi-random model and a conjectured computational threshold even in the easier fully-random model. This result comes close to resolving open questions by Feige and Steinhardt. This is joint work with Pravesh Kothari and David Steurer.

17:15-17:40  Speaker: Ion Nechita. Title: Generating quantum permutation matrices

Abstract: I will present a Sinkhorn-like algorithm for generating quantum permutation matrices which encode quantum symmetries of graphs. This is joint work with Simon Schmidt and Moritz Weber, arXiv:1911.04912

17:40-18:05 Speaker: Ioana Bercea. Title: Locally Uniform Hashing

Abstract: Hashing is a commonly used technique for getting improved algorithms. Most analyses, however, assume access to fully-random hash functions, which is unrealistic in terms of the resources available to the algorithm. A fundamental line of work has thus been to design realistic hash functions (with small space and fast evaluation time) that make the algorithm perform almost as if it used fully-random hash functions. In this talk, we will review one such hash function, called a tornado tabulation hash function, that provides state-of-the-art randomness guarantees for several fundamental algorithms. In particular, we will define and discuss one key property that it exhibits, that of local uniformity. This is joint work with Lorenzo Beretta, Jonas Klausen, Jakob Bæk Tejs Houen, and Mikkel Thorup, to appear in FOCS 2023.

18:05-18:45 Break 40'/ Meal and social time

18:45-19:10  Speaker: Marius Zimand. Title: Universal almost optimal compression and Slepian-Wolf coding in probabilistic polynomial time, 

Abstract:  Good lossless compression means mapping data to short compressed codes. Ideally, the codes should have minimal or close-to-minimal description length. It is also desirable to have fast compression and decompression algorithms. Unfortunately, it is impossible to obtain close-to-minimal codes from which decompression is even remotely efficient.  In contrast, we show that, remarkably, there is no fundamental conflict between having close-to-minimal codes and efficient compression. More precisely, if a good approximation of the length of a minimal description of the data is given, then a probabilistic compressor can generate an almost minimal compressed code in polynomial time. The same optimal compressor can be used for any description system. Moreover, it can be used for distributed compression as well. Joint work with Bruno Bauwens.Paper is available at:  https://dl.acm.org/doi/10.1145/3575807

(older version at   https://arxiv.org/abs/1911.04268 ). Journal of ACM, April 2023.

19:10-19:35  Speaker: Ana-Andreea Stoica. Title: A graph-based algorithm for computing Pareto frontiers of multiple objectives: an application to fair clustering 

Abstract: Recent application of fairness in algorithmic design include clustering, where the composition of clusters may suggest that different groups gain different benefits from membership in a cluster (for example, differentiated access to transportation among demographic groups in the problem of facility location). In this work, we build a polynomial-time algorithm to trace the Pareto-frontier of multiple objectives in graph-based clustering. We reduce our problem to the negative cycle finding problem and leverage timely graph-based algorithms for solving it. We showcase the efficacy of our algorithm on a network from US Highschools that includes information about students' demographics, setting as objectives the clustering cost (Ncut) and demographic parity as a fairness objective. 

19:35 - SOCIAL & Discutie libera despre algoritmica Romaneasca 

Joi/Thursday Iulie/July 20, 2023

15:30-15:55 Speaker: Laura Ciobanu. Title: Word equations, formal languages and complexity

Abstract: Solving word equations (in free monoids) is a rich and well-established area in theoretical computer science. In this talk I will give a short non-technical survey containing results from both mathematics and computer science about solving equations in (semi)groups, with emphasis on the free ones. In particular, I will explain that the solutions to equations can be beautifully described in terms of EDT0L languages, and that the (non-deterministic) space complexity is remarkably low even for groups arising in deep geometric settings. This is based on work with/of Volker Diekert, Murray Elder, Alex Evetts and Alex Levine.

15:55-16:20  Speaker: Gruia Calinescu. Title: Combination algorithms for Steiner Tree variants

Abstract: We give better approximation ratios for two Steiner Tree variants by combining known algorithms: the almost optimum 3-restricted decomposition and iterative randomized rounding. The first problem is Steiner Tree with minimum number of Steiner Points and bounded edged length problem (SMT-MSP).

The input consists of a set of terminals T in Euclidean space R^2. A feasible solution is a Steiner tree  spanning T with Steiner points S such that every edge in this tree has length at most 1. And the objective is to minimize the cardinality of S. Previously, the best approximation ratio for SMT-MSP was 2.386.

We present a polynomial time algorithm with ratio 2.277. The second problem is Minimum Steiner Tree in quasi-bipartite graphs. It is a minimum Steiner Tree problem on graph G=(V,E,c) with terminal set T.

And the edge set does not include any edge between two vertices not in T. The best-known approximation ratio for this problem is 73/60. We improve this ratio to 298/245. Join work with Xiaolang Wang

16:20-16:50 Break 30’

16:50-17:15  Speaker: Adrian Miclaus. Title: Faster Algorithms for Computing the Hairpin Completion Distance and Minimum Ancestor

Abstract: Hairpin completion is an operation on formal languages that has been inspired by hairpin formation in DNA biochemistry and has many applications especially in DNA computing. Consider s to be a string over the alphabet {A, C, G, T} such that a prefix/suffix of it matches the reversed complement of a substring of s. Then, in a hairpin completion operation the reversed complement of this prefix/suffix is added to the start/end of s forming a new string. In this paper we study two problems related to the hairpin completion. The first problem asks the minimum number of hairpin operations necessary to transform one string into another, number that is called the hairpin completion distance. For this problem we show an algorithm of running time O(n²), where n is the maximum length of the two strings. Our algorithm improves on the algorithm of Manea (TCS 2010), that has running time O(n² log n). In the minimum distance common hairpin completion ancestor problem we want to find, for two input strings x and y, a string w that minimizes the sum of the hairpin completion distances to x and y. Similarly, we present an algorithm with running time O(n²) that improves by a O(log n) factor the algorithm of Manea (TCS 2010). This is joint work with Itai Boneh, Dvir Fried and Alexandru Popa. Paper is available at:link to paper

17:15-17:40 Speaker: Ioan Todinca. Title: On graphs that can be covered by k shortest paths

Abstract: We consider undirected graphs G whose edges (or vertices) can be covered by k shortest paths. We show that, for any BFS of such graphs, the number of vertices in a same layer (i.e., at the same distance from the source) is upper bounded by a single-exponential function of k. In particular, the pathwidth of G is also bounded by such a function. As a corollary, we prove that the problem Isometric Path Cover with Terminals (which, given a graph G and a set of k pairs of vertices called terminals, asks whether G can be covered by kshortest paths, each joining a pair of terminals) is FPT with respect to the number of terminals. The same holds for the similar problem Strong Geodetic Set with Terminals (which, given a graph G and a set of k terminals, asks whether there exist k(k-1)/2 shortest paths covering G, each joining a distinct pair of terminals). Moreover, this implies that the related problems Isometric Path Cover and Strong Geodetic Set (defined similarly but where the set of terminals is not part of the input) are in XP with respect to parameter k. https://arxiv.org/abs/2206.15088. Joint work with: Maël Dumas, Florent Foucaud, Anthony Perez.

17:40-18:05  Speaker: Tamio-Vesa Nakajima.  Title: Approximate linearly ordered hypergraph colouring.

Abstract: In the approximate graph colouring problem, we are given a k-colourable graph G, and we must efficiently find an l-colouring of G for some l >= k. In this talk, we will see an algorithm for a variant of the approximate graph colouring problem, namely the approximate linearly ordered (LO) hypergraph colouring problem. This is similar to the approximate graph colouring problem, but considers LO colourings of hypergraphs rather than ordinary graph colourings. An LO colouring of a hypergraph is an assignment of integers to the vertices of the hypergraph such that each edge contains a unique maximum value. The algorithm we give has the following performance: Given a 3-uniform hypergraph H with n vertices that has an LO colouring that uses 2 colours, it finds an LO colouring of H that uses O(cbrt(n log log n / log n)) colours, in polynomial time. This is joint work with Stanislav Živný.

18:05-18:45 Break 40’ (Meal and social time)

18:45-19:10 Speaker: Cosmin Pohoata Title: Some remarks on the permanent-determinant problem

Abstract: Given an n by n matrix A and an m by m matrix B with entries that are affine linear functions of the entries of A, what is the smallest m such that the determinant of B equals the permanent of A? In this talk, I will give a friendly introduction to this problem, also known as the permanent-determinant problem (a famous question in theoretical computer science), and discuss why it is also interesting in the context of recent developments in extremal and additive combinatorics (e.g. the Croot-Lev-Pach method).

19:10-19:35  Speaker: Gabriel Istrate. Title: Mechanism Design With Predictions for Obnoxious Facility Location

Abstract: We study mechanism design with predictions for the obnoxious facility location problem. We present deterministic strategyproof mechanisms that display a common tradeoff between robustness and consistency. The common tradeoff is valid for obnoxious facility location on segments, squares, circles and trees. All these mechanisms are actually group strategyproof, with the exception of the case of squares, where manipulations from coalitions of two agents exist. We prove that the  uncovered tradeoff is optimal in the 1-dimensional case. We also deal with the case of agents with dual preferences, showing that the same tradeoff applies. In this case the condition of strategyproofness has to be relaxed, though. We will discuss further issues and open problems raised by our work. Joint work with Cosmin Bonchiș.