School “PAC (probably approximately correct) learning and Boolean Harmonic Analysis”

Monday

Noam Lifshitz I

Noam Lifshitz II

Alex Iosevich I

Cristian González-Riquelme

Yuval Filmus

Tuesday

Noam Lifshitz III

Noam Lifshitz IV

Alex Iosevich II

Joseph Slote

Yuval Filmus II

Wednesday

Yuval Filmus III

Alexandros Eskenazis I

Alexander Volberg I

Lars Becker

Alexandros Eskenazis II

Thursday

Alexandros Eskenazis III

Yuval Filmus IV

Alex Iosevich III

Francisco Escudero Gutiérrez

Alexander Volberg II

Friday

Alexandros Eskenazis IV

Alexander Volberg III

Alex Iosevich IV

Miriam Gordin

Alexandros Eskenazis (CNRS, Sorbonne Université): Functional inequalities in Metric Geometry

I will present a collection of results in which discrete functional inequalities play the role of invariants to bi-Lipschitz embeddings of finite graphs into Banach and metric spaces. Examples of such invariants include the nonlinear versions of type and cotype, Markov convexity, diamond convexity, the nonlinear spectral gap inequality, and others. From these, one can in turn deduce nonembeddability results for the Hamming cube, l_∞--grids, trees, diamond graphs and expanders.

Yuval Filmus (Technion – Israel Institute of Technology): Structure theorems in Boolean Harmonic Analysis

Many of the classical theorems in Boolean Function Analysis are structure theorems. Examples include the FKN theorem, Friedgut’s junta theorem, and sharp threshold theorems. We will discuss some classical theorems and some modern ones, focusing on the biased hypercube and on the symmetric group.

Alex Iosevich (University of Rochester): Signal recovery, restriction theory, and applications

Let f: ℤ_N^d → C be a signal and suppose that it is transmitted via its Fourier transform f̂(m)=N^-d Σ_{x ∈ {ℤN}^d} χ(-x · m) f(x), where the frequencies f̂(m)_{m ∈ S} are missing, for some S ⊆ {ℤ}_N^d. The question we ask is, can the original signal f be recovered exactly? Matolcsi and Szuchs, and Donoho and Stark (independently) proved that if f is supported in E ⊆ {ℤ}_N^d with |E||S|<(N^d)/2, then f can be recovered exactly. We are going to see that if S satisfies a non-trivial restriction estimate, the recovery condition can be significantly improved. We are also going to see that multi-linear restriction theory can be used to improve the recovery condition for multiple transmissions. Continuous aspects of this problem will also be discussed with the restriction conjecture described as a signal recovery mechanism.

This is joint work with Azita Mayeli (CUNY).

Noam Lifshitz (Hebrew university of Jerusalem): Inverse results for isoperimetric inequalities

Given a graph, the inverse isoperimetric problem concerns the structure of subsets A of the vertices, with few edges between the set A and its complement A^c. One well known problem in this direction is the Fourier-Entropy-Influence conjecture, which concerns the inverse isoperimetric problem in the Hamming cube. It has applications to PAC learning and also to other areas. In my talk I will discuss some progress towards the conjecture and also several other related inverse isoperimetric inequalities.

Based on joint works with Evra, Kelman, Kindler, Keevash, Minzer, Safra.

Alexander Volberg (Michigan State University): Quantum and classical low degree learning via a dimension-free Remez inequality

Recent efforts in Analysis of Boolean Functions aim to extend core results to new spaces, including noncommutative spaces (matrix algebras). We will present here a new way to relate functions on the hypergrid (or products of cyclic groups) to their harmonic extensions over the polytorus. We show the supremum of a function over products of the cyclic group controls the supremum of function over the entire polytorus , with multiplicative constant not depending on the dimension of polytorus. This inequality is the key ingredient that allows us to extend to new spaces a recent series of algorithms for learning low-degree polynomials on the hypercube and low-degree quantum observables on qubits. In particular, our dimension-free Remez inequality implies cyclic-group Bohnenblust-Hille-type (BH-type) estimates that seem impossible to obtain with existing techniques. And these BH-type estimates in turn enable low-degree learning algorithms for polynomials on the hypergrid and quantum observables. This Remez-type inequality removes the main technical barrier to giving O(log n) sample complexity.

(No recording available)

Lars Becker (Universität Bonn): On the Fourier weight of F2 polynomials

Given a function f on the hypercube F₂ⁿ, define its level k Fourier weight to be the l¹-sum of all its Fourier coefficients associated to sets with k elements. If f is a polynomial of degree d, then how large can its level k Fourier weight be? This question was posed by Chattopadhyay, Hatami, Hosseini and Lovett, motivated by applications to pseudorandom generators. They conjecture an upper bound exponential in k and polynomial in d. We present a proof of this conjecture for level 1 and polynomials of any degree, due to the above listed authors and Tal. Further, we give a proof for degree 2 polynomials and any level k, which is joint work with Alexander Volberg.

Francisco Escudero Gutiérrez (Centrum Wiskunde & Informatica (CWI) and QuSoft): A cb-Bohnenblust-Hille inequality with constant one and its applications in Learning Theory

The main result of this work shows that Bohnenblust-Hille inequality for m- homogeneous polynomials holds with constant one when the operator norm is replaced by the completely bounded norm. Moreover, we show that this inequality nds some interesting consequences in quantum learning theory. In the second part of this paper, we broaden our investigation of the Bohnenblust-Hille inequality to other contexts. In particular, we extend recent results by Volberg and Zhang, demonstrating its applicability within a framework we have termed Learning Low-Degree Quantum Objects.

Cristian González-Riquelme (Instituto Superior Tecnico, Universidade de Lisboa): Sharp Fourier restriction over finite fields

Sharp Fourier restriction theory has been a topic of interest over the last decades. On the other hand, efforts have been made in order to develop the theory of Fourier restriction over finite fields.

In this talk, we will present some recently made developments (in a joint work with Diogo Oliveira e Silva) in the intersection of these two topics.

Miriam Gordin (Princeton University): Vector-valued concentration on the symmetric group

Existing vector-valued concentration inequalities, such as the classical results of Pisier, are known only in very special settings, such as the Gaussian measure on Rⁿ and the uniform measure on the discrete hypercube {-1,1}ⁿ. We present a novel vector-valued concentration inequality for the uniform measure on the symmetric group which goes beyond the product setting of the prior known results. Furthermore, we discuss the implications of this result for the nonembeddability of the symmetric group into Banach spaces of nontrivial Rademacher type, a question of interest in the metric geometry of Banach spaces. We build on prior work of Ivanisvili, van Handel, and Volberg (2020) who proved a vector-valued inequality on the discrete hypercube, resolving a question of Enflo in the metric theory of Banach spaces. This talk is based on joint work with Ramon van Handel.

Joseph Slote (California Institute of Technology): Pseudorandomness and Fourier growth

A central idea in theoretical computer science is that randomness is in the eyes of the beholder: many Boolean functions cannot distinguish between the uniform distribution over the hypercube and certain "pseudorandom" distributions with very small support. In this talk we motivate pseudorandomness, explain how these distributions can sometimes convert randomized algorithms into deterministic ones, and finally exhibit distributions that fool an emerging and important class of Boolean functions: those with bounded Fourier growth.

(No recording available)