Universität Bonn

Dual Trimester Program: "Boolean Analysis in Computer Science"


September 9 - December 18, 2024

Organizers: Sergey Bobkov, Polona Durcik, Alexandros Eskenazis, Irina Holmes Fay, Paata Ivanisvili, Dor Minzer, and Alexander Volberg

Description: The trimester program aims to  bring together experts, postdocs, and students in computer science and certain areas in mathematics (analysis, probability, and combinatorics) in order to learn about some challenging open problems recently raised in computer science, to use and invent necessary new tools and techniques in mathematics to solve these challenging problems, and vice versa to learn and further extend methods developed in computer science to develop new directions in mathematics motivated by questions in computer science. The core topics of the trimester program would be:  learning theory, complexity of classical and quantum algorithms, vector valued functions on the hypercube, complex Hypercontractivity, polynomial inequalities on the hypercube, and discrete approximation theory on the hamming cube.

The due-date for application has expired and the application platform is closed.


Participants

PERSON
AFFILIATION
PERIOD OF STAY
Gautam Aishwarya
Technion - Israel Institute of Technology
20.10.2024 - 18.12.2024
Florent Baudier
Texas A&M University
 06.10.2024 - 12.10.2024
Lars Becker
Universität Bonn
09.09.2024 - 18.12.2024
David Beltran
Universitat de Valencia
07.10.2024 - 19.10.2024
Pierre Bizeul
Technion
03.11.2024 - 18.12.2024
Sergey Bobkov
University of Minnesota
09.10.2024 - 18.12.2024
Alexander Borichev
Aix Marseille University
17.10.2024 - 06.11.2024
Xiaonan Chen
University of California, Irvine
03.11.2024 - 29.11.2024
Valentina Ciccone
Universität Bonn
09.09.2024 - 18.12.2024
Dario Cordero-Erausquin
Sorbonne Université
17.11.2024 - 22.11.2024
Jaume de Dios Pont
ETHZ
 12.10.2024 - 25.10.2024
Oliver Dragičević
University of Ljubljana
02.11.2024 - 10.11.2024
Devraj Duggal
University of Minnesota
13.09.2024 - 18.12.2024
Polona Durcik
Chapman University
09.09.2024 - 18.10.2024
28.10.2024 - 18.12.2024
Alexandros Eskenazis
CNRS, Sorbonne Université
09.09.2024 - 08.12.2024
Francisco Escudero Gutiérrez
Centrum Wiskunde & Informatica (CWI) and QuSoft
15.09.2024 - 08.11.2024
Yuval Filmus
Technion - Israel Institute of Technology
09.09.2024 - 22.09.2024

02.10.2024 - 27.10.2024

Felipe Ferreira Goncalves
IMPA
03.11.2024 - 22.11.2024
Miriam  Gordin
Princeton University
10.09.2024 - 25.09.2024
Marco Fraccaroli
Basque Center for Applied Mathematics
15.09.2024 - 18.10.2024
Dmitry Grigoryev
CNRS, Université de Lille
09.09.2024 - 18.12.2024
Kornélia Héra
Universität Bonn
07.10.2024 - 18.12.2024
Tuomas Hytönen
Aalto University
15.09.2024 - 11.10.2024
Alex Iosevich
University of Rochester
15.09.2024 - 28.09.2024
Benjamin Jaye
Georgia Tech
30.11.2024 - 14.12.2024
Guy Kindler
The Hebrew University of Jerusalem
09.09.2024 - 18.12.2024
Ohad Klein
The Hebrew University of Jerusalem
03.11.2024 - 13.11.2024
Egor Kosov
Centre de Recerca Matemàtica
18.11.2024 - 17.12.2024
Vjekoslav Kovač
University of Zagreb
06.10.2024 - 11.10.2024
Dmitrii Krachun
Princeton University
05.11.2024 - 09.11.2024
Cosmas Kravaris
Princeton University
06.10.2024 - 19.10.2024
Rafal Latala
University of Warsaw
09.09.2024 - 04.10.2024
Noam Lifshitz
The Hebrew University of Jerusalem
09.09.2024 - 18.09.2024
Galyna Livshyts
Georgia Institute of Technology
30.11.2024 - 14.12.2024
Jose Ramon Madrid Padilla
Virginia Polytechnic Institute and State University
07.10.2024 - 15.10.2024
Nathan Mehlhop
Lousiana State University
25.11.2024 - 18.12.2024
James Melbourne
Centro de Investigación en Matemáticas, A.C.
13.09.2024 - 23.11.2024
Kristina Oganesyan
University of Ghent
24.11.2024 - 18.12.2024
Krzysztof Oleszkiewicz
University of Warsaw
09.09.2024 - 30.09.2024
Diogo Oliveira e Silva
Instituto Superior Técnico Lisboa
09.09.2024 - 18.12.2024
Emma Pollard
Boise State University
09.09.2024 - 06.12.2024
Cyril Roberto
Univesrité Paris Nanterre
26.10.2024 - 09.11.2024
Joris Roos
University of Massachusetts Lowell
09.09.2024 - 07.12.2024
Miquel Saucedo
Universitat Autònoma de Barcelona
09.09.2024 - 18.12.2024
Gideon Schechtman
Weizmann Institute of Science
06.10.2024 - 31.10.2024
Rocco Servedio
Columbia University
22.09.2024 - 12.10.2024
Lenka Slavíkóva
Charles University
06.10.2024 - 19.10.2024
Joseph Slote
California Institute of Technology
02.10.2024 - 05.12.2024

