ICTS

Markov chains are among the most popular sampling algorithms both in theory and practice. There is a vast theory on understanding the mixing times of Markov chains. But what if the Markov chain does not mix fast? Can we still use such Markov chains in down-stream applications of sampling, and what theoretical guarantees can we show about these chains? In this talk, we will define a notion of "locally stationary measure" -- which is an analogue of local optima in convex optimization. We will see some generic methods to analyze the structure of distributions that non-mixing Markov chains sample from, along with applications to finding large independent sets in graphs, and finding planted cuts in random graphs. Finally, we will conclude the talk with a set of open questions on locally stationary measures. Based on joint work with Kuikui Liu, Prasad Raghavendra, Amit Rajaraman and David X Wu.

I will present a method to reduce extremal combinatorial problems to establishing the unsatisfiability of k-sparse linear equations mod 2 (aka k-XOR formulas) with a limited amount of randomness. This latter task is then accomplished by bounding the spectral norm of certain "Kikuchi" matrices built from the k-XOR formulas. In these talks, I will discuss a couple of applications of this method from the following list. 

1. Proving hypergraph Moore bound (Feige's 2008 conjecture) -- the optimal trade-off between the number of equations in a system of k-sparse linear equations modulo 2 and the size of the smallest linear dependent subset. This theorem generalizes the famous irregular Moore bound of Alon, Hoory and Linial (2002) for graphs (equivalently, 2-sparse linear equations mod 2).

2. Proving a cubic lower bound on 3-query locally decodable codes (LDCs), improving on a quadratic lower bound of Kerenedis and de Wolf (2004) and its generalization to q-query locally decodable codes for all odd q,  

 3. Proving an exponential lower bound on linear 3-query locally correctable codes (LCCs). This result establishes a sharp separation between 3-query LCCs and 3-query LDCs that are known to admit a construction with a sub-exponential length. It is also the first result to obtain any super-polynomial lower bound for >2-query local codes. 

Time permitting, I may also discuss applications to strengthening Szemeredi's theorem, which asks for establishing the minimal size of a random subset of integers S such that every dense subset of integers contains a 3-term arithmetic progression with a common difference from S, and the resolution of Hamada's 1970 conjecture on the algebraic rank of binary 4-designs. 

I will include pointers to the many open questions and directions where meaningful progress seems within reach for researchers who may get interested in some of the topics.  

I will present a method developed roughly over the past decade and a half that reduces efficient algorithm design to finding "low-degree sum-of-squares" certificates -- thus proofs -- of uniqueness (or, more generally, "list uniqueness") of near-optimal solutions in input instances. This is a principled way of designing and analyzing a semidefinite programming relaxation + rounding algorithm for your target problem. This technique turns out be powerful tool in algorithm design. 

In this tutorial, I will introduce this technique and cover special cases of a couple of recent important applications. The first comes from a recent renaissance of efficient high-dimensional robust statistical estimation, where the proofs-to-algorithms method played a central role in the eventual resolution of the robust Gaussian Mixture learning problem (dating back to Pearson in 1894 and a concrete version due to Vempala in 2010). The second will be drawn from combinatorial optimization. It will focus on finding planted cliques in the semirandom model, answering a question dating back to Feige and Kilian (2001) and, more recently, by Feige (2019) and Steinhardt (2018). 

Both applications are glimpses of a rich research area in which young researchers may find interesting directions for further research.

Since the early days of property testing, the problem of monotonicity testing has been a central problem of study. Despite the simplicity of the problem, the question has led to a (still continuing) flurry of papers over the past two decades. A long standing open problem has been to determine the non-adaptive complexity of monotonicity testing for Boolean functions on hypergrids. 

This talk is about the (almost) resolution of this question, by \sqrt{d} query "path testers". The path to these results is through a beautiful theory of "directed isoperimetry", showing that classic isoperimetric theorems on the Boolean hypercube extend to the directed setting. This fact is surprising, since directed graphs/random walks are often ill-behaved and rarely yield a nice theory. These directed theorems provide an analysis of directed random walks on product domains, which lead to optimal monotonicity testers. 

I will present some of the main tools used in these results, and try to provide an intuitive explanation of directed isoperimetric theorems.

We review the localization method, pioneered by Lov\'asz and Simonovits (1993) and developed substantially by Eldan (2012),  to prove inequalities in high dimension. At its heart, the method uses a sequence of transformations to convert an arbitrary instance to a highly structured one (often even one-dimensional). We will work out some illustrative examples. 

Streaming algorithms make one pass over a massive dataset, and should answer some queries on the data while maintaining a memory footprint sublinear in the data size. We show non-trivial streaming algorithms, and lower bounds, for computing various statistics of data streams
(counts, heavy hitters, and more) as well as for graph problems.

We look at the stability and sensitivity of planar percolation models generated by a Poisson point process under re-sampling dynamics. Noise stability refers to whether certain global percolation events remain unchanged when a small fraction of points are re-sampled, while noise sensitivity means these events become nearly independent even when only arbitrarily small fraction of points are re-sampled.

To analyze these properties, one wants to estimate chaos coefficients in the Wiener-Itô chaos expansion for Poisson functionals, analogue of Fourier-Walsh expansion for functionals of random bits. Motivated by substantial progress in the case of random bits, we introduce two tools to estimate the chaos coefficients. First approach is via stopping sets, which serve as a continuum analogue of randomized algorithms, and the second approach is using pivotal and spectral samples, which provide sharper bounds.

We illustrate these methods using two well-known models: Poisson Boolean percolation, where unit balls are placed at Poisson points, and Voronoi percolation, where Voronoi cells based on Poisson points are randomly retained. Our focus will be on sharp noise sensitivity or stability of crossing events, specifically whether a large rectangle is traversed by a connected component of the percolation model.

The talk is based on joint projects with Chinmoy Bhattacharjee, Guenter Last, and Giovanni Peccati

TBA

This talk explores how problems in private optimization—specifically, low-rank matrix approximation—give rise to novel tools and results in sampling and statistical physics. I will present two recent advances:

Sampling from Harish-Chandra–Itzykson–Zuber (HCIZ) Distributions via Private Optimization:
We introduce an efficient algorithm for computing private low-rank approximations and show how its structure enables efficient sampling from HCIZ measures, which are central to mathematical physics and random matrix theory.

Spectral Sampling and Utility of the Gaussian Mechanism:
We provide a new analysis of the Gaussian Mechanism for differential privacy through the lens of Dyson Brownian motion, yielding refined spectral sampling guarantees and new bounds on eigenvalue gaps in random matrices.

These results illustrate how sampling tasks arising from privacy constraints can lead to powerful connections between random matrix theory, optimization, sampling, and statistical physics.

The online convex paging problem models a broad class of cost  functions for the classical paging problem. In particular, it naturally  captures fairness constraints: e.g., that no specific page (or groups of  pages) suffers an ``unfairly'' high number of evictions by considering
$\ell_p$ norms of  eviction vectors for $p>1$. The case of the $\ell_\infty$ norm has also been of special interest, and is called  min-max paging.

We give tight upper and lower bounds for the convex paging problem for a  broad class of convex functions.  Prior to our work, only fractional algorithms were known for this general setting. Moreover, our general result also improves on prior works for special cases of the problem.   For example, it implies that the randomized competitive ratio of the  min-max paging problem is $\Theta(\log k\log n)$; this improves both the  upper bound and the lower bound given in prior work by logarithmic factors. It also shows that the randomized and deterministic competitive
ratios for $\ell_p$-norm paging are $\Theta(p\log k)$ and $\Theta(pk)$  respectively.

This is joint work with Anupam Gupta and Debmalya Panigrahi.