More Like this

1. Matricial Frameworks for the Mandelbrot and Filled Julia Sets

   Babcock, Eric; Brindle, Dawson; Hamidi, Mitch; Ismert, Lara (December 2023, Ball State Undergraduate Mathematics Exchange)

   Both the Mandelbrot set and filled Julia sets are subsets in the complex plane derived by studying iterations of complex polynomials. We develop a matricial framework to establish an alternate form of iteration by complex polynomials using a sequence of affine transformations. Using this framework, we are able to check membership in a filled Julia set and the Mandelbrot set by studying boundedness of sequences of matrices. Specifically, we show that a complex number belongs to the Mandelbrot set if and only if a particular sequence of matrices is bounded in the operator norm, and a complex number belongs to a filled Julia set if and only if a particular sequence of matrices is bounded in operator norm. 

   more » « less
2. Communication Complexity of Inner Product in Symmetric Normed Spaces

   Andoni, Alexandr; Blasiok, Jaroslaw; Filtser, Arnold (January 2023, Leibniz international proceedings in informatics)

   Tauman Kalai, Yael (Ed.)

   We introduce and study the communication complexity of computing the inner product of two vectors, where the input is restricted w.r.t. a norm N on the space ℝⁿ. Here, Alice and Bob hold two vectors v,u such that ‖v‖_N ≤ 1 and ‖u‖_{N^*} ≤ 1, where N^* is the dual norm. The goal is to compute their inner product ⟨v,u⟩ up to an ε additive term. The problem is denoted by IP_N, and generalizes important previously studied problems, such as: (1) Computing the expectation 𝔼_{x∼𝒟}[f(x)] when Alice holds 𝒟 and Bob holds f is equivalent to IP_{𝓁₁}. (2) Computing v^TAv where Alice has a symmetric matrix with bounded operator norm (denoted S_∞) and Bob has a vector v where ‖v‖₂ = 1. This problem is complete for quantum communication complexity and is equivalent to IP_{S_∞}. We systematically study IP_N, showing the following results, near tight in most cases: 1) For any symmetric norm N, given ‖v‖_N ≤ 1 and ‖u‖_{N^*} ≤ 1 there is a randomized protocol using 𝒪̃(ε^{-6} log n) bits of communication that returns a value in ⟨u,v⟩±ε with probability 2/3 - we will denote this by ℛ_{ε,1/3}(IP_N) ≤ 𝒪̃(ε^{-6} log n). In a special case where N = 𝓁_p and N^* = 𝓁_q for p^{-1} + q^{-1} = 1, we obtain an improved bound ℛ_{ε,1/3}(IP_{𝓁_p}) ≤ 𝒪(ε^{-2} log n), nearly matching the lower bound ℛ_{ε, 1/3}(IP_{𝓁_p}) ≥ Ω(min(n, ε^{-2})). 2) One way communication complexity ℛ^{→}_{ε,δ}(IP_{𝓁_p}) ≤ 𝒪(ε^{-max(2,p)}⋅ log n/ε), and a nearly matching lower bound ℛ^{→}_{ε, 1/3}(IP_{𝓁_p}) ≥ Ω(ε^{-max(2,p)}) for ε^{-max(2,p)} ≪ n. 3) One way communication complexity ℛ^{→}_{ε,δ}(N) for a symmetric norm N is governed by the distortion of the embedding 𝓁_∞^k into N. Specifically, while a small distortion embedding easily implies a lower bound Ω(k), we show that, conversely, non-existence of such an embedding implies protocol with communication k^𝒪(log log k) log² n. 4) For arbitrary origin symmetric convex polytope P, we show ℛ_{ε,1/3}(IP_{N}) ≤ 𝒪(ε^{-2} log xc(P)), where N is the unique norm for which P is a unit ball, and xc(P) is the extension complexity of P (i.e. the smallest number of inequalities describing some polytope P' s.t. P is projection of P'). 

   more » « less
