The Gaussian distribution is widely used in mechanism design for differential privacy (DP). Thanks to its sub-Gaussian tail, it significantly reduces the chance of outliers when responding to queries. However, it can only provide approximate DP. In this paper, we introduce and analyze a new distribution for use in DP that is based on the Gaussian distribution, but it has improved privacy performance. The so-called offset-symmetric Gaussian tail (OSGT) distribution is obtained through using the normalized tails of two symmetric Gaussians around zero. Consequently, it can still have sub-Gaussian tail and lend itself to analytical derivations. We analytically derive the variance of the OSGT random variable and its differential privacy metrics. Numerical results show the OSGT mechanism can offer better privacy-utility performance compared to the Gaussian and Laplace mechanisms.
Free resolutions are algebraic constructs that encode interesting invariants, called Betti numbers, of rings, ideals, and modules. Under mild assumptions, a group action on the object being resolved lifts to its resolutions, which enables the use of representation theory to describe resolutions. I will illustrate these concepts using the ideal generated by all squarefree monomials of a given degree as an example, and show how representation theory leads to a nice combinatorial description of Betti numbers.
The handle slide operation, originally defined for ribbon graphs, was extended to delta-matroids by I. Moffatt and E. Mphako-Bandab, whoshow that, using a delta-matroid analogue of handle slides, every binary delta-matroid in which the empty set is feasible can be written in a canonical form analogous to the canonical form for one-vertex maps on a surface.
We provide a canonical form for binary delta-matroids without restriction on the feasibility of the empty set. This is joint work with Remi Cocu Avohou.
This talk is divided into three parts. The first part introduces the Koszul property, why it is a desirable property for an algebra, along with methods and difficulties in determining when it is satisfied.
The second part introduces Strongly Stable Ideals through examples. We then describe some of their combinatorial properties and what benefits one obtains from studying them.
In the third part, we discuss a historical overview of results regarding the characterization of Rees and multiRees algebras of Strongly Stable Ideals that are Koszul, starting with a result from Emmanuela DeNegri (1994) up to the most recent result from Selvi Kara, Kuei-Nuan Lina and myself (2020).
Let G be a simple graph with maximum degree Delta(G). A subgraph H of G is overfull if |E(H)|>Delta(G) is greater than the floor function of |V(H)|/2. Chetwynd and Hilton in 1985 conjectured that a graph G with \Delta(G)>|V(G)|/3 has chromatic index \Delta(G) if and only if G contains no overfull subgraph. In this talk, we will survey some recent progress towards the conjecture. In particular, we will mention the confirmation of the conjecture on graphs with a small core degree, dense quasi-random graphs of odd order, and large graphs of order 2n and minimum degree at least (1+\varepsilon)n for any 0<\varepsilon<1.
Domino ideals are a class of monomial ideals whose generating sets correspond to the sets of domino tilings of a2 x n tableau. It is well known that the number of domino tilings of a 2 x n tableau is given by a Fibonacci number. This talk will consider the graded Betti numbers from the minimal free resolution of a domino ideal, and the relationship between the Fibonacci numbers and the graded Betti numbers of the corresponding domino ideal. Additionally, the application of the Eliahou–Kervaire splitting of a monomial ideal will be discussed within the context of these domino ideals.
We consider the private multi-group aggregation (PMGA) problem. This setting involves n users, and each user belongs to one of k distinct groups and holds an integer value. A central server wants to find the aggregate (sum) of the values in each group (with high accuracy) under communication and local differential privacy constraints. The privacy constraint guarantees that the user’s group remains private. This is motivated by applications where a user’s group can reveal sensitive information, such as religious and political beliefs, health conditions, or race.
In this talk, we will introduce the Query and Aggregate (Q&A) scheme for PMGA. The novelty of Q&A is that it is an interactive aggregation scheme. In Q&A, each user is assigned a random query matrix, to which he sends the server an answer based on his group and value. We will compare Q&A to the Randomized Group (RG) scheme, which is non-interactive and adapts existing randomized response schemes to the PMGA setting.
Motivated by large-scale storage problems around data loss, a budding branch of coding theory has surfaced in the last decade or so, centered around locally recoverable codes. These codes have the property that individual symbols in a codeword are functions of other symbols in the same word. If a symbol is lost (as opposed to corrupted), it can be recomputed, and hence a code word can be repaired. Algebraic geometry has a role to play in the design of codes with locality properties. In this talk I will explain how to use algebraic surfaces to both reinterpret constructions of optimal codes already found in the literature, and to find new locally recoverable codes, many of which are optimal (in a suitable sense). This is joint work with Cecília Salgado and Felipe Voloch.
Recent progress on the Auslander-Reiten and Huneke-Weigand Conjectures
Various conjectures have emerged as far back as the 1950’s concerning conditions on the vanishing of Ext/Tor. Among the most celebrated are the Auslander-Reiten and Huneke-Wiegand conjectures, which pose that a finitely-generated module over a commutative Noetherian ring should be free in certain scenarios. We will discuss some recent progress on these conjectures. In particular, we will journey through some surprising connections between the Huneke-Wiegand conjecture and several seemingly disparate theories. Using these ideas we will provide conditions, some necessary and some sufficient, for the Huneke-Wiegand conjecture to hold. As a culmination, we will discuss a recent proof of the speaker of the Auslander-Reiten conjecture for graded Gorenstein domains.
Lattice reduction algorithms have received much attention in recent years due to their relevance in cryptography. In this talk, we will discuss some of the recent developments on enumeration-based lattice reduction algorithms.
First, we will discuss a lattice reduction algorithm that achieves root Hermite factor k^(1/(2k)) in time k^(k/8 + o(k)) and polynomial memory. This improves the previously best known enumeration-based algorithms which achieve the same quality, but in time k^(k/(2e) +o(k)). The main idea is to conduct the preprocessing in a larger dimension than the enumerate dimension. Second, we discuss the usage of approximate enumeration oracles in BKZ, together with extended preprocessing ideas. In the end, we will illustrate some simulated results to demonstrate their practical behavior.
This talk is based on the following joint work:
M. R. Albrecht, S. Bai, P. A. Fouque, P. Kirchner, D. Stehlé, W. Wen: Faster Enumeration-Based Lattice Reduction: Root Hermite Factor k^(1/(2k)) Time k^(k/8+o(k)). CRYPTO (2) 2020: 186-212.
M. R. Albrecht, S. Bai, J. Li, J. Rowell: Lattice Reduction with Approximate Enumeration Oracles – Practical Algorithms and Concrete Performance. CRYPTO (2) 2021: 732-759.