scientific article; zbMATH DE number 7413499
From MaRDI portal
Publication:5158498
DOI10.4086/toc.2021.v017a004OpenAlexW2978378153MaRDI QIDQ5158498
Jack Murtagh, Omer Reingold, Aaron Sidford, Salil P. Vadhan
Publication date: 25 October 2021
Published in: Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1903.06361
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Randomized algorithms (68W20) Theory of computing (68Qxx)
Related Items (2)
Derandomization beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space ⋮ On Constructing Expanders for Any Number of Vertices
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
- Eigenvalues and expanders
- Explicit constructions of linear-sized superconcentrators
- Entropy waves, the zig-zag graph product, and new constant-degree expanders
- Uniform constant-depth threshold circuits for division and iterated multiplication.
- Pseudorandomness for network algorithms
- Spectral Sparsification of Graphs
- Small-Bias Probability Spaces: Efficient Constructions and Applications
- Pseudorandom Generators for Regular Branching Programs
- Explicit Concentrators from Generalized N-Gons
- An Elementary Construction of Constant-Degree Expanders
- Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
- Undirected connectivity in log-space
- Log Depth Circuits for Division and Related Problems
- Simple Constructions of Almost k-wise Independent Random Variables
- Almost-linear-time algorithms for Markov chains and new spectral primitives for directed graphs
- On Constructing Expanders for Any Number of Vertices
- Computational Complexity
- Approximate Maximum Flow on Separable Undirected Graphs
- Computational Complexity
This page was built for publication:
