Learning quantum observables of low degrees from a logarithmic number of random queries

Speaker: 

Haonan Zhang

Institution: 

UCI

Time: 

Wednesday, January 11, 2023 - 2:00pm to 3:00pm

Host: 

Location: 

510R Rowland Hall

A fundamental problem from computational learning theory is to well-reconstruct an unknown function on the discrete hypercubes. One classical result of this problem for the random query model is the low-degree algorithm of Linial, Mansour and Nisan in 1993. This was improved exponentially by Eskenazis and Ivanisvili in 2022 using a family of polynomial inequalities going back to Littlewood in 1930. Recently, quantum analogs of such polynomial inequalities were conjectured by Rouzé, Wirth and Zhang (2022). This conjecture was resolved by Huang, Chen and Preskill (2022) without knowing it when studying learning problems of quantum dynamics. In this talk, I will discuss another proof of this conjecture that is simpler and gives better estimates. As an application, it allows us to recover the low-degree algorithm of Eskenazis and Ivanisvili in the quantum setting. This is based on arXiv:2210.14468, joint work with Alexander Volberg (MSU).

Robustness of graph/hypergraph properties

Speaker: 

Asaf Ferber

Institution: 

UCI

Time: 

Wednesday, March 1, 2023 - 2:00pm to 3:00pm

Location: 

510R Rowland Hall

