Program (final)

Luni/Monday 7 Iunie/June 

(The times below are Romanian times. Subtract 7 for the EDT times)

15:20-15:30 Opening remarks

15:30-15:55 Dan Alistarh. Title: Efficient (Distributed) Algorithms for Machine Learning

Abstract: Machine learning has made considerable progress over the past decade, matching and even surpassing human performance on a varied set of narrow computational tasks. This progress has been enabled by the widespread availability of large datasets, as well as by improved algorithms and models. Distribution, implemented either through single-node concurrency or through multi-node parallelism, has been the third third key ingredient to these advances. The goal of this talk is to provide an overview of the role of efficient (distributed) algorithms in machine learning, with an eye towards the intriguing trade-offs between synchronization and communication costs of distributed machine learning algorithms, on the one hand, and their convergence, on the other. The focus will be on parallelization strategies for the fundamental stochastic gradient descent (SGD) algorithm, which is a key tool when training machine learning models, as well as efficient methods for optimization and compression. In addition, I will provide an overview of ongoing research and open problems in this area.

15:55-16:20 Alex Popa. Title: Efficient algorithms for counting gapped palindromes:

Abstract: A gapped palindrome is a string u v uR, where uR represents the reverse of string u. In this talk we show three efficient algorithms for counting the occurrences of gapped palindromes in a given string S of length N. First, we present a solution in O(N) time for counting all gapped palindromes without additional constraints. Then, in the case where the length of v is constrained to be in an interval [g, G], we show an algorithm with running time O(N logN). Finally, we show an algorithm in O(N logN) time for a more general case where we count gapped palindromes u v uR, where uR starts at position i with g(i) ≤ v ≤G(i), for all positions i.

16:20-16:50 Break 30’

16:50-17:15 Adrian Vladu. Title: Graph Algorithms Through the Lens of Continuous Optimization

Abstract: Recent years have witnessed a surge in the development of fast graph algorithms based on methods from continuous optimization. Classically, graph algorithms have relied on purely combinatorial techniques. However, new ideas stemming from scientific computing and machine learning set forth an emerging theme of algorithm design via continuous optimization. I will provide a tour through some of the techniques that underlie this theme, and show how they can be used to obtain fast algorithms for solving a range of fundamental problems such as maximum flow, minimum cost flow, or negative-weight shortest paths. Additionally, I will show how these modern algorithms offer far reaching insights which can dramatically speed-up standard machine learning primitives.

17:15-17:40 Ileana Streinu. Title: Rigidity, Circuits and Combinatorial Resultants

Abstract:  Given a graph together with positive weights associated to its edges, the “2D Localization” problem asks for a placement of the graph vertices in the Euclidean plane such that the edge lengths match the given weights. A slightly easier case — the “single unknown distance” problem — asks only for the possible values of one unknown distance between a pair of vertices. Both problems can be easily formulated algebraically and could, in principle, be addressed with variations of the doubly-exponential time Groebner Basis algorithm. But of course this is not feasible in practice, even for small cases. Known results from rigidity theory, together with techniques involving algebraic matroids, a theorem of Lovasz and Dress and the formulation of the problem in terms of Cayley (rather than Cartesian) coordinates, help reduce the single-distance problem to the computation of a so-called circuit polynomial in the Cayley-Menger ideal. By taking into account combinatorial rigidity properties of the underlying graphs, we develop a new algorithm that significantly outperforms Groebner Bases for computing such polynomials. We introduce a new operation on graphs called a “combinatorial resultant,” which captures properties of the Sylvester resultant of two polynomials in the algebraic rigidity matroid. We show that every rigidity-circuit graph has a “construction tree,” with this operation marking the tree's interior nodes and with K4 graphs at the leaves. Our algorithm performs an algebraic elimination (using classical resultants) guided by the construction tree. A number of intriguing open questions remain — both combinatorial and algebraic. To demonstrate the effectiveness of our new method, we implemented it in Mathematica: it took less than 15 seconds on an example where a Groebner Basis calculation took 5 days and 6 hrs. (This is joint work with Goran Malic.)

17:40 -18:05 Guillaume Ducoffe. Title: Faster diameter computation within proper minor-closed graph classes.

Abstract: The diameter of an unweighted undirected graph is the maximum distance (in the number of edges) between every two vertices. Computing the diameter has applications in the design of communication networks, and in social network analysis. While there is a textbook algorithm for the problem that runs in polynomial time, it is too slow and it requires too much space for being applied to very large complex networks. We present a faster algorithm for all planar graphs, graphs embedded in a fixed surface, and proper minor-closed graph classes in general, using a very general VC-dimension argument. This is joint work with Michel Habib and Laurent Viennot (Univ. Paris-Diderot, France).

18:05-18:45 Break 40’   

18:45-19:10 Alex Andoni. Title: Approximating Edit Distance in Near-Linear Time

Abstract: Edit distance is a classic measure of similarity between strings, with applications ranging from computational biology to coding. Computing edit distance is also a classic dynamic programming problem, with a quadratic run-time solution, often taught in the "Intro to Algorithms" classes. Improving this runtime has been a decades-old challenge, now ruled likely-impossible using tools from the modern area of fine-grained complexity. We will briefly survey recent research that led to an algorithm *approximating* the edit distance in near-linear time, up to a constant factor. This research direction has been reenergized by the breakthrough paper of [Chakraborty, Das, Goldenberg, Koucky, Saks; FOCS'18], who showed the first constant-factor approximation algorithm with a (strongly) sub-quadratic running time. (Joint work with Negev Shekel Nosatzki (FOCS'20).)