3. On Weissler’s Conjecture on the Hamming Cube I

   https://doi.org/10.1093/imrn/rnaa363  

   Ivanisvili, P; Nazarov, F (December 2020, International Mathematics Research Notices)

   null (Ed.)

   Abstract Let $$1\leq p \leq q <\infty $$ and let $$w \in \mathbb{C}$$. Weissler conjectured that the Hermite operator $$e^{w\Delta }$$ is bounded as an operator from $$L^{p}$$ to $$L^{q}$$ on the Hamming cube $$\{-1,1\}^{n}$$ with the norm bound independent of $$n$$ if and only if $$\begin{align*} |p-2-e^{2w}(q-2)|\leq p-|e^{2w}|q. \end{align*}$$It was proved in [ 1], [ 2], and [ 17] in all cases except $$2<p\leq q <3$$ and $$3/2<p\leq q <2$$, which stood open until now. The goal of this paper is to give a full proof of Weissler’s conjecture in the case $p=q$. Several applications will be presented. 

   more » « less
4. Random quantum graphs

   https://doi.org/10.1090/tran/8584  

   Chirvasitu, Alexandru; Wasilewski, Mateusz (April 2022, Transactions of the American Mathematical Society)

   We prove a number of results to the effect that generic quantum graphs (defined via operator systems as in the work of Duan-Severini-Winter / Weaver) have few symmetries: for a Zariski-dense open set of tuples ( X 1 , ⋯ , X d ) (X_1,\cdots ,X_d) of traceless self-adjoint operators in the n × n n\times n matrix algebra the corresponding operator system has trivial automorphism group, in the largest possible range for the parameters: 2 ≤ d ≤ n 2 − 3 2\le d\le n^2-3 . Moreover, the automorphism group is generically abelian in the larger parameter range 1 ≤ d ≤ n 2 − 2 1\le d\le n^2-2 . This then implies that for those respective parameters the corresponding random-quantum-graph model built on the GUE ensembles of X i X_i ’s (mimicking the Erdős-Rényi G ( n , p ) G(n,p) model) has trivial/abelian automorphism group almost surely. 

   more » « less
5. Sparse High Dimensional Expanders via Local Lifts

   https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2024.68  

   Ben_Yaacov, Inbar; Dikstein, Yotam; Maor, Gal (January 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Kumar, Amit; Ron-Zewi, Noga (Ed.)

   High dimensional expanders (HDXs) are a hypergraph generalization of expander graphs. They are extensively studied in the math and TCS communities due to their many applications. Like expander graphs, HDXs are especially interesting for applications when they are bounded degree, namely, if the number of edges adjacent to every vertex is bounded. However, only a handful of constructions are known to have this property, all of which rely on algebraic techniques. In particular, no random or combinatorial construction of bounded degree high dimensional expanders is known. As a result, our understanding of these objects is limited. The degree of an i-face in an HDX is the number of (i+1)-faces that contain it. In this work we construct complexes whose higher dimensional faces have bounded degree. This is done by giving an elementary and deterministic algorithm that takes as input a regular k-dimensional HDX X and outputs another regular k-dimensional HDX X̂ with twice as many vertices. While the degree of vertices in X̂ grows, the degree of the (k-1)-faces in X̂ stays the same. As a result, we obtain a new "algebra-free" construction of HDXs whose (k-1)-face degree is bounded. Our construction algorithm is based on a simple and natural generalization of the expander graph construction by Bilu and Linial [Yehonatan Bilu and Nathan Linial, 2006], which build expander graphs using lifts coming from edge signings. Our construction is based on local lifts of high dimensional expanders, where a local lift is a new complex whose top-level links are lifts of the links of the original complex. We demonstrate that a local lift of an HDX is also an HDX in many cases. In addition, combining local lifts with existing bounded degree constructions creates new families of bounded degree HDXs with significantly different links than before. For every large enough D, we use this technique to construct families of bounded degree HDXs with links that have diameter ≥ D. 

   more » « less