Dual Trimester Program: "Boolean Analysis in Computer Science"

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.

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.

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.

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.

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).

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.

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.

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.

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.

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.

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.

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.