Derandomization beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space
From MaRDI portal
Publication:5096446
DOI10.1137/20M134109XzbMath1494.68097arXiv1708.04634MaRDI QIDQ5096446
Aaron Sidford, Omer Reingold, Jack Murtagh, Salil P. 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
Analysis of algorithms and problem complexity (68Q25) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Random walks on graphs (05C81) Expander graphs (05C48)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Pseudorandom generators for space-bounded computation
- \(\text{BP}_{\text{H}}\text{SPACE}(S) \subseteq \text{DSPACE}(S^{3/2})\)
- \(\text{RL}\subseteq \text{SC}\)
- Entropy waves, the zig-zag graph product, and new constant-degree expanders
- In search of an easy witness: Exponential time vs. probabilistic polynomial time.
- Uniform constant-depth threshold circuits for division and iterated multiplication.
- Relationships between nondeterministic and deterministic tape complexities
- A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning
- Pseudorandomness for Regular Branching Programs via Fourier Analysis
- Pseudorandom walks on regular digraphs and the RL vs. L problem
- Spectral Sparsification of Graphs
- Small-Bias Probability Spaces: Efficient Constructions and Applications
- Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
- S-T connectivity on digraphs with a known stationary distribution
- Pseudorandom Generators for Regular Branching Programs
- Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
- Undirected connectivity in log-space
- An $O(\logn \log\logn)$ Space Algorithm for Undirected st-Connectivity
- Log Depth Circuits for Division and Related Problems
- Simple Constructions of Almost k-wise Independent Random Variables
- Addendum to “simple constructions of almost k-wise independent random variables”
- New problems complete for nondeterministic log space
- Almost-linear-time algorithms for Markov chains and new spectral primitives for directed graphs
- Breaking the multicommodity flow barrier for o(√log n)-approximations to sparsest cut
- Faster Generation of Random Spanning Trees
- Pseudorandom generators for width-3 branching programs
- Improved pseudorandomness for unordered branching programs through local monotonicity
- An efficient parallel solver for SDD linear systems
- An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations
- Approaching Optimality for Solving SDD Linear Systems
- Pseudorandom generators for group products
- Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- A Nearly-m log n Time Solver for SDD Linear Systems
- Inverting well conditioned matrices in quantum logspace
- A simple, combinatorial algorithm for solving SDD systems in nearly-linear time
- Derandomizing polynomial identity tests means proving circuit lower bounds
- A compendium of problems complete for symmetric logarithmic space
- Graph Sparsification by Effective Resistances
This page was built for publication: Derandomization beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space
