scientific article; zbMATH DE number 7650109

DOI10.4230/LIPIcs.APPROX-RANDOM.2019.42MaRDI QIDQ5875498

Jack Murtagh, Aaron Sidford, Omer Reingold, Salil P. Vadhan

Publication date: 3 February 2023

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

random walksderandomizationspectral approximationexpander graphsspace complexity

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (2)

Explicit expanders of every degree and size ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Explicit constructions of linear-sized superconcentrators
• \(\text{BP}_{\text{H}}\text{SPACE}(S) \subseteq \text{DSPACE}(S^{3/2})\)
• Pseudorandomness for network algorithms
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• Pseudorandom Generators for Regular Branching Programs
• Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
• Undirected connectivity in log-space
• Simple Constructions of Almost k-wise Independent Random Variables
• A Framework for Analyzing Resparsification Algorithms
• Almost-linear-time algorithms for Markov chains and new spectral primitives for directed graphs
• Density Independent Algorithms for Sparsifying k-Step Random Walks
• An efficient parallel solver for SDD linear systems
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques

This page was built for publication: