Derandomization beyond connectivity: undirected Laplacian systems in nearly logarithmic space

DOI10.1137/20M134109XzbMATH Open1494.68097arXiv1708.04634MaRDI QIDQ5096446FDOQ5096446

Aaron Sidford, Salil Vadhan, Omer Reingold, Jack Murtagh

Publication date: 17 August 2022

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

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).

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

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

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)

Cites Work

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

Cited In (2)

• Near-optimal derandomization of medium-width branching programs
• Optimal explicit small-depth formulas for the coin problem

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)