Rajula Srivastava

Universität Bonn
09.09.2024 - 18.12.2024
Lauritz Streck
University of Cambridge
06.10.2024 - 29.11.2024
Maude Szusterman
Tel Aviv University
15.09.2024 - 15.12.2024
Sergey Tikhonov
ICREA and CRM
29.09.2024 - 12.10.2024

17.11.2024 - 30.11.2024

Tomasz Tkocz
Carnegie Mellon University
17.11.2024 - 23.11.2024
Gennady Uratsev
University of Arkansas
06.10.2024 - 18.12.2024
Akanksha Vishwakarma Roos
self-affiliated
17.11.2024 - 30.11.2024
Alexander Volberg
Michigan State University
09.09.2024 - 18.12.2024
Bruno Volzone Politecnico di Milano
10.10.2024 - 10.11.2024
Blazej Wróbel
Polish Academy of Sciences
06.10.2024 - 16.10.2024
Kenwen Wu
University of California, Berkeley
03.11.2024 - 16.11.2024
Xudong Wu
Nanjing University
03.11.2024 - 29.11.2024
Xinyuan Xie
University of Califronia, Irvine
15.09.2024 - 18.12.2024
Quanhua Xu
Université de Franche-Comté
07.10.2024- 12.10.2024
Haonan Zhang
University of South Carolina
04.10.2024 - 03.11.2024

