Events

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: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,

Title:Benign Optimization Landscape of Formulations for Time-of-Arrival-Based Source Localization Problem

Abstract: : In this talk, we will address the maximum-likelihood (ML) formulation and a least-squares (LS) formulation of the time-of-arrival (TOA)-based source localization problem. Although both formulations are generally non-convex, we will show that they both possess benign optimization landscape. First, we consider the ML formulation of the TOA-based source localization problem. Under standard assumptions on the TOA measurement model, we will show a bound on the distance between an optimal solution and the true target position and establish the local strong convexity of the ML function at its global minima. Second, we consider the LS formulation of the TOA-based source localization problem. We will show that the LS formulation is globally strongly convex under certain condition on the geometric configuration of the anchors and the source and on the measurement noise. We will then derive a characterization of the critical points of the LS formulation, which leads to a bound on the maximum number of critical points under a very mild assumption on the measurement noise and a sufficient condition for the critical points of the LS formulation to be isolated. The said characterization also leads to an algorithm that can find a global optimum of the LS formulation by searching through all critical points. Lastly, we will discuss some possible future directions.

Title: Sequential Contracts on Matroids

Abstract: First, I will talk about the well-known pandora’s box problem, and then I will introduce the generalization of pandora’s box to matroids. We call this problem “sequential contracts on matroids” and we will discuss some recent results about this problem. In particular, we will look at complexity results of the problem. This is joint work with Kanstantsin Pashkovich and Jacob Skitsko for my URA project in Spring 2024.

Title: Positivity of P-Recursive Sequences Satisfying Linear Recurrences

 Abstract: Whether it is decidable to determine when sequences satisfying linear recurrences with constant coefficients have all positive terms is a notorious problem in enumerative combinatorics that has essentially been open for around 90 years. Nevertheless, a "meta-principle" states that all such sequences arising from combinatorial counting problems belong to a special class where positivity (and more general asymptotic

behaviour) is decidable. Here we discuss new software for determining positivity for sequences satisfying linear recurrences with *polynomial* coefficients. Originally motivated by a novel approach to proving genus one solution uniqueness for the Canham model for biomembrane shapes, our algorithm combines rigorous numeric analytic continuation of functions satisfying linear ODEs with singularity analysis techniques from analytic combinatorics. The main talk will be presented using a live Sage Jupyter notebook, and audience members who have access to Sage with a recent version of the ore_algebra package installed (available at

https://github.com/mkauers/ore_algebra) will be able to follow along and play with the package during the talk.

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

Title:A bound on the quantum value of all compiled nonlocal games

Abstract: Nonlocal games provide valuable insights into quantum entanglement and even enable a classical verifier to confirm and control the behavior of entangled quantum provers. However, an issue with this approach has always been the necessity of two non-communicating quantum provers. To address this issue, a group of researchers recently introduced a "compilation procedure" that reduces the need for multiple provers and enforces non-communication through cryptographic methods. In this talk, we will show that even in this single prover "compiled setting," the prover remains fundamentally constrained. Specifically, we show that any polynomial-time quantum prover cannot win the "compiled game" with a higher probability than any quantum commuting provers could win the original nonlocal game. Our result is derived through a novel combination of techniques from cryptography and operator algebras and allows us to recover several important self-testing results in the "compiled setting".