Workshop: Information theory, Boolean functions, and lattice problems

Monday

Chandra Nair

Lisa Sauermann

Noah Stephens-Davidowitz

Piotr Nayar

Tuesday

Igal Sason

Sergey Tikhonov

Joseph Slote

Wednesday

Thomas Courtade

James Melbourne

Tomasz Tkocz

Thursday

Gautam Aishwarya

Emma Pollard

Bruno Volzone

Friday

Dario Cordero-Erausquin

Felipe Ferreira Goncalves

Gautam Aishwarya (Technion - Israel Institute of Technology): A Shannon-Kneser-Poulsen theorem

Consider the following questions.

Question 1: Does the volume of a union of balls decrease if their centres are brought pairwise closer?

Question 2: Does communication over an additive white Gaussian noise channel worsen if the transmitters are brought pairwise closer?

These questions appeal to our basic intuition about geometry and information transmission, which seems to suggest the answer to both of them is yes. The first question is open; the Kneser-Poulsen conjecture asserts that it has an affirmative answer. In this talk, based on well-known analogies between convex geometry and information theory, we will frame (and prove) the natural entropic formulation of the Kneser-Poulsen conjecture. As a corollary, an affirmative answer to the second question is obtained.

This talk is based on joint work with Dongbin Li.

Dario Cordero-Erausquin (Sorbonne Université): Convexity, duality and heat diffusion

Motivated by a semi-group approach to the Blaschke-Santalo inequality, we will discuss how log-concavity and duality (in the form of the Legendre transform) evolve along Gaussian diffusions.

Based on two joint works with Nathael Gozlan, Shohei Nakamura, Hiroshi Tsuji and M. Fradelizi, D. Langharst.

Thomas Courtade (University of California, Berkeley): Information inequalities on Euclidean space

This talk will cover recent developments in information inequalities, with an emphasis on unifying perspectives. In particular, I'll present a general class of entropy inequalities, and demonstrate a variety of applications to information theory, analysis, geometry, statistics (and more!).

This talk is based in part on joint works with Efe Aras and Jingbo Liu.

Felipe Ferreira Goncalves (IMPA - Instituto de Matematica Pura e Aplicada): Linear Programming, Sign Uncertainty, and Sphere packings

In this talk we shall try to explain the unexpected connection between the sphere packing problem and the sign uncertainty phenomenon, and how one can solve some of these problems in dimensions 8, 12, 24 and 48 using modular forms.

(No recording available.)

James Melbourne (Centro de Investigación en Matemáticas, A.C.): On the Entropy Power of Sums of Dependent Random Variables and Related Inequalities

We prove a generalization of the Entropy Power Inequality (EPI) for dependent random variables, showing that in particular, the EPI can be extended to variables with jointly log supermodular densities. A key tool is the confirmation of a recent conjecture of Zartash and Robeva, that log supermodularity is preserved under Gaussian convolution. We demonstrate this result as a corollary of the four function theorem of Ahlswede–Daykin in Euclidean space, for which we will present a transportation proof that contains the classical Prekopa Liendler inequality as well.

(Pending permission to publish the recording)

Chandra Nair (The Chinese University of Hong Kong): Some conjectures relating the optimality of dictator functions and connections to discrete isoperimetric inequalities

In this talk, we will present a family of conjectures that postulate the optimality of dictator functions (each corresponding to a parameterized family of entropy functions). We will show that the conjectures are ordered by the parameters: i.e. proving the conjecture for a smaller value of the parameter will imply those for a larger value. Then, we will relate the extreme parameter case to isoperimetric inequalities on the discrete Hamming cube studied by Talagrand and Bobkov.

Piotr Nayar (University of Warsaw): Minimum entropy of a log-concave random variable with fixed variance

We show that for log-concave real random variables with fixed variance the Shannon differential entropy is minimized for an exponential random variable. We apply this result to derive upper bounds on capacities of additive noise channels with log-concave noise. We also improve constants in the reverse entropy power inequalities for log-concave random variables.

Based on a joint work with James Melbourne and Cyril Roberto