PERSON
AFFILIATION
PERIOD OF STAY
Luis Eduardo Aceves González
Lars Becker
Valentina Ciccone
Devraj Duggal
Polona Durcik
Francisco Escudero Gutiérrez
Alexandros Eskenazis
Yuval Filmus
Marco Fraccaroli
Li Gao
Cristian Andres Gonzalez Riquelme
Miriam Gordin
Tuomas Hytönen
Alex Iosevich
Guy Kindler
Rafal Latala
Yongjin Lee
Zane Li
Noam Lifshitz
James Melbourne
Siddharth Mulherkar
Giuseppe Negro
Krzysztof Oleszkiewicz
Diogo Oliveira e Silva
Emma Pollard
Joris Roos
Miquel Saucedo
Shobu Shiraki
Joseph Slote
Maud Szusterman
Alexander Volberg
Xinyuan Xie
Texas A&M University
Universität Bonn
Universität Bonn
University of Minnesota-Twin Cities
Chapman University
Centrum Wiskunde & Informatica (CWI) and QuSoft
CNRS, Sorbonne Université
Technion – Israel Institute of Technology
BCAM - Basque Center for Applied Mathematics
Wuhan University
Instituto Superior Tecnico, Universidade de Lisboa
Princeton University
Aalto University
University of Rochester
The Hebrew University of Jerusalem
University of Warsaw
University of Illinois Urbana-Champaign
North Carolina State University
Hebrew university of Jerusalem
Centro de Investigación en Matemáticas, A.C.
University of California, Los Angeles
Instituto Superior Técnico
University of Warsaw
Instituto Superior Técnico
Boise State University
University of Massachusetts Lowell
Universitat Autònoma de Barcelona
Instituto Superior Técnico
California Institute of Technology
Tel Aviv University
Michigan State University
University of California, Irvine
 
 
 
 
PERSON
AFFILIATION
PERIOD OF STAY
Luis Eduardo Aceves González
Florent Baudier
Lars Becker
David Beltran
Sergey Bobkov
Pandelis Dodos
Devraj Duggal
Polona Durcik
Michael Dymond
Francisco Escudero Gutiérrez
Alexandros Eskenazis
Marco Fraccaroli
Li Gao
Tuomas Hytönen
Guy Kindler
Vjekoslav Kovač
Cosmas Kravaris
Patrick Kreitzberg
Jose Ramon Madrid Padilla
James Melbourne
Manor Mendel
Diogo Oliveira e Silva
Stefanie Petermichl
Emma Pollard
Joris Roos
Justin Salez
Miquel Saucedo
Gideon Schechtman
Rocco Servedio
Lenka Slavíkóva
Joseph Slote
Lauritz Streck
Maud Szusterman
Sergey Tikhonov
Gennady Uraltsev
Alexander Volberg
Blazej Wróbel
Xinyuan Xie
Quanhua Xu
Haonan Zhang
Texas A&M University
Texas A&M University
Universität Bonn
Universitat de Valencia
University of Minnesota
University of Athens
University of Minnesota-Twin Cities
Chapman University
University of Birmingham
Centrum Wiskunde & Informatica (CWI) and QuSoft
CNRS, Sorbonne Université
BCAM - Basque Center for Applied Mathematics
Wuhan University
Aalto University
The Hebrew University of Jerusalem
University of Zagreb
Princeton University
University of Montana
Virginia Polytechnic Institute and State University
Centro de Investigación en Matemáticas, A.C.
Open University of Israel
Instituto Superior Técnico
Universität Würzburg
Boise State University
University of Massachusetts Lowell
Université Paris-Dauphine
Universitat Autònoma de Barcelona
Weizmann Institute of Science
Columbia University
Charles University
California Institute of Technology
University of Cambridge
Tel Aviv University
ICREA and CRM
University of Arkansas
Michigan State University
Institute of Mathematics, Polish Academy of Sciences
University of California, Irvine
Université de Franche-Comté
University of South Carolina 
 
 
 
 
 
 
PERSON
AFFILIATION
PERIOD OF STAY
Radoslaw Adamczak
Gautam Aishwarya
Srinivasan Arunachalam
Lars Becker
Pierre Bizeul
Sergey Bobkov
Alexander Borichev (tbc)
Xiaonan Chen
Valentina Ciccone
Mateus Costa de Sousa
Devraj Duggal
Polona Durcik
Francisco Escudero Gutiérrez
Alexandros Eskenazis
Felipe Ferreira Gonçalves
Friedrich Götze
Hamed Hatami
Pooya Hatami
Ohad Klein
Dmitrii Krachun
James Melbourne
Shivam Nadimpalli
Diogo Oliveira e Silva
Emma Pollard
Cyril Roberto
Joris Roos
Miquel Saucedo
Ohad Sheinfeld
Joseph Slote
Lauritz Streck
Maud Szusterman
Gennady Uraltsev
Alexander Volberg
Bruno Volzone
Kewen Wu
Xudong Wu
Xinyuan Xie
University of Warsaw
Technion - Israel Institute of Technology
IBM Quantum, Almaden Research Center
Universität Bonn
Technion
University of Minnesota
Aix Marseille University
University of California, Irvine
Universität Bonn
BCAM
University of Minnesota-Twin Cities
Chapman University
Centrum Wiskunde & Informatica (CWI) and QuSoft
CNRS, Sorbonne Université
IMPA - Instituto de Matematica Pura e Aplicada
Universität Bielefeld
McGill University
The Ohio State University
Hebrew University
Princeton University
Centro de Investigación en Matemáticas, A.C.
Columbia University
Instituto Superior Técnico
Boise State University
Univesrité Paris Nanterre
University of Massachusetts Lowell
Universitat Autònoma de Barcelona
Bar-Ilan University
California Institute of Technology
University of Cambridge
Tel Aviv University
University of Arkansas
Michigan State University
Politecnico di Milano
University of California, Berkeley
Nanjing University
University of California, Irvine
 
 
 
 
PERSON
AFFILIATION
PERIOD OF STAY
Gautam Aishwarya
Lars Becker
Pierre Bizeul
Sergey Bobkov
Xiaonan Chen
Valentina Ciccone
Dario Cordero-Erausquin
Mateus Costa de Sousa
Thomas Courtade
Devraj Duggal
Polona Durcik
Alexandros Eskenazis
Felipe Ferreira Gonçalves
Dmitry Grigoryev
Steven Heilman
Benjamin Jaye
Egor Kosov
Michel Ledoux
Galyna Livshyts
Chandrasekhar Madhavan Nair
James Melbourne
Piotr Nayar
Diogo Oliveira e Silva
Jinyoung Park
Emma Pollard
Joris Roos
Igal Sason
Miquel Saucedo
Lisa Sauermann
Ohad Sheinfeld
Joseph Slote
Rajula Srivastava
Noah Stephens-Davidowitz
Lauritz Streck
Maud Szusterman
Sergey Tikhonov
Tomasz Tkocz
Gennady Uraltsev
Akanksha Vishwakarma Roos
Alexander Volberg
Bruno Volzone
Xudong Wu
Xinyuan Xie
Technion - Israel Institute of Technology
Universität Bonn
Technion
University of Minnesota
University of California, Irvine
Universität Bonn
Sorbonne Université
BCAM
University of California, Berkeley
University of Minnesota-Twin Cities
Chapman University
CNRS, Sorbonne Université
IMPA - Instituto de Matematica Pura e Aplicada
CNRS, Mathematiques, Université de Lille
University of Southern California
Georgia Tech
Centre de Recerca Matemàtica
University of Toulouse, France
Georgia Institute of Technology
The Chinese University of Hong Kong
Centro de Investigación en Matemáticas, A.C.
University of Warsaw
Instituto Superior Técnico
Courant Institute, New York University
Boise State University
University of Massachusetts Lowell
Technion - Israel Institute of Technology
Universitat Autònoma de Barcelona
Universität Bonn
Bar-Ilan University
California Institute of Technology
Universität Bonn
Cornell University
University of Cambridge
Tel Aviv University
ICREA and CRM
Carnegie Mellon University
University of Arkansas
self-affiliated
Michigan State University
Politecnico di Milano
Nanjing University
University of California, Irvine 
 
 
 
 

  Trimester Seminar Series