19:10-19:35 Florin Manea. Title: Efficiently Testing Simon’s Congruence

Abstract: Simon’s congruence ∼_k is a relation on words defined by Imre Simon in the 1970s and intensely studied since then. This congruence was initially used in connection to piecewise testable languages, but also found many applications in, e.g., learning theory, databases theory, or linguistics. The ∼_k-relation is defined as follows: two words are ∼_k-congruent if they have the same set of subsequences of length at most k. A long standing open problem, stated already by Simon in his initial works on this topic, was to design an algorithm which computes, given two words s and t, the largest k for which s∼_k t. We propose the first algorithm solving this problem in linear time O(|s|+|t|) when the input words are over the integer alphabet {1,…,|s|+|t|}. Our approach can be extended to an optimal algorithm in the case of general alphabets as well. To achieve these results, we introduce a novel data-structure, called Simon-Tree, which allows us to construct a natural representation of the equivalence classes induced by ∼_k on the set of suffixes of a word, for all k ≥ 1. We show that such a tree can be constructed for an input word in linear time. Then, when working with two words s and t, we compute their respective Simon-Trees and efficiently build a correspondence between the nodes of these trees. This correspondence, which can also be constructed in linear time O(|s|+|t|), allows us to retrieve the largest k for which s∼_k t.

19:35 - SOCIAL and OPEN PROBLEMS 

Marti/Tuesday 8 Iunie/June

15:30-15:55  László Kozma. Title: Self-adjusting trees and heaps

Abstract: Self-adjusting data structures are remarkable due to their simplicity and flexible structure; their analysis, however, often requires sophisticated arguments. Classical examples include splay trees and pairing heaps. Simple variants of these data structure turned out difficult to analyze, and important open questions remain about the original structures as well. (The conjecture that splay trees are constant-competitive is the famous dynamic optimality conjecture.) In this talk I will review some classical results and present a recent data structure (the smooth heap), that is a promising alternative to the pairing heap, both in theory and practice.

15:55-16:20 Mihai Prunescu. Title: The exponential diophantine problem for the rational numbers

Abstract: We prove that deciding whether exponential diophantine equations have rational solutions is algorithmically undecidable. This problem is related to Hilbert's 10th problem.

16:20-16:50 Break 30’

16:50-17:15 Maria Potop-Butucaru. Title: Reliable Distributed Algorithms in the Decentralized Finance Era

Abstract: Blockchain phenomena is similar to the last century gold rush. Blockchain technologies are publicized as being the technical solution for fully decentralizing activities that were for centuries centralized such as administration and finance. Recently, decentralized finance based on blockchain technologies opened a new research field:  reliable distributed economical systems that is a cross research between classical distributed systems, economy  and formal methods. This talk will visit several fault-tolerant distributed algorithms abstractions through the lens of decentralized finance presenting  some results and techniques and open research directions.

17:15-17:40 Alina Ene. Title: A gentle introduction to adaptive optimization

Abstract: In this talk, we take a brief look at some of the most popular and influential iterative algorithms for optimizing modern machine learning models. We will introduce the celebrated Adagrad algorithm (Duchi, Hazan, and Singer; McMahan and Streeter) that uses past gradient information to adaptively set its step sizes. We will briefly discuss some remarkable properties of algorithms in the Adagrad family, including their ability to automatically adapt to unknown problem structure such as (local or global) smoothness and convexity. If time permits, we will also touch upon recent progress on obtaining accelerated Adagrad algorithms that simultaneously achieve optimal convergence in the smooth, non-smooth, and stochastic setting, without any knowledge of the smoothness parameters or the variance of the stochastic gradients.

17:40 -17:50 Break 10'

17:50-18:30  Short presentations:   Ioan Todinca (Université d'Orléans)

                                                        Cosmin Bonchis (Universitatea de Vest, Timisoara)

                                                        Ana-Andreea Stoica (Columbia University)

                                                        Sorin Alexe (QML Alpha LLC) 

18:30-18:45 Break 15’  

18:45-19:10  Simina Branzei.  Title: Searching, Sorting, and Cake Cutting in Rounds

Abstract: We study sorting and searching in rounds motivated by a cake cutting problem.The search problem we consider is: we are given an array x=(x1,…,xn) and an element z promised to be in the array. We have access to an oracle that answers comparison queries and the goal is to find the location of z with success probability at least p∈[0,1] in at most k rounds of interaction with the oracle. The problem is called ordered or unordered search, depending on whether the array x is sorted or unsorted,respectively. We analyze the expected query complexity of randomized and deterministic algorithms, finding a surprising query complexity gap between the performance of randomized algorithms on a worst case input and deterministic algorithms on a worst case input distribution. We also discuss the connections of these search problems to sorting in the rank query model and proportional cake cutting with contiguous pieces. (Based on joint work with Dimitris Paparas and Nicholas Recker.)

19:10-19:35  Sebastian Cioaba.  Title: Spectral graph theory and Theoretical Computer Science

Abstract: Spectral graph theory studies eigenvalues and eigenvectors of various matrices associated with graphs. It plays a key role in theory of expanders graphs (sparse regular graphs whose second largest eigenvalue in absolute value is small compared with its degree) and the design and analysis of the Goemans-Williamson SDP approximation algorithm for the max-cut. More recently, spectral graph theory was fundamental in Huang’s resolution of the Sensitivity Conjecture by using signed adjacency matrices and their eigenvalues. In this talk, I will give an overview of these results and present some open problems.