Emma Pollard (Boise State University): Symmetrization Resistance

An asymmetric random variable X is said to be symmetrization resistant if every independent random variable Y that produces a symmetric sum X+Y has a greater variance than that of X. Asymmetric Bernoulli random variables were shown to be symmetrization resistant by Kagan, Mallows, Shepp, Vanderbei, and Vardi (1999); Pal (2008) gave a proof using stochastic calculus. Proving symmetrization resistance appears to be difficult: little is known about other asymmetric distributions. We introduce the notion of entropic symmetrization resistance, which is the same as symmetrization resistance except that the entropy (rather than variance) of Y must exceed that of X. We show that Bernoulli random variables exhibit entropic symmetrization resistance exactly when they exhibit symmetrization resistance. We also extend the underlying entropy and variance inequalities to the hypercube. Finally, we explore the possibility of extensions to non-Bernoulli random variables.

This talk is based on joint work with Mokshay Madiman.

Igal Sason (Technion - Israel Institute of Technology): Combinatorial Applications of the Shearer and Han Inequalities in Graph Theory and Boolean Functions.

Shearer’s and Han’s inequalities in information theory have significant combinatorial applications, particularly in areas such as graph theory, Boolean functions, and lattice problems. This talk explores several formulations of these inequalities and delves into some of their intriguing applications, highlighting their utility in solving combinatorial problems across these domains.

Lisa Sauermann (Endenicher Allee 60): The quadratic Littlewood-Offord Problem

Let Q(x_1,…,x_n) be a given quadratic polynomial, and consider xi_1,..,xi_n to be independent unbiased {1,-1}-valued random variables (i.e. each xi_i takes value 1 with probability 1/2 and value -1 with probability 1/2). To what extent can Q(xi_1,...,xi_n) concentrate on a single value? This question is a quadratic version of the classical Littlewood–Offord problem for linear polynomials. It was popularised by Costello, Tao and Vu in their study of symmetric random matrices, and also has connections to the Gotsman-Linial conjecture in Boolean Analysis. This talk will discuss an essentially optimal bound for this question, as conjectured by Nguyen and Vu.

Joint work with Matthew Kwan.

(Pending permission to publish the recording)

Joseph Slote (California Institute of Technology): Fourier multipliers for functions on the discrete

Functions on the discrete n-torus ℤ_Kⁿ are natural objects in several areas, but functional inequalities that are standard on the hypercube (K=2) and the n-torus (K=∞) are harder to obtain for intermediate K. We present a class of Fourier multipliers which are bounded independent of dimension when applied to functions on ℤ_Kⁿ with low-degree Fourier expansions. From these we obtain a proof of Figiel’s inequalities for Rademacher projections on level-l characters, as well as bounded projections onto much finer-grained sets of characters thanks to connections to transcendental number theory (including an appearance of Baker’s theorem). As an application we show a dimension-free Bernstein-type discretization inequality, with ℤ_Kⁿ as our sampling set.

Noah Stephens-Davidowitz (Cornell University): A reverse Minkowski theorem

Minkowski's celebrated first theorem is one of the foundational results in the study of the geometry of numbers, and it has innumerable applications from number theory to convex geometry to cryptography. It tells us that a lattice (i.e., a linear transformation of Z^n) that is globally dense (i.e., has low determinant) must be locally dense (i.e., must have many short vectors). We will show a proof of a nearly tight converse to Minkowski's theorem, originally conjectured by Daniel Dadush -- a lattice with many short points must have a sublattice with small determinant. This "reverse Minkowski theorem" has numerous applications in, e.g., complexity theory, additive combinatorics, cryptography, the study of Brownian motion on flat tori, algorithms for lattice problems, etc. Just recently, it was used by Reis and Rothvoss to give the first asymptotic improvement to integer programming in nearly forty years.

Based on joint work with Oded Regev.

Sergey Tikhonov (ICREA and CRM): Polynomial inequalities and discretization

We survey recent developments in a study of the following classical inequalities for polynomials: Bernstein, Nikolskii, Remez as well as their connections to discretization.

(No recording available.)