Thursday, December 12,  from 2:45 to 4:00 pm

Title: Uncertainty Principles Associated to Sets Satisfying the Geometric Control Condition

Abstract: In this talk we shall introduce and prove some forms of the uncertainty principle suggested by problems in control theory.  Joint work with Walton Green and Mishko Mitkovski.

Tuesday, December 10, 2024 - from 2:45 to 4:00 pm (cancelled)

Title: Polynomial approximation in L^2 of a log-concave weight.

Abstract: Given a measure with exponential moments, it is well known that polynomials are dense in L^2. A natural question is to quantify the rate of approximation for some classes of function, say Lipschitz. Such results are known as Jackson's theorem. We discuss the about log-concave case, especially in dimension one. Joint work with Bo'az Klartag.

Thursday, December 5, 2024 - from 2:45 to 4:00 pm

Title: Jackson's inequality on the hypercube

Abstract: This talk explores how well real-valued functions on the hypercube can be uniformly approximated by degree-d polynomials. I will present techniques for obtaining upper and lower bounds. As a first application, we show that the reverse Bernstein inequality fails in the tail space L^{1}_{≥0.499n}, improving previous counterexamples in L^{1}_{≥Clog log(n)}. As a second application, we show that no sensitivity theorem holds for bounded-valued functions, even when degree is relaxed to approximate degree. This is a joint work with Paata Ivanisvili and Roman Vershynin.

Tuesday, December 3, 2024  - from 2:45 to 4:00 pm

Title: Discrete Brunn-Minkowski inequality for subsets of the cube

Abstract: The classical Brunn-Minkowski inequality implies that for any two subsets A and B of Euclidean space, the volume of the Minkowski sum A + B is bounded from below by (|A||B|)^{1/2}. This inequality continues to hold in the discrete setting, on the integer lattice with counting measure. The topic of this talk is an optimal sharpening of this inequality when the sets A, B are contained in the cube {0, 1, 2}^d. I will discuss some applications and a useful method for proving inequalities in one variable. This is based on joint work with Paata Ivanisvili, Dmitry Krachun and José Madrid. 

Thursday, November 28, 2024 - from 2:45 to 4:00 pm (cancelled)

Title: Banach-space valued multilinear singular integrals and time-frequency analysis

Abstract: Since the 1960s, Calderón-Zygmund theory has provided a framework for studying singular integral operators that resemble the Hilbert transform, a ubiquitous operator in complex analysis, PDEs, and many other areas of mathematics. In the 1980s, Bourgain and Burkholder characterized the Banach spaces where linear Calderón-Zygmund theory is available through the UMD property—a purely probabilistic condition.

More recently, there has been significant interest in multilinear singular integral operators, which arise e.g. in fractional Leibniz rules and multilinear ergodic theory. However, a complete Banach-space valued theory remains elusive, especially for operators that exhibit stronger singularities than Calderón-Zygmund operators, such as the bilinear Hilbert transform—a prototypical operator of time-frequency type.

We will review the techniques involved in these problems, with emphasis on time-frequency analysis methods, presenting both our current understanding and open directions for extending the theory to the multilinear setting.

Tueday, November 26, 2024 - from 2:45 to 4:00 pm

Title: Sampling discretization problem

Abstract: Informally speaking, sampling discretization studies how well one can replace the computation of integral Lp norms for a given class of functions, by the evaluation of these functions at a fixed small set of points. On the one hand, such problems are classical. The first results of this type were obtained in 1937 by Marcinkiewicz for Lp-norms, with 1<p< infty, and by Marcinkiewicz-Zygmund for L1-norm for the class of univariate trigonometric polynomials of a fixed degree. On the other hand, the systematic study of sampling discretization has begun only recently.

Let C(Ω), be the space of all continuous functions on some compact subset Ω of R^n, equipped with a Borel probability measure μ. Let X_N be some N-dimensional subspace of C(Ω), let p≥1 , and let 0<ε<1. We aim to determine the smallest integer m for which there exists points x_1, … , x_m in Ω, such that for any f in X_N:

(1-ε) ||f||_p^p ≤ \frac{1}{m} \sum_{1 ≤ j ≤m} |f(x_j)|^p ≤ (1+ε) ||f||_p^p

where ||.||_p denotes the norm on L^p(Ω, μ). Clearly,  the number of points m cannot be less than the dimension N of the subspace X_N. We are interested in conditions on the subspace which can guarantee that m can be chosen close to N.

In the talk we shall discuss recent progress and some techniques in this area.

Thursday, November 14, 2024 - from 2:45 to 4:00 pm

Title: Sharp Strichartz Estimates via Hermite Polynomials and Hypercontractivity

Abstract: We will present an approach to prove sharp inequalities for free-range Schrödinger propagator using a pseudo-conformal transformation (the Lens transform) that reformulates the whole problem as a sort of average hypercontractivity statement in Gauss space We will indicate how to solve this in the even exponent case. We will also explain an old idea from my phd thesis on how to solve the general case via 3-symbol Hamming cube approximations.

Tuesday, November 12, 2024 - from 2:45 to 4:00 pm

Title: Stability in the Banach isometric conjecture for planar sections

Abstract: Banach asked whether a normed space all whose k-dimensional linear subspaces are isometric to each other, for some fixed 2 \leq k < \dim (V), must necessarily be Euclidean. At present, an affirmative answer is known for k=2 (Auerbach-Mazur-Ulam, 1935), all even k (Gromov, 1967), all k=1 \mod 4 but k=133 (Bor-Hernandez Lamoneda-Jimenez Desantiago-Montejano Peimbert, 2021), and k=3 (Ivanov-Mamaev-Nordskova, 2023). These developments, except perhaps the recent resolution of the k=3 case, can be considered spiritual successors to the original argument of Auerbach-Mazur-Ulam for k=2 which is based on a topological obstruction. In this talk, I will present a stable version of their result: if all 2-dimensional linear subspaces are approximately isometric to each other, then the normed space is approximately Euclidean. This talk is based on joint work with Dmitry Faifman.

Thursday, October 31, 2024 - from 2:45 to 4:00 pm

