Random permutations using GEPP

Speaker: 

John Peca-Medlin

Institution: 

University of Arizona

Time: 

Wednesday, May 8, 2024 - 2:00pm to 3:00pm

Host: 

Location: 

510R Rowland Hall

Gaussian elimination with partial pivoting (GEPP) remains the most used dense linear solver. For a nxn matrix A, GEPP results in the factorization PA = LU where L and U are lower and upper triangular matrices and P is a permutation matrix. If A is a random matrix, then the associated permutation from the P factor is random. When is this a uniform permutation? How many disjoint cycles are in its cycle decomposition (which equivalently answers how many GEPP pivot movements are needed on A)? What is the longest increasing subsequence of this permutation? We will provide some statistical answers to these questions for select random matrix ensembles and transformations. For particular butterfly permutations, we will present full distributional descriptions for these particular statistics. Moreover, we introduce a random butterfly matrix ensemble that induces the Haar measure on the full 2-Sylow subgroup of the symmetric group on a set of size 2ⁿ.

Online differential privacy

Speaker: 

Yiyun He

Institution: 

UCI

Time: 

Wednesday, April 10, 2024 - 2:00pm to 3:00pm

Location: 

510R Rowland Hall

We present a polynomial-time algorithm for online differentially private synthetic data generation. For a data stream within the hypercube [0,1]^d and an infinite time horizon, we develop an online algorithm that generates a differentially private synthetic dataset at each time t. This algorithm achieves a near-optimal accuracy bound in the 1-Wasserstein distance.

Extreme Eigenvalues of a Random Laplacian Matrix

Speaker: 

Kyle Luh

Institution: 

CU Boulder

Time: 

Wednesday, April 17, 2024 - 2:00pm

Host: 

Location: 

510R Rowland Hall

The extreme eigenvalues of a random matrix have been important objects of study since the inception of random matrix theory and also have a variety of applications.  The Laplacian matrix is the workhorse of spectral graph theory and is the key player in many practical algorithms for graph clustering, network control theory and combinatorial optimization.  In this talk, we discuss the fluctuations of the extreme eigenvalues of a random Laplacian matrix with gaussian entries.  The proof relies on a broad set of techniques from random matrix theory and free probability.  We will also describe some recent progress on a broader class of random Laplacian matrices.

This is joint work with Andrew Campbell and Sean O'Rourke.

Measurable tilings

Speaker: 

Jan Grebik

Institution: 

UCLA

Time: 

Wednesday, April 3, 2024 - 2:00pm to 3:00pm

Host: 

Location: 

510R Rowland Hall

Let $(X,\mu)$ be a standard probability space and $G\curvearrowright (X,\mu)$ be a measure-preserving action of a group $G$ on $X$. The general problem that we consider is to understand the structure of measurable tilings $F\oplus A=X$ of $X$ by a measurable tile $A\subseteq X$ shifted by a finite set $F\subseteq G$, thus the shifts $f\cdot A$, $f\in F$ partition $X$ up to null sets. The motivation comes from the theory of (paradoxical) equidecompositions and tilings in $\mathbb{R}^n$. After a summary of recent results that concern the spheres and tori, I will focus on the intersection of these cases, that is, the case of the circle. Using the structure theorem of Greenfeld and Tao for tilings of $\mathbb{Z}^d$, we show that measurable tilings of the circle can be reduced to tilings of finite cyclic groups.

This is a joint work with Conley and Pikhurko, and Greenfeld, Rozhon and Tao.

A quantum algorithm for learning a hidden graph of bounded degree

Speaker: 

Liam Hardiman

Institution: 

UCI

Time: 

Wednesday, February 14, 2024 - 2:00pm

Location: 

510R Rowland Hall

We are presented with a graph, $G$, on $n$ vertices and $m$ edges whose edge set is unknown. Our goal is to learn the edges of $G$ with as few queries to an oracle as possible. When we submit a set $S$ of vertices to the oracle, it tells us whether or not $S$ induces at least one edge in $G$. This so-called OR-query model has been well studied, with Angluin and Chen giving an upper bound on the number of queries needed of $O(m \log n)$ for a general graph $G$ with $m$ edges.
   
When we allow ourselves to make *quantum* queries (we may query subsets in superposition), then we can achieve speedups over the best possible classical algorithms. In the case where $G$ has maximum degree $d$ and is $O(1)$-colorable, Montanaro and Shao presented an algorithm that learns the edges of $G$ in at most $\tilde{O}( d^2 m^{3/4} )$ quantum queries. This gives an upper bound of $\tilde{O}( m^{3/4} )$ quantum queries when $G$ is a matching or a Hamiltonian cycle, which is significantly larger than the lower bound of $\Omega( \sqrt{m} )$ queries given by Ambainis and Montanaro.

We improve on the work of Montanaro and Shao in the case where $G$ has bounded degree. In particular, we present a randomized algorithm that, with high probability, learns cycles and matchings in $\tilde{O}( \sqrt{m} )$ quantum queries, matching the theoretical lower bound up to logarithmic factors.

Doubly Noisy Linear Systems and the Kaczmarz Algorithm

Speaker: 

Anna Ma

Institution: 

UCI

Time: 

Wednesday, April 24, 2024 - 2:00pm

Host: 

Location: 

510R Rowland Hall

Large-scale linear systems, Ax=b, frequently arise in data science and scientific computing at massive scales, thus demanding effective iterative methods to solve them. Often, these systems are noisy due to operational errors or faulty data-collection processes. In the past decade, the randomized Kaczmarz algorithm (RK) was studied extensively as an efficient iterative solver for such systems. However, the convergence study of RK in the noisy regime is limited and considers measurement noise in the right-hand side vector, b. Unfortunately, that is not always the case, and the coefficient matrix A can also be noisy. In this talk, we motivate and discuss doubly noise linear systems and the performance of the Kaczmarz algorithm applied to such systems. 

Approximately Hadamard matrices and random frames

Speaker: 

Mark Rudelson

Institution: 

University of Michigan

Time: 

Wednesday, February 28, 2024 - 2:00pm

Host: 

Location: 

510R Rowland Hall

We will discuss a problem concerning random frames which arises in signal processing. A frame is an overcomplete set of vectors in the n-dimensional linear space which allows a robust decomposition of any vector in this space as a linear combination of these vectors. Random frames are used in signal processing as a means of encoding since the loss of a fraction of coordinates does not prevent the recovery. We will discuss a question when a random frame contains a copy of a nice (almost orthogonal) basis.

Despite the probabilistic nature of this problem it reduces to a completely deterministic question of existence of approximately Hadamard matrices.  An n by n matrix with plus-minus 1 entries is called Hadamard if it acts on the space as a scaled isometry. Such matrices exist in some, but not in all dimensions. Nevertheless, we will construct plus-minus 1 matrices of every size which act as approximate scaled isometries. This construction will bring us back to probability as we will have to combine number-theoretic and probabilistic methods.

Joint work with Xiaoyu Dong.

Pages

Subscribe to RSS - Combinatorics and Probability