Events

Title: Entropy and the growth rate of universal covering trees

Abstract:This work studies the relation between two graph parameters, rho and Lambda. For an undirected graph G,  rho(G) is the growth rate of its universal covering tree, while Lambda(G) is a weighted geometric average of the vertex degree minus one, corresponding to the rate of entropy growth for the non-backtracking random walk (NBRW). It is well known that rho >= Lambda for all graphs, and that graphs with rho = Lambda exhibit some special properties. In this work we derive an easy to check, necessary and sufficient condition for the equality to hold. Furthermore, we show that the variance of the number of random bits used by a length l NBRW is O(1) if rho = Lambda and Omega(l) if rho > Lambda. As a consequence we exhibit infinitely many non-trivial examples of graphs with rho = Lambda.

Joint work with Idan Eisner, Tel-Hai College, Israel.

Title: New perspectives on quasisymmetry via divided differences, flag varieties, etc.

 Abstract: In this talk we will introduce a new combinatorial approach to understanding quasisymmetric polynomials via a quasisymmetric analogue of "divided differences". The resulting combinatorial theory is paired with a geometric theory that closely follows the classical development of Schubert calculus and Schubert varieties. Next week Nantel Bergeron will continue with the torus-equivariant story.

There will be a pre-seminar presenting relevant background at the beginning graduate level starting at 1pm,

Title: A New Complexity Analysis of Primal-Dual Interior-Point Methods with Applications to Hyperbolic Cone Programming

Abstract: Primal-dual interior-point methods stand at the forefront of convex optimization, distinguished by their theoretical efficiency and practical robustness. After presenting the fundamental 
structure of these algorithms, I will introduce a complexity measure for a large family of primal-dual algorithms. A consequence of the new analyses of this complexity measure is a substantial improvement of the iteration 
complexity bounds for these primal-dual algorithms on hyperbolic cone programming problems.

This talk is based on joint work with Joachim Dahl and Lieven Vandenberghe.

Title: : Algebraic bounds for sum-rank-metric codes

Abstract:The sum-rank metric is a generalization of the well-known Hamming and rank metrics. In this talk we introduce two new bounds on the maximal cardinality of the sum-rank-metric code with a given minimum distance. One of the bounds exploits a connection between such a code and a (d-1)-independent set in a graph defined for the sum-rank-metric space. We then use the eigenvalues of the graph to deduce the bound. The second bound is derived from the Delsarte's LP method, which has been previously obtained for Hamming metric, rank metric, Lee metric, and others, but the sum-rank-metric case remained open. To derive the new LP bound we propose a way to construct an association scheme for the sum-rank metric, since the approach used in the Hamming and the rank-metric cases fails due to the associated graph not being distance-regular in general. Based on computational experiments on relatively small instances, we observe that the obtained bounds often outperform the bounds previously known for sum-rank-metric codes.

This talk is based on a joint work with A. Abiad, A.L. Gavrilyuk, A. Ravagnani, and I. Ponomarenko.

Title: Structure of tournaments with a forbidden subtournament

Abstract: For a tournament $S$, a tournament is $S$-free if it has no subtournament isomorphic to $S$. Until now, there have been only a small number of tournaments $S$ such that the complete structure of $S$-free tournaments is known. 

Let $\triangle(1, 2, 2)$ be a tournament obtained from the cyclic triangle by substituting two-vertex tournaments for two of its vertices. In this talk, we present a structure theorem for $\triangle(1, 2, 2)$-free tournaments, which was previously unknown. As an application, we provide tight bounds for the chromatic number as well as the size of the largest transitive subtournament for such tournaments.

This talk is based on joint work with Taite LaGrange, Mathieu Rundström, Arpan Sadhukhan, and Sophie Spirkl.