Title: Counting Lattice Points in Ellipsoids and the Central Limit Theorem for Quadratic Forms

Abstract: In this talk we review classical results on lattice point counting problems for ellipsoids and describe in dimensions five and larger some older and recent results on explicit error bounds. We outline their relation to corresponding errors estimates in the multivariate central limit theorem in Probability and the importance of gap principles for bounding Fourier integrals.

Tuesday, October 29, 2024 - from 2:45 to 4:00 pm

Title: Testing monotonicity from quantum data

Abstract: This talk is about testing properties of Boolean functions from data, where it turns out quantum algorithms can have dramatic speedups. We will focus on monotonicity testing. Here, a classical algorithm given access only to uniformly random samples (x,f(x)) requires at least 2^Ω(sqrt(n)) samples to test if f is monotone. On the other hand, we will describe a quantum algorithm for monotonicity testing that requires only poly(n) quantum data, in the form of so-called function states: sum_x |x,f(x) ⟩. We will also prove an n^3/2 lower bound for such quantum algorithms via a careful analysis of certain matrix ensembles. This is one of the first works to consider such lower bound arguments, and we welcome discussion and improvements to our techniques.  - Based on joint work with Matthias Caro and Preksha Naik.

Thursday, October 24, 2024 - from 2:15 to 3:30 pm

Title: The zero distribution for Taylor series with random and pseudo-random coefficients

Abstract: We study the local distribution of zeros of Taylor series for different classes of coefficients: random ones (independent, stationary, arithmetic random) and pseudo-random ones (exponential-polynomial, Rudin-Shapiro, Thue-Morse).

Tuesday, October 22, 2024 - from 2:45 to 4:00 pm

Title: Query lower bounds for log-concave sampling

Abstract: A central step in the implementation of probabilistic algorithms is that of sampling from known, complicated probability distributions: Given the density of a random variable (for example, as a black-box function that one can query) generate samples from a random variable that has a distribution "similar enough" to the given one. Significant effort has been devoted to designing more and more efficient algorithms, ranging from relatively simple algorithms, such as rejection sampling, to increasingly sophisticated such as Langevin or diffusion based models. In this talk we will focus on the converse question: Finding universal complexity lower bounds that no algorithm can beat.  We will do so in the case when the log-density is a strictly concave smooth function. In this case we will be able to construct tight bounds in low dimension using a modification of Perron's sprouting construction for Kakeya sets. Based on joint work with Sinho Chewi, Jerry Li, Chen Lu and Shyam Narayanan.

Thursday, October 17, 2024 - from 2:45 to 4:00 pm

Title: Global maximizers for spherical restriction

Abstract: We prove that constant functions are the unique real-valued maximizers for all L^2-L^{2n} adjoint Fourier restriction inequalities on the unit sphere S^{d-1}\subset R^d, d \in {3,4,5,6,7}, where n\geq 3 is an integer. The proof uses tools from probability theory, Lie theory, functional analysis, and the theory of special functions. It also relies on general solutions of the underlying Euler--Lagrange equation being smooth, a fact of independent interest which we discuss. We further show that complex-valued maximizers coincide with nonnegative maximizers multiplied by the character e^{i\xi\cdot\omega}, for some \xi, thereby extending previous work of Christ & Shao (2012) to arbitrary dimensions d\geq 2 and general even exponents.

Tuesday, October 15, 2024 - from 2:45 to 4:00 pm

Title: The L^p theory for outer measure spaces

Abstract: The theory of L^p spaces for outer measures, or outer L^p spaces, was introduced by Do and Thiele, as tool in the proof of estimate for multilinear forms arising in the context of harmonic analysis (Calderón-Zygmund theory, time-frequency analysis). To this end, they developed the theory in the direction of the interpolation properties of the spaces, such as Hölder’s inequality and Marcinkiewicz interpolation. However, the outer L^p spaces can be defined in a broader generality of settings, for example extending the classical notion of mixed L^p spaces on the Cartesian product of measure spaces. In this talk we expose further developments in the theory of the outer L^p spaces, focusing on their Banach space properties, such as Fubini’s theorem, Köthe duality, and Minkowski’s inequality.

Thursday, October 3, 2024 - from 2:45 to 4:00 pm

Title: Bounded functions with small tails are Juntas 

