More Like this

1. Efficient Approximate Unitary Designs from Random Pauli Rotations

   https://doi.org/10.1109/FOCS61266.2024.00036  

   Haah, Jeongwan; Liu, Yunchao; Tan, Xinyu (October 2024, IEEE)

   We construct random walks on simple Lie groups that quickly converge to the Haar measure for all moments up to order t. The spectral gap of this random walk is shown to be Ω(1/t), which coincides with the best previously known bound for a random walk on the permutation group on {0, 1}^n. This implies that the walk gives an ε-approximate unitary t-design. Our simple proof uses quadratic Casimir operators of Lie algebras. 

   more » « less
2. K-Theory and the Universal Coefficient Theorem for Simple Separable Exact C*-Algebras Not Isomorphic to Their Opposites

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

   Phillips, N Christopher; Viola, Maria Grazia (March 2023, International Mathematics Research Notices)

   Abstract We construct uncountably many mutually nonisomorphic simple separable stably finite unital exact C*-algebras that are not isomorphic to their opposite algebras. In particular, we prove that there are uncountably many possibilities for the $$K_0$$-group, the $$K_1$$-group, and the tracial state space of such an algebra. We show that these C*-algebras satisfy the Universal Coefficient Theorem, which is new even for the already known example of an exact C*-algebra nonisomorphic to its opposite algebra produced in an earlier work. 

   more » « less
3. Least squares as random walks

   https://doi.org/10.1016/j.physleta.2025.130449  

   Kostinski, Alexander; Ierley, Glenn; Kostinski, Sarah (June 2025, Physics Letters A)

   Linear least squares (LLS) is perhaps the most common method of data analysis, dating back to Legendre, Gauss and Laplace. Framed as linear regression, LLS is also a backbone of mathematical statistics. Here we report on an unexpected new connection between LLS and random walks. To that end, we introduce the notion of a random walk based on a discrete sequence of data samples (data walk). We show that the slope of a straight line which annuls the net area under a residual data walk equals the one found by LLS. For equidistant data samples this result is exact and holds for an arbitrary distribution of steps. 

   more » « less
4. Local Access to Random Walks , January 2022

   Biswas, A.S.; Pyne, E.; Rubinfeld, R. (January 2022, Innovations in Theoretical Computer Science (ITCS 2022))

   For a graph G on n vertices, naively sampling the position of a random walk of at time t requires work Ω(t). We desire local access algorithms supporting positionG(t) queries, which return the position of a random walk from some fixed start vertex s at time t, where the joint distribution of returned positions is 1/ poly(n) close to those of a uniformly random walk in ℓ1 distance. We first give an algorithm for local access to random walks on a given undirected d-regular graph with eO( 1 1−λ √ n) runtime per query, where λ is the second-largest eigenvalue of the random walk matrix of the graph in absolute value. Since random d-regular graphs G(n, d) are expanders with high probability, this gives an eO(√ n) algorithm for a graph drawn from G(n, d) whp, which improves on the naive method for small numbers of queries. We then prove that no algorithm with subconstant error given probe access to an input d-regular graph can have runtime better than Ω(√ n/ log(n)) per query in expectation when the input graph is drawn from G(n, d), obtaining a nearly matching lower bound. We further show an Ω(n1/4) runtime per query lower bound even with an oblivious adversary (i.e. when the query sequence is fixed in advance). We then show that for families of graphs with additional group theoretic structure, dramatically better results can be achieved. We give local access to walks on small-degree abelian Cayley graphs, including cycles and hypercubes, with runtime polylog(n) per query. This also allows for efficient local access to walks on polylog degree expanders. We show that our techniques apply to graphs with high degree by extending or results to graphs constructed using the tensor product (giving fast local access to walks on degree nϵ graphs for any ϵ ∈ (0, 1]) and Cartesian product. 

   more » « less
5. Learning Attribute Distributions Through Random Walks

   https://doi.org/10.1007/978-3-031-21131-7_2  

   Antunes, N.; Bhamidi, S.; Pipiras, V. (January 2023, Complex Networks and Their Applications XI)

   Cherifi, H.; Mantegna, R.N.; Rocha, L.M.; Cherifi, C.; Micciche, S. (Ed.)

   We investigate the statistical learning of nodal attribute distributions in homophily networks using random walks. Attributes can be discrete or continuous. A generalization of various existing canonical models, based on preferential attachment is studied, where new nodes form connections dependent on both their attribute values and popularity as measured by degree. We consider several canonical attribute agnostic sampling schemes such as Metropolis-Hasting random walk, versions of node2vec (Grover and Leskovec 2016) that incorporate both classical random walk and non-backtracking propensities and propose new variants which use attribute information in addition to topological information to explore the network. The performance of such algorithms is studied on both synthetic networks and real world systems, and its dependence on the degree of homophily, or absence thereof, is assessed. 

   more » « less