In this talk we will consider some notions of `robustness' of graph/hypergraph properties. We will survey some existing results and will try to emphasize the following new result (joint with Adva Mond and Kaarel Haenni): The binomial random digraph $D_{n,p}$
typically contains the minimum between the minimum out- and in-degrees many edge-disjoint Hamilton cycles, given that $p\geq \log^C n/n$, which is optimal up to log factors.

On higher dimensional point sets in general position

Speaker: 

Andrew Suk

Institution: 

UCSD

Time: 

Wednesday, March 15, 2023 - 2:00pm to 3:00pm

Host: 

Location: 

RH 510

An old question of Erdos asks: Given a set of $N$ points in $R^d$ with no $d+2$ members on a common hyperplane, what is the size of the largest subset of points in general position (i.e., no $d+1$ members on a hyperplane)?  In 2018, Balogh and Solymosi showed that one can use the hypergraph container method to tackle this problem in the plane.  In this talk, I will show how to use the container method to tackle Erdos' question in any dimension.  This is joint work with Ji Zeng.

Nonbacktracking Eigenvector Method for Hypergraph Community Detection

Speaker: 

Jamie Haddock

Institution: 

Harvey Mudd College

Time: 

Wednesday, February 22, 2023 - 2:00pm to 3:00pm

Host: 

Location: 

510R Rowland Hall

The hypergraph community detection problem asks us to find groups of related or similar entities in hypergraph data. While there are many approaches to this problem, this talk will focus on a spectral method that utilizes information from the eigenvectors of the nonbacktracking or Hashimoto matrix. The Hashimoto operator can be shown to be related to belief-propagation for statistical inference, and using this relationship we obtain a performant hypergraph community detection algorithm with well-understood regions of success and failure for the hypergraph stochastic block model. The talk will additionally pose some conjectures on the fundamental limits of community detection in hypergraphs.

Sharp density bounds on the finite field Kakeya problem

Speaker: 

Boris Bukh

Institution: 

Carnegie Mellon University

Time: 

Wednesday, March 8, 2023 - 2:00pm to 3:00pm

Host: 

Location: 

RH 510R

 A set is Kakeya if it contains a line in every direction. We prove that every Kakeya set in the $n$-space over $F_q$ has at least
$2^{-n+1}*q^n$ elements. This is sharp up to the lower-order terms. Joint work with Ting-Wei Chao.

Binary iterative hard thresholding for 1-bit Compressed Sensing

Speaker: 

Arya Mazumdar

Institution: 

UCSD

Time: 

Wednesday, January 25, 2023 - 2:00pm

Host: 

Location: 

510R Rowland Hall

Compressed sensing has been a very successful high-dimensional signal acquisition and recovery technique that relies on linear operations. However, the actual measurements of signals have to be quantized before storing or processing. 1(One)-bit compressed sensing is a heavily quantized version of compressed sensing, where each linear measurement of a signal is reduced to just one bit: the sign of the measurement. Once enough of such measurements are collected, the recovery problem in 1-bit compressed sensing aims to find the original signal with as much accuracy as possible. 

For recovery of sparse vectors, a popular reconstruction method from 1-bit measurements is the binary iterative hard thresholding (BIHT) algorithm. The algorithm is a simple projected sub-gradient descent method, and is known to converge well empirically, despite the nonconvexity of the problem. The convergence property of BIHT was not theoretically justified, except with an exorbitantly large number of measurements (i.e., a number of measurement greater than max{k^10,24^48,k^3.5/ϵ}, where k is the sparsity, ϵ denotes the approximation error, and even this expression hides other factors). In this paper we show that the BIHT algorithm converges with only Õ(k/ϵ) measurements. Note that, this dependence on k and ϵ is optimal for any recovery method in 1-bit compressed sensing. With this result, to the best of our knowledge, BIHT is the only practical and efficient (polynomial time) algorithm that requires the optimal number of measurements in all parameters (both k and ϵ). This is also an example of a gradient descent algorithm converging to the correct solution for a nonconvex problem, under suitable structural conditions.

Joint work with Nami Matsumoto.

Graphical Designs

Speaker: 

Stefan Steinerberger

Institution: 

University of Washington

Time: 

Wednesday, February 15, 2023 - 2:00pm to 3:00pm

Host: 

Location: 

510R Rowland Hall

Spherical Designs are very special points on the sphere with the property that the average of a low-degree polynomial over the points is the same as the global average of the polynomial on the sphere. As it turns out, the definition can be suitably interpreted to make sense on a finite combinatorial Graph as well.  The arising structures are breathtakingly pretty (many pictures will be shown). They can be interpreted as the analogue of Platonic bodies in graphs. Graphs can have many more symmetries than Euclidean space and, correspondingly, some of these point structures are remarkably symmetric. This is also naturally related to Extremal Combinatorics where classical Theorems (the Erdos-Ko-Rado Theorem or the Deza-Frankl theorem)  suddenly turn into beautiful special cases.   If we only consider the hypercube graph {0,1}^d, we naturally encounter problems from coding theory.   A probabilistic interpretation tells us new things about the speed with which random walks on the graph become random.   There will be pictures, a survey of recent results by C. Babecki, K. Golubev, D. Shiroma, R. Thomas and many, many open problems.

Community detection in hypergraphs

Speaker: 

Ioana Dumitriu

Institution: 

UCSD

Time: 

Wednesday, February 8, 2023 - 2:00pm to 3:00pm

Host: 

Location: 

510R Rowland Hall

The Hypergraph Stochastic Block Model (HSBM) is a complex, many-parameter model generalizing the well-known graph SBM--a paradigm for studying community detection. One of the main uses of the (H)SBM is that it allows us to develop guarantees for community detection algorithms by providing thresholds---parameter conditions that theoretically describe the necessary and sufficient requirements for community detection in the model. These thresholds naturally depend on the type of recovery desired.

I will talk about the most general conditions and thresholds we can develop, under various tweaks in the model, for almost exact and exact recovery in more, or less, general HSBM. This is joint work with Haixiao Wang and Yizhe Zhu. 

Around the rational exponents conjecture

Speaker: 

David Conlon

Institution: 

Caltech

Time: 

Wednesday, November 2, 2022 - 2:00pm

Host: 

Location: 

510R Rowland Hall

Given a natural number n and a graph H, the extremal number ex(n, H) is the largest number of edges in an H-free graph on n vertices. One of the outstanding questions concerning extremal numbers, originally posed by Erdos and Simonovits, is the rational exponents conjecture, which asks whether for every rational number r between 1 and 2, there is a graph H such that c n^r < ex(n, H) < C n^r for some positive constants c and C. We will discuss some of the recent progress on this conjecture.

Zero bias enhanced Stein couplings for normal approximation

Speaker: 

Larry Goldstein

Institution: 

USC

Time: 

Wednesday, October 19, 2022 - 2:00pm

Location: 

510R Rowland Hall

Stein's method for distributional approximation has become a valuable tool in probability and statistics by providing finite sample distributional bounds for a wide class of target distributions in a number of metrics. A key step in popular versions of the method involves making couplings constructions, and a family of couplings of Chen and Roellin vastly expanded the range of applications for which Stein's method for normal approximation could be applied. This family subsumes both Stein's classical exchangeable pair, and the size bias coupling. A further simple generalization includes zero bias couplings, and also allows for situations where the coupling is not exact. The zero bias versions result in bounds for which often tedious computations of a variance of a conditional expectation is not required. An example to the Lightbulb process shows that even though the method may be simple to apply, it may yield improvements over previous results that had achieved bounds with optimal rates and small, explicit constants. 

 

Pages

Subscribe to RSS - Combinatorics and Probability