Abstract: There seems to be some recent interest in structural results concerning functions whose Fourier transform is mostly supported on `low-degrees'  while their range is restricted to a specific set. This is at least partly motivated by applications to Theoretical Computer Science. In this talk I will go over a not-so-recent result with this theme, which shows that a function f over the discrete hypercube whose Fourier representation is `mostly' of low degree and which obtains values in the (continuous) segment [-1,1] must be close to a junta, namely it can be approximated by only looking at a constant number of input-coordinates. The proof goes by showing a large-deviation lower bound for low degree functions that uses some tricks that may be of interest. If time permits I may also talk about some improvements to our result made by O’Donnell and Zhao. Joint work with Irit Dinur, Ehud Friedgut, and Ryan O'Donnell.

Tuesday, October 1, 2024 - from 2:45 to 4:00 pm

Title: Weighted inequalities for the Fourier transform

Abstract: In this talk we discuss inequalities for the Fourier transform between weighted Lebesgue spaces and their connection with an interpolation technique due to Calderón.

Thursday, September 26, 2024 - from 2:45 to 4:00 pm

Title: On the spectral norm of Rademacher matrices

Abstract: We will discuss two-sided non-asymptotic bounds for the mean spectral norm of nonhomogenous weighted Rademacher matrices. We will present a lower bound and show that it may be reversed up to log log log n factor for arbitrary n×n Rademacher matrices. Moreover, the triple logarithm may be eliminated for matrices with 0,1-coefficients.

Tuesday, September 24, 2024 - from 2:45 to 4 pm

Title: On Spherical Covariance Representations

Abstract: We first motivate the study of covariance representations by surveying preceding results in the Gaussian space. Their spherical counterparts are then derived thereby allowing applications to the spherical concentration phenomenon. The applications include second order concentration inequalities. The talk is based on joint work with Sergey Bobkov.

Thursday, September 12, 2024 - from 2:45 to 4:00 pm

Title: On the asymptotics of the optimal constants in the Khinchine-Kahane inequality

Abstract: Let us consider a sequence of indepenedent symmetric +/-1 random variables, often called the Rademacher system. A linear combination of these random variables is a real random variable called a (weighted) Rademacher sum. There are also vector-valued Rademacher sums, in which the real coefficients in the linear combination are replaced by vectors from some normed linear space. Rademacher sums, both real and vector-valued, have been studied for more than 100 years now. In the talk, classical moment inequalities for Rademacher sums will be described, going back to Khinchine (1923) and Kahane (1964), as well as some more recent results.

Video


Publications

No.
Author(s)
Title
Preprint
Publication
2024c01 Escudero-Gutiérrez, F. Learning junta distributions and quantum junta states, and QAC0 circuits 2410.15822
 
 
2024c02 Arunachalam, S.; Dutt, A.; Escudero-Gutiérrez, F. Testing and learning structured quantum Hamiltonians 2411.00082
 

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

September 16 - 20, 2024

Venue: HIM lecture hall (Poppelsdorfer Allee 45, Bonn)

Organizers:  Sergey Bobkov, Polona Durcik, Alexandros Eskenazis, Irina Holmes Fay, Paata Ivanisvili, Dor Minzer, and Alexander Volberg

Lecturers:

  • Alexandros Eskenazis
  • Yuval Filmus
  • Alex Iosevich
  • Noam Lifshitz
  • Alexander Volberg

Description: The interaction between learning theory and harmonic analysis was emphasized by mathematics of quantum computing. One of the outstanding open problems in this area concerns the sharp estimates in Bohnenblust-Hille inequality that generalizes a celebrated Littlewood’s lemma.

How to learn (with small error and with large probability) a complicated function or a very large matrix in a relatively small number of random (quantum) queries?  Of course, there should be some Fourier type restrictions on a function (a matrix) to have a reasonable answer to this.

The “classical” way of learning (Boolean) functions comes from very sophisticated extensions of  theorems of Kahn—Kalai—Linial type. In those results the interplay between maximal influence and heavy Fourier tails is the main technique. Maximal influence should be large if the `tail’ is small. However, recently another approach that is hinged on Bohnenblust—Hille inequality appeared. The school will cover the classical maximal influence approach to `probably approximately correct' (PAC) learning as well as the recent achievements using Bohnenblust—Hille inequality and its quantum counterpart.