Title: Statistical Fluctuations in the Causal Set-Continuum Correspondence

 Abstract: Causal set theory is an approach to quantum gravity that proposes that spacetime is fundamentally discrete and the causal relations among the discrete elements play a prominent role in the physics. Progress has been made in recognizing and understanding how some continuumlike features can emerge from causal sets at macroscopic scales, i.e., when the number of elements is large. An important result in this context is that a causal set is well approximated by a continuum spacetime if there is a number-volume correspondence between the causal set and spacetime.

This occurs when the number of elements within an arbitrary spacetime region is proportional to its volume. Such a correspondence is known to be best achieved when the number of causal set elements is randomly distributed according to the Poisson distribution. I will discuss the Poisson distribution and the statistical fluctuations it induces in the causal set-continuum correspondence, highlighting why it is important and interesting. I will also discuss new tools and techniques that facilitate such analyses.

There will be a pre-seminar presenting relevant background at the beginning graduate level starting at 1pm,

Title:Accuracy Aware Minimally Invasive Data Exploration For Decision Support

Abstract: Decision-support (DS) applications, crucial for timely and informed decision-making, often analyze sensitive data, raising significant privacy concerns. While privacy-preserving randomized mechanisms can mitigate these concerns, they introduce the risk of both false positives and false negatives. Critically, in DS applications, the number of false negatives often needs to be strictly controlled. Existing privacy-preserving techniques like differential privacy, even when adapted, struggle to meet this requirement without substantial privacy leakage, particularly when data distributions are skewed. This talk introduces a novel approach to minimally invasive data exploration for decision support. Our method minimizes privacy loss while guaranteeing a bound on false negatives by dynamically adapting privacy levels based on the underlying data distribution. We further extend this approach to handle complex DS queries, which may involve multiple conditions on diverse aggregate statistics combined through logical disjunction and conjunction. Specifically, we define complex DS queries and their associated accuracy requirements, and present algorithms that strategically allocate a privacy budget to minimize overall privacy loss while satisfying the bounded accuracy guarantee.

Title: Combinatorial Contract Theory

AbstractFirst, I will introduce the contract theory setting. Afterwards, we'll survey some approximation and hardness of approximation results in the land of combinatorial contract theory. We'll talk briefly about the flavour of techniques used in such results. This should exemplify a few typical approaches taken in this setting. With any luck, we'll all find the level of detail pleasant. The main results will be from Multi-Agent Contracts (STOC 23) and On The (In)approximability of Combinatorial Contracts (ITCS 24). We may take a dip into results from Multi-Agent Combinatorial Contracts (SODA 25) or other papers, time permitting.

Title: Spherical friezes

 Abstract: A fundamental problem in spherical distance geometry aims to recover an $n$-tuple of points on a 2-sphere in $\mathbb{R}^3$, viewed up to oriented isometry, from $O(n)$ input measurements. This talk will discuss an algebraic solution to this problem using only the four arithmetic operations. We will show how a new type of frieze pattern can be employed to arrange the measurement data. These friezes exhibit glide symmetry and a version of the Laurent phenomenon.

There will be a pre-seminar presenting relevant background at the beginning graduate level starting at 1pm,

Title:What is New in Join-Aggregate Query Processing?

Abstract: Join-aggregate queries defined over commutative semirings subsume a wide variety of common algorithmic problems, such as graph pattern matching, graph colorability, matrix multiplication, and constraint satisfaction problems. Developing efficient algorithms for computing join-aggregate queries in the conventional RAM model has been a holy grail in database theory. One of the most celebrated results in this area is the Yannakakis algorithm dating back to 1981. Despite its prominence as a textbook solution, no improvements in its complexity have been made over the past 40 years. In this talk, I will present the first algorithm that improves upon Yannakakis for computing acyclic join-aggregate queries. Moreover, this algorithm is proven to be output-optimal among all combinatorial algorithms. One application is an output-optimal algorithm for chain matrix multiplication over sparse matrices. Beyond combinatorial algorithms, I will also show how fast matrix multiplication can further speed up the processing of conjunctive queries, a critical subclass of join-aggregate queries. Finally, I will highlight a few interesting open problems in this area.