Derandomized Squaring of Graphs

No abstract is available for this paper.

• Publication year

  2005

• Venue

  International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

• Publication date

  2005-08-22

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/11538462_37
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Expander flows, geometric embeddings and graph partitioning

  2009cited by this paper
• Electronic Colloquium on Computational Complexity, Report No. 22 (2005) Pseudorandom Walks in Biregular Graphs and the RL vs. L Problem ∗ PRELIMINARY VERSION

  2005cited by this paper
• Undirected ST-connectivity in log-space

  2005influential reference
• Expander flows, geometric embeddings and graph partitioning

  2004cited by this paper
• Smaller explicit superconcentrators

  2003cited by this paper
• Bipartite Subgraphs and the Smallest Eigenvalue

  2000cited by this paper
• Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors

  2000influential reference
• Derandomized graph products

  1995cited by this paper
• Pseudorandomness for network algorithms

  1994cited by this paper
• Universal Traversal Sequences for Expander Graphs

  1993cited by this paper
• Conductance and convergence of Markov chains-a combinatorial treatment of expanders

  1989cited by this paper
• Random walks, universal traversal sequences, and the complexity of maze problems

  1979cited by this paper
• Relationships Between Nondeterministic and Deterministic Tape Complexities

  1970cited by this paper
• Derandomized Squaring of Graphs

  year unknowncited by this paper
• Journal of Graph Algorithms and Applications Many-to-one Boundary Labeling

  year unknowncited by this paper

• Tractable Unordered 3-CNF Games

  2025cites this paper
• Weighted Pseudorandom Generators for Read-Once Branching Programs via Weighted Pseudorandom Reductions

  2025cites this paper
• Wide Replacement Products Meet Gray Codes: Toward Optimal Small-Bias Sets

  2025cites this paper
• A Logspace Constructive Proof of L=SL

  2025influential citation
• On Sums of INW Pseudorandom Generators

  2025cites this paper
• Limitations of the Impagliazzo–Nisan–Wigderson Pseudorandom Generator Against Permutation Branching Programs

  2024influential citation
• A Study of Error Reduction Polynomials

  2024cites this paper
• Comparison Theorems for the Mixing Times of Systematic and Random Scan Dynamics

  2024cites this paper
• Tight Bounds for the Zig-Zag Product

  2024cites this paper
• Expanderizing Higher‐Order Random Walks

  2024influential citation
• Efficient Approximate Unitary Designs from Random Pauli Rotations

  2024cites this paper
• Small-Space Spectral Sparsification via Bounded-Independence Sampling

  2024cites this paper
• Weighted Pseudorandom Generators via Inverse Analysis of Random Walks and Shortcutting

  2023influential citation
• Derandomized Squaring: An Analytical Insight into Its True Behavior

  2023cites this paper
• Explicit orthogonal and unitary designs

  2023influential citation
• Singular Value Approximation and Reducing Directed to Undirected Graph Sparsification

  2023cites this paper
• Recursive Error Reduction for Regular Branching Programs

  2023cites this paper
• Singular Value Approximation and Sparsifying Random Walks on Directed Graphs

  2023cites this paper
• Almost Ramanujan Expanders from Arbitrary Expanders via Operator Amplification

  2022cites this paper
• The Space Complexity of Undirected Graph Exploration

  2022cites this paper
• Recent Progress on Derandomizing Space-Bounded Computation

  2022cites this paper
• Derandomizing Directed Random Walks in Almost-Linear Time

  2022cites this paper
• On the Problem of Undirected st-connectivity

  2022influential citation
• Hitting sets for regular branching programs

  2022cites this paper
• Expander random walks: a Fourier-analytic approach

  2021cites this paper
• Pseudodistributions that beat all pseudorandom generators (extended abstract)

  2021cites this paper
• Limitations of the Impagliazzo-Nisan-Wigderson Pseudorandom Generator against Permutation Branching Programs

  2021influential citation
• Expander Random Walks: The General Case and Limitations

  2021cites this paper
• Deterministic Approximation of Random Walks via Queries in Graphs of Unbounded Size

  2021cites this paper
• Pseudorandom Pseudo-distributions with Near-Optimal Error for Read-Once Branching Programs

  2020cites this paper
• Spectral Sparsification via Bounded-Independence Sampling

  2020cites this paper
• Pseudorandom Generators for Unbounded-Width Permutation Branching Programs

  2020influential citation
• FPT-space Graph Kernelizations

  2020cites this paper
• Expander Construction in VNC1

  2020cites this paper
• High-precision Estimation of Random Walks in Small Space

  2019cites this paper