Trimester Program guests, who were invited and have confirmed to be at HIM during the period of this school, are eligible to attend this event.


Workshop: Analysis and Geometry on Discrete Spaces

October 7 - 11, 2024

Venue: HIM lecture hall (Poppelsdorfer Allee 45, Bonn)

Organizers: Sergey Bobkov, Polona Durcik, Alexandros Eskenazis, Irina Holmes Fay, Paata Ivanisvili, Dor Minzer, and Alexander Volberg

Lecturers:

  • Florent Baudier
  • David Beltran
  • Pandelis Dodos
  • Polona Durcik
  • Michael Dymond
  • Yuval Filmus
  • Li Gao
  • Tuomas Hytönen
  • Guy Kindler
  • Vjekoslav Kovač
  • Jose Ramon Madrid Padilla
  • Stefanie Petermichl
  • Joris Roos
  • Justin Salez
  • Rocco Servedio
  • Lenka Slavíková
  • Błażej Wróbel 
  • Quanhua Xu
  • Haonan Zhang

Analytic questions of a discrete nature are ubiquitous in many areas of mathematics and theoretical computer science. The purpose of this conference is to bring together a diverse group of experts working, broadly, on Discrete Analysis with particular emphasis on questions having a geometric component. The topics will include Boolean analysis, vector-valued harmonic analysis, metric embeddings, geometry of graphs and groups, and aspects of discrete probability and theoretical computer science.

 Trimester Program guests, who were invited and have confirmed to be at HIM during the period of this workshop, are eligible to attend this event.


Workshop: Analysis in TCS: testing, learning, and complexity

November 4 - 8, 2024

Venue: HIM lecture hall (Poppelsdorfer Allee 45, Bonn)

Organizers: Sergey Bobkov, Polona Durcik, Alexandros Eskenazis, Irina Holmes Fay, Paata Ivanisvili, Dor Minzer, Joseph Slote, and Alexander Volberg

Lecturers:

  • Srinivasan Arunachalam
  • Francisco Escudero Gutierrez
  • Tom Gur (online)
  • Hamed Hatami
  • Pooya Hatami
  • Ohad Klein
  • Dmitry Krachun
  • Avichai Marmor (online)
  • Dan Mikulincer (online)
  • Shivam Nadimpalli
  • Joris Roos
  • Ohad Sheinfeld
  • Kewen Wu


Harmonic analysis on the hypercube has long found exciting applications in theoretical computer science, in areas as diverse as learning theory, voting theory, and computational complexity theory. And TCS has also inspired challenging new questions in analysis, often leading to new perspectives on familiar topics. Indeed, this connection is only deepening as quantum computing, machine learning, and other areas of TCS expand to spaces beyond the hypercube. Talks in this workshop will focus on such connections recently uncovered, techniques in use today, and conjectures old and new. We hope it can also be an invitation to the topic for a harmonic analysis audience, thanks to additional introductory talks scheduled.

Trimester Program guests, who were invited and have confirmed to be at HIM during the period of this workshop, are eligible to attend this event.


Workshop: Information theory, Boolean functions, and lattice problems

November 18 - 22, 2024

Venue: HIM lecture hall (Poppelsdorfer Allee 45, Bonn)

Organizers: Sergey Bobkov, Polona Durcik, Alexandros Eskenazis, Steven Heilman, Irina Holmes Fay, Paata Ivanisvili, Dor Minzer, and Alexander Volberg

Lecturers:

  • Gautam Aishwarya
  • Dario Cordero-Erasquin
  • Thomas Courtade
  • Felipe Gonçalves
  • James Melbourne
  • Chandra Nair
  • Piotr Nayar
  • Emma Pollard
  • Igal Sason
  • Lisa Sauermann
  • Joseph Slote
  • Noah Stephens-Davidowitz
  • Sergey Tikhonov
  • Tomasz Tkocz
  • Bruno Volzone

This workshop brings together leading experts in Boolean analysis, information theory, and lattices to explore the forefront of these disciplines  through the talks and discussions about  intriguing open problems, recent resolutions, and the evolution of innovative ideas, approaches, and techniques.

 Trimester Program guests, who were invited and have confirmed to be at HIM during the period of this workshop, are eligible to attend this event.


Wird geladen