Derandomization beyond connectivity: undirected Laplacian systems in nearly logarithmic space

DOI10.1137/20M134109XMaRDI QIDQ5096446zbMATH OpenFDO

Authors Jack Murtagh, Omer Reingold, Aaron Sidford, Salil Vadhan

Publication date 17 August 2022

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1708.04634

zbMATH Keywords

spectral sparsificationrandom walksderandomizationexpander graphsspace complexityLaplacian systems

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Random walks on graphs (05C81) Expander graphs (05C48)

Abstract: We give a deterministic $ildeO(logn)$-space algorithm for approximately solving linear systems given by Laplacians of undirected graphs, and consequently also approximating hitting times, commute times, and escape probabilities for undirected graphs. Previously, such systems were known to be solvable by randomized algorithms using $O(logn)$ space (Doron, Le Gall, and Ta-Shma, 2017) and hence by deterministic algorithms using $O(lo{g}^{3/2}n)$ space (Saks and Zhou, FOCS 1995 and JCSS 1999). Our algorithm combines ideas from time-efficient Laplacian solvers (Spielman and Teng, STOC `04; Peng and Spielman, STOC `14) with ideas used to show that Undirected S-T Connectivity is in deterministic logspace (Reingold, STOC `05 and JACM `08; Rozenman and Vadhan, RANDOM `05).

Recommendations

• Probabilistic logarithmic-space algorithms for Laplacian solvers
• Undirected connectivity in log-space
• scientific article; zbMATH DE number 1256637
• scientific article; zbMATH DE number 1559538
• An O (log( n ) ^4/3 ) space algorithm for ( s, t ) connectivity in undirected graphs

Cites work

• scientific article; zbMATH DE number 3692649 (Why is no real title available?)
• scientific article; zbMATH DE number 1953444 (Why is no real title available?)
• scientific article; zbMATH DE number 1559537 (Why is no real title available?)
• A Nearly-m log n Time Solver for SDD Linear Systems
• A compendium of problems complete for symmetric logarithmic space
• A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning
• A simple, combinatorial algorithm for solving SDD systems in nearly-linear time
• Addendum to “simple constructions of almost k-wise independent random variables”
• Almost-linear-time algorithms for Markov chains and new spectral primitives for directed graphs
• An $O(\logn \log\logn)$ Space Algorithm for Undirected st-Connectivity
• An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations
• An efficient parallel solver for SDD linear systems
• Approaching optimality for solving SDD linear systems
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Breaking the multicommodity flow barrier for o(√log n)-approximations to sparsest cut
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Deterministic approximation of random walks in small space
• Electrical flows, Laplacian systems, and faster approximation of maximum flow in undirected graphs
• Entropy waves, the zig-zag graph product, and new constant-degree expanders
• Faster Generation of Random Spanning Trees
• Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
• Graph sparsification by effective resistances
• Improved pseudorandomness for unordered branching programs through local monotonicity
• In search of an easy witness: Exponential time vs. probabilistic polynomial time.
• Inverting well conditioned matrices in quantum logspace
• Log Depth Circuits for Division and Related Problems
• Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
• New problems complete for nondeterministic log space
• Probabilistic logarithmic-space algorithms for Laplacian solvers
• Pseudorandom generators for group products
• Pseudorandom generators for regular branching programs
• Pseudorandom generators for space-bounded computation
• Pseudorandom generators for width-3 branching programs
• Pseudorandom walks on regular digraphs and the RL vs. L problem
• Pseudorandomness and Fourier-growth bounds for width-3 branching programs
• Pseudorandomness for regular branching programs via Fourier analysis
• Pseudorandomness for width-2 branching programs
• Relationships between nondeterministic and deterministic tape complexities
• Simple Constructions of Almost k-wise Independent Random Variables
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• Spectral sparsification of graphs
• Towards an SDP-based approach to spectral methods: a nearly-linear-time algorithm for graph partitioning and decomposition
• Undirected connectivity in log-space
• Uniform constant-depth threshold circuits for division and iterated multiplication.
• \(\text{BP}_{\text{H}}\text{SPACE}(S) \subseteq \text{DSPACE}(S^{3/2})\)
• \(\text{RL}\subseteq \text{SC}\)
• \(s\)-\(t\) connectivity on digraphs with a known stationary distribution

Cited in

(4)

• Near-optimal derandomization of medium-width branching programs
• Optimal explicit small-depth formulas for the coin problem
• Probabilistic logarithmic-space algorithms for Laplacian solvers
• Deterministic approximation of random walks in small space

This page was built for publication: Derandomization beyond connectivity: undirected Laplacian systems in nearly logarithmic space

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5096446)