• Deterministic Approximation of Random Walks in Small Space

  2019cites this paper
• Bounded Independence Plus Noise

  2019cites this paper
• Combinatorial Optimization On Massive Datasets: Streaming, Distributed, And Massively Parallel Computation

  2018cites this paper
• Massively Parallel Algorithms for Finding Well-Connected Components in Sparse Graphs

  2018cites this paper
• Expanding Generating Sets for Solvable Permutation Groups

  2018cites this paper
• Hitting sets with near-optimal error for read-once branching programs

  2018cites this paper
• Lecture 2 – Deterministic Amplification

  2018cites this paper
• 1 Undirected Graphs as Operators Definition 1

  2018cites this paper
• Randomness Extractors and Space-Bounded Computation

  2018cites this paper
• Derandomization Beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space

  2017influential citation
• A MODERN APPROACH

  2017cites this paper
• Explicit, almost optimal, epsilon-balanced codes

  2017cites this paper
• Construction in VNC 1 ( Extended Abstract )

  2017cites this paper
• Survey : The Zig-Zag Product and USTCON ∈

  2016influential citation
• 5 Constructing bipartite vertex expanders

  2016cites this paper
• Expansion in Lifts of Graphs

  2015cites this paper
• Formation of Robust Multi-Agent Networks through Self-Organizing Random Regular Graphs

  2015cites this paper
• Randomized Search of Graphs in Log Space and Probabilistic Computation

  2014cites this paper
• Decentralized graph processes for robust multi-agent networks

  2014cites this paper
• Pseudorandomness for Regular Branching Programs via Fourier Analysis

  2013cites this paper
• Small-Bias Sets for Nonabelian Groups: Derandomizing the Alon-Roichman Theorem

  2013cites this paper
• T he C omputational C omplexity C olumn

  2013cites this paper
• Random Walks on Some Basic Classes of Digraphs

  2013cites this paper
• Small-Bias Sets for Nonabelian Groups - Derandomizations of the Alon-Roichman Theorem

  2013cites this paper
• The Computational Complexity of Randomness

  2013cites this paper
• Testing Small Set Expansion in General Graphs

  2012cites this paper
• Near-Optimal Expanding Generating Sets for Solvable Permutation Groups

  2012cites this paper
• Nonlinear spectral calculus and super-expanders

  2012influential citation
• Pseudorandomness for Permutation Branching Programs Without the Group Theory

  2012cites this paper
• Testing Conductance in General Graphs

  2011cites this paper
• Bravely, Moderately: A Common Theme in Four Recent Works

  2011cites this paper
• Pseudorandom Generators for Group Products ( version with the geometric proof — 2 nd draft )

  2011cites this paper
• Pseudorandom generators for group products: extended abstract

  2011cites this paper
• Computational applications of invariance principles

  2011cites this paper
• Realizable paths and the NL vs L problem

  2011influential citation
• Pseudorandomness for Permutation and Regular Branching Programs

  2011cites this paper
• Pseudorandom generators for combinatorial checkerboards

  2011cites this paper
• Expansion in Soluble Groups

  2011influential citation
• Realizable Paths and the NL vs L Problem

  2010cites this paper
• Pseudorandom Generators for Group Products

  2010cites this paper
• Pseudorandom Bit Generators That Fool Modular Sums

  2009cites this paper
• Towards a calculus for non-linear spectral gaps

  2009cites this paper
• Pseudorandomness I

  2009cites this paper
• Pseudorandom generators for polynomial threshold functions

  2009cites this paper
• Computational Complexity: A Modern Approach

  2009cites this paper
• Undirected connectivity in log-space

  2008cites this paper
• A combinatorial construction of almost-ramanujan graphs using the zig-zag product

  2008cites this paper
• Codes, graphs and graph based codes

  2007influential citation
• Expanders made elementary : A combinatorial analysis of an expander construction

  2007cites this paper
• Pseudorandom walks on regular digraphs and the RL vs. L problem

  2006cites this paper
• Expander Graphs and their Applications

  2006cites this paper
• SIGACT news complexity theory column 51

  2006cites this paper
• On expander graphs and connectivity in small space

  2006cites this paper
• Some graph products and their expansion properties

  2006cites this paper
• Undirected ST-connectivity in log-space

  2005cites this paper
• Derandomized Constructions of k-Wise (Almost) Independent Permutations

  2005cites this paper
• The Computational Complexity Column

  2004cites this paper
• A Common Theme in Four Recent Works

  year unknowncites this paper
• Derandomized Squaring of Graphs

  year unknowncites this paper