In this paper, we introduce a new, spectral notion of approximation between directed graphs, which we call singular value (SV) approximation. SVapproximation is stronger than previous notions of spectral approximation considered in the literature, including spectral approximation of Laplacians for undirected graphs [ST04], standard approximation for directed graphs [CKP + 17], and unitcircle (UC) approximation for directed graphs [AKM + 20]. Further, SV approximation enjoys several useful properties not possessed by previous notions of approximation, e.g., it is preserved under products of randomwalk matrices and bounded matrices. We provide a nearly lineartime algorithm for SVsparsifying (and hence UCsparsifying) Eulerian directed graphs, as well as ℓstep random walks on such graphs, for any ℓ≤poly(n). Combined with the Eulerian scaling algorithms of [CKK + 18], given an arbitrary (not necessarily Eulerian) directed graph and a set S of vertices, we can approximate the stationary probability mass of the (S,Sc) cut in an ℓstep random walk to within a multiplicative error of 1/polylog(n) and an additive error of 1/poly(n) in nearly linear time. As a starting point for these results, we provide a simple blackbox reduction from SVsparsifying Eulerian directed graphs to SVsparsifying undirected graphs; such a directedtoundirected reduction was not known for previous notions of spectral approximation.
more »
« less
High Dimensional Expanders: Eigenstripping, Pseudorandomness, and Unique Games
Higher order random walks (HDwalks) on high dimensional expanders (HDX) have seen an incredible amount of study and application since their introduction by Kaufman and Mass (ITCS 2016), yet their broader combinatorial and spectral properties remain poorly understood. We develop a combinatorial characterization of the spectral structure of HDwalks on twosided localspectral expanders (Dinur and Kaufman FOCS 2017), which offer a broad generalization of the wellstudied Johnson and Grassmann graphs. Our characterization, which shows that the spectra of HDwalks lie tightly concentrated in a few combinatorially structured strips, leads to novel structural theorems such as a tight ℓ2characterization of edgeexpansion, as well as to a new understanding of localtoglobal graph algorithms on HDX.
Towards the latter, we introduce a novel spectral complexity measure called Stripped Threshold Rank, and show how it can replace the (much larger) threshold rank as a parameter controlling the performance of algorithms on structured objects. Combined with a sumofsquares proof for the former ℓ2characterization, we give a concrete application of this framework to algorithms for unique games on HDwalks, where in many cases we improve the state of the art (Barak, Raghavendra, and Steurer FOCS 2011, and Arora, Barak, and Steurer JACM 2015) from nearlyexponential to polynomial time (e.g. for sparsifications of Johnson graphs or of slices of the qary hypercube). Our characterization of expansion also holds an interesting connection to hardness of approximation, where an ℓ∞variant for the Grassmann graphs was recently used to resolve the 22 Games Conjecture (Khot, Minzer, and Safra FOCS 2018). We give a reduction from a related ℓ∞variant to our ℓ2characterization, but it loses factors in the regime of interest for hardness where the gap between ℓ2 and ℓ∞ structure is large. Nevertheless, our results open the door for further work on the use of HDX in hardness of approximation and their general relation to unique games.
more »
« less
 Award ID(s):
 1953928
 NSFPAR ID:
 10320386
 Date Published:
 Journal Name:
 Proceedings of the 2022 Annual ACMSIAM Symposium on Discrete Algorithms (SODA)
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


The algorithms in this paper (when combined with our FOCS’16 paper) allow one to, in almost linear time, compute a whole bunch of things about random walks in directed graphs. For example, one can compute the stationary distribution, hitting the time between a pair of vertices, commute times between all vertices, escape probabilities, approximations of the mixing time, and more.more » « less

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 dregular graph with eO( 1 1−λ √ n) runtime per query, where λ is the secondlargest eigenvalue of the random walk matrix of the graph in absolute value. Since random dregular 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 dregular 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 smalldegree 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

In a recent work, Moshkovitz [FOCS '14] presented a transformation on twoplayer games called ``fortification'', and gave an elementary proof of an (exponential decay) parallel repetition theorem for fortified twoplayer projection games. In this paper, we give an \emph{analytic reformulation} of Moshkovitz's fortification framework, which was originally cast in combinatorial terms. This reformulation allows us to expand the scope of the fortification method to new settings. First, we show \emph{any} game (not just projection games) can be fortified, and give a simple proof of parallel repetition for general fortified games. Then, we prove parallel repetition and fortification theorems for games with players sharing quantum entanglement, as well as games with more than two players. This gives a new gap amplification method for general games in the quantum and multiplayer settings, two problems which have recently received much attention. An important component of our work is a variant of the fortification transformation, called ``ordered fortification", that preserves the entangled value of a game. The original fortification of Moshkovitz does not in general preserve the entangled value of a game, and this was a barrier to extending the fortification framework to the quantum setting.more » « less

Kernel matrices, as well as weighted graphs represented by them, are ubiquitous objects in machine learning, statistics and other related fields. The main drawback of using kernel methods (learning and inference using kernel matrices) is efficiency – given n input points, most kernelbased algorithms need to materialize the full n × n kernel matrix before performing any subsequent computation, thus incurring Ω(n^2) runtime. Breaking this quadratic barrier for various problems has therefore, been a subject of extensive research efforts. We break the quadratic barrier and obtain subquadratic time algorithms for several fundamental linearalgebraic and graph processing primitives, including approximating the top eigenvalue and eigenvector, spectral sparsification, solving lin ear systems, local clustering, lowrank approximation, arboricity estimation and counting weighted triangles. We build on the recently developed Kernel Density Estimation framework, which (after preprocessing in time subquadratic in n) can return estimates of row/column sums of the kernel matrix. In particular, we de velop efficient reductions from weighted vertex and weighted edge sampling on kernel graphs, simulating random walks on kernel graphs, and importance sampling on matrices to Kernel Density Estimation and show that we can generate samples from these distributions in sublinear (in the support of the distribution) time. Our reductions are the central ingredient in each of our applications and we believe they may be of independent interest. We empirically demonstrate the efficacy of our algorithms on lowrank approximation (LRA) and spectral sparsi fication, where we observe a 9x decrease in the number of kernel evaluations over baselines for LRA and a 41x reduction in the graph size for spectral sparsification.more » « less