skip to main content


Search for: All records

Award ID contains: 2007079

Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?

Some links on this page may take you to non-federal websites. Their policies may differ from this site.

  1. Abstract

    We investigate the validity of the “Einstein relations” in the general setting of unimodular random networks. These are equalities relating scaling exponents:$$\begin{aligned} d_{w} &= d_{f} + \tilde{\zeta }, \\ d_{s} &= 2 d_{f}/d_{w}, \end{aligned}$$wheredwis the walk dimension,dfis the fractal dimension,dsis the spectral dimension, and$\tilde{\zeta }$is the resistance exponent. Roughly speaking, this relates the mean displacement and return probability of a random walker to the density and conductivity of the underlying medium. We show that ifdfand$\tilde{\zeta } \geqslant 0$exist, thendwanddsexist, and the aforementioned equalities hold. Moreover, our primary new estimate$d_{w} \geqslant d_{f} + \tilde{\zeta }$is established for all$\tilde{\zeta } \in \mathbb{R}$.

    For the uniform infinite planar triangulation (UIPT), this yields the consequencedw=4 usingdf=4 (Angel in Geom. Funct. Anal. 13(5):935–974, 2003) and$\tilde{\zeta }=0$(established here as a consequence of the Liouville Quantum Gravity theory, following Gwynne-Miller 2020 and (Ding and Gwynne in Commun. Math. Phys. 374(3):1877–1934, 2020)). The conclusiondw=4 had been previously established by Gwynne and Hutchcroft (2018) using more elaborate methods. A new consequence is thatdw=dffor the uniform infinite Schnyder-wood decorated triangulation, implying that the simple random walk is subdiffusive, sincedf>2.

     
    more » « less
    Free, publicly-accessible full text available December 1, 2024
  2. We present an algorithmic framework for quantum-inspired classical algorithms on close-to-low-rank matrices, generalizing the series of results started by Tang’s breakthrough quantum-inspired algorithm for recommendation systems [STOC’19]. Motivated by quantum linear algebra algorithms and the quantum singular value transformation (SVT) framework of Gilyén et al. [STOC’19], we develop classical algorithms for SVT that run in time independent of input dimension, under suitable quantum-inspired sampling assumptions. Our results give compelling evidence that in the corresponding QRAM data structure input model, quantum SVT does not yield exponential quantum speedups. Since the quantum SVT framework generalizes essentially all known techniques for quantum linear algebra, our results, combined with sampling lemmas from previous work, suffice to generalize all prior results about dequantizing quantum machine learning algorithms. In particular, our classical SVT framework recovers and often improves the dequantization results on recommendation systems, principal component analysis, supervised clustering, support vector machines, low-rank regression, and semidefinite program solving. We also give additional dequantization results on low-rank Hamiltonian simulation and discriminant analysis. Our improvements come from identifying the key feature of the quantum-inspired input model that is at the core of all prior quantum-inspired results: ℓ2-norm sampling can approximate matrix products in time independent of their dimension. We reduce all our main results to this fact, making our exposition concise, self-contained, and intuitive.

     
    more » « less
  3. Braverman, Mark (Ed.)
    We present an O((log n)²)-competitive algorithm for metrical task systems (MTS) on any n-point metric space that is also 1-competitive for service costs. This matches the competitive ratio achieved by Bubeck, Cohen, Lee, and Lee (2019) and the refined competitive ratios obtained by Coester and Lee (2019). Those algorithms work by first randomly embedding the metric space into an ultrametric and then solving MTS there. In contrast, our algorithm is cast as regularized gradient descent where the regularizer is a multiscale metric entropy defined directly on the metric space. This answers an open question of Bubeck (Highlights of Algorithms, 2019). 
    more » « less