Beginning with the work of Landau, Pollak and Slepian in the 1960s on time‐band limiting, commuting pairs of integral and differential operators have played a key role in signal processing, random matrix theory, and integrable systems. Previously, such pairs were constructed by ad hoc methods, which essentially worked because a commuting operator of low order could be found by a direct calculation. We describe a general approach to these problems that proves that every point
 Award ID(s):
 1901830
 NSFPAR ID:
 10154966
 Date Published:
 Journal Name:
 Journal für die reine und angewandte Mathematik (Crelles Journal)
 Volume:
 0
 Issue:
 0
 ISSN:
 00754102
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

Abstract W of Wilson's infinite dimensional adelic Grassmannian gives rise to an integral operator , acting on for a contour , which reflects a differential operator with rational coefficients in the sense that on a dense subset of . By using analytic methods and methods from integrable systems, we show that the reflected differential operator can be constructed from the Fourier algebra of the associated bispectral function . The exact size of this algebra with respect to a bifiltration is in turn determined using algebro‐geometric methods. Intrinsic properties of four involutions of the adelic Grassmannian naturally lead us to consider the reflecting property above in place of plain commutativity. Furthermore, we prove that the time‐band limited operators of the generalized Laplace transforms with kernels given by the rank one bispectral functions always reflect a differential operator. A 90° rotation argument is used to prove that the time‐band limited operators of the generalized Fourier transforms with kernels admit a commuting differential operator. These methods produce vast collections of integral operators with prolate‐spheroidal properties, associated to the wave functions of all rational solutions of the KP hierarchy vanishing at infinity, introduced by Krichever in the late 1970s. 
Commuting integral and differential operators connect the topics of signal processing, random matrix theory, and integrable systems. Previously, the construction of such pairs was based on direct calculation and concerned concrete special cases, leaving behind important families such as the operators associated to the rational solutions of the Korteweg–de Vries (KdV) equation. We prove a general theorem that the integral operator associated to every wave function in the infinitedimensional adelic Grassmannian G r a d of Wilson always reflects a differential operator (in the sense of Definition 1 below). This intrinsic property is shown to follow from the symmetries of Grassmannians of Kadomtsev–Petviashvili (KP) wave functions, where the direct commutativity property holds for operators associated to wave functions fixed by Wilson’s sign involution but is violated in general. Based on this result, we prove a second main theorem that the integral operators in the computation of the singular values of the truncated generalized Laplace transforms associated to all bispectral wave functions of rank 1 reflect a differential operator. A 9 0 ○ rotation argument is used to prove a third main theorem that the integral operators in the computation of the singular values of the truncated generalized Fourier transforms associated to all such KP wave functions commute with a differential operator. These methods produce vast collections of integral operators with prolatespheroidal properties, including as special cases the integral operators associated to all rational solutions of the KdV and KP hierarchies considered by [Airault, McKean, and Moser, Commun. Pure Appl. Math. 30, 95–148 (1977)] and [Krichever, Funkcional. Anal. i Priložen. 12, 76–78 (1978)], respectively, in the late 1970s. Many examples are presented.more » « less

Lysyanskaya, Anna ; Handschuh, Helena (Ed.)We study the blackbox function inversion problem, which is the problem of finding x[N] such that f(x)=y, given as input some challenge point y in the image of a function f:[N][N], using T oracle queries to f and preprocessed advice 01S depending on f. We prove a number of new results about this problem, as follows. 1. We show an algorithm that works for any T and S satisfying TS2maxST=(N3) . In the important setting when ST, this improves on the celebrated algorithm of Fiat and Naor [STOC, 1991], which requires TS3N3. E.g., Fiat and Naor's algorithm is only nontrivial for SN23 , while our algorithm gives a nontrivial tradeoff for any SN12 . (Our algorithm and analysis are quite simple. As a consequence of this, we also give a selfcontained and simple proof of Fiat and Naor's original result, with certain optimizations left out for simplicity.) 2. We show a nonadaptive algorithm (i.e., an algorithm whose ith query xi is chosen based entirely on and y, and not on the f(x1)f(xi−1)) that works for any T and S satisfying S=(Nlog(NT)) giving the first nontrivial nonadaptive algorithm for this problem. E.g., setting T=Npolylog(N) gives S=(NloglogN). This answers a question due to CorriganGibbs and Kogan [TCC, 2019], who asked whether it was possible for a nonadaptive algorithm to work with parameters T and S satisfying T+SlogNo(N) . We also observe that our nonadaptive algorithm is what we call a guessandcheck algorithm, that is, it is nonadaptive and its final output is always one of the oracle queries x1xT. For guessandcheck algorithms, we prove a matching lower bound, therefore completely characterizing the achievable parameters (ST) for this natural class of algorithms. (CorriganGibbs and Kogan showed that any such lower bound for arbitrary nonadaptive algorithms would imply new circuit lower bounds.) 3. We show equivalence between function inversion and a natural decision version of the problem in both the worst case and the average case, and similarly for functions f:[N][M] with different ranges. All of the above results are most naturally described in a model with shared randomness (i.e., random coins shared between the preprocessing algorithm and the online algorithm). However, as an additional contribution, we show (using a technique from communication complexity due to Newman [IPL, 1991]) how to generically convert any algorithm that uses shared randomness into one that does not.more » « less

Abstract The generalized Wilson loop operator interpolating between the supersymmetric and the ordinary Wilson loop in
SYM theory provides an interesting example of renormalization group flow on a line defect: the scalar coupling parameter $\mathcal{N}=4$ζ has a nontrivial beta function and may be viewed as a running coupling constant in a 1D defect QFT. In this paper we continue the study of this operator, generalizing previous results for the beta function and Wilson loop expectation value to the case of an arbitrary representation of the gauge group and beyond the planar limit. Focusing on the scalar ladder limit where the generalized Wilson loop reduces to a purely scalar line operator in a free adjoint theory, and specializing to the case of the rankk symmetric representation ofSU (N ), we also consider a certain ‘semiclassical’ limit wherek is taken to infinity with the productkζ ^{2}fixed. This limit can be conveniently studied using a 1D defect QFT representation in terms ofN commuting bosons. Using this representation, we compute the beta function and the circular loop expectation value in the largek limit, and use it to derive constraints on the structure of the beta function for general representation. We discuss the corresponding 1D RG flow and comment on the consistency of the results with the 1D defect version of the Ftheorem. 
Let f: {0, 1}n → {0, 1} be a boolean function, and let f∧(x, y) = f(x ∧ y) denote the ANDfunction of f, where x ∧ y denotes bitwise AND. We study the deterministic communication complexity of f∧ and show that, up to a logn factor, it is bounded by a polynomial in the logarithm of the real rank of the communication matrix of f∧. This comes within a logn factor of establishing the logrank conjecture for ANDfunctions with no assumptions on f. Our result stands in contrast with previous results on special cases of the logrank conjecture, which needed significant restrictions on f such as monotonicity or low F2degree. Our techniques can also be used to prove (within a logn factor) a lifting theorem for ANDfunctions, stating that the deterministic communication complexity of f∧ is polynomially related to the ANDdecision tree complexity of f. The results rely on a new structural result regarding boolean functions f: {0, 1}n → {0, 1} with a sparse polynomial representation, which may be of independent interest. We show that if the polynomial computing f has few monomials then the set system of the monomials has a small hitting set, of size polylogarithmic in its sparsity. We also establish extensions of this result to multilinear polynomials f: {0, 1}n → with a larger range.more » « less