Events

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.

Title: : Precise Eigenvalue Location for Random Regular Graphs

Abstract:The spectral theory of regular graphs has broad applications in theoretical computer science, statistical physics, and other areas of mathematics. Graphs with optimally large spectral gap are known as Ramanujan graphs. Previous constructions of Ramanujan graphs are based on number theory and have specific constraints on the degree and number of vertices. In this talk, we show that, in fact, most regular graphs are Ramanujan; specifically, a randomly selected regular graph has a probability of 69% of being Ramanujan. We establish this through a rigorous analysis of the Green’s function of the adjacency operator, focusing on its behavior under random edge switches.

Title:Two-coloured lines in finite geometry

Abstract: Given a colouring of the points of a projective plane, when is it true that every line contains at most two colours? I will discuss recent generalizations of classical results in this area, and a surprising link with a famous question in graph theory.

Title: Operahedron Lattices

 Abstract: Two classical lattices are the Tamari lattice on bracketings of a word and the weak order on permutations. The Hasse diagram of each of these lattices is the oriented 1-skeleton of a polytope, theassociahedron and the permutohedron respectively. We examine a poset on bracketings of rooted trees whose Hasse diagram is the oriented 1-skeleton of a polytope called th operahedron. We show this poset is a lattice which answers question of Laplante-Anfossi. These lattices provide an extremelynatural generalization of both the Tamari lattice and the weak order.

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