A combinatorial construction of almost-ramanujan graphs using the zig-zag product

No abstract is available for this paper.

• Publication year

  2008

• Venue

  Symposium on the Theory of Computing

• Publication date

  2008-05-17

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/1374376.1374424
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Iterative Construction of Cayley Expander Graphs

  2006cited by this paper
• Lifts, Discrepancy and Nearly Optimal Spectral Gap*

  2006cited by this paper
• Expander Graphs and their Applications

  2006cited by this paper
• Random graphs

  2006cited by this paper
• Derandomized Squaring of Graphs

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

  2005influential reference
• Expanders In Group Algebras

  2004cited by this paper
• A proof of Alon's second eigenvalue conjecture and related problems

  2004cited by this paper
• Smaller explicit superconcentrators

  2003cited by this paper
• A proof of alon's second eigenvalue conjecture

  2003cited by this paper
• Semi-direct product in groups and Zig-zag product in graphs: Connections and applications

  2002cited by this paper
• Randomness conductors and constant-degree lossless expanders

  2002cited by this paper
• Semi-direct product in groups and zig-zag product in graphs: connections and applications

  2001cited by this paper
• Randomness Conductors and Constant-Degree Expansion Beyond the Degree / 2 Barrier

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

  2000cited by this paper
• Eigenvalues and expansion of regular graphs

  1995cited by this paper
• Existence and Explicit Constructions of q + 1 Regular Ramanujan Graphs for Every Prime Power q

  1994cited by this paper
• On the second eigenvalue of a graph

  1991cited by this paper
• Eigenvalues and expanders

  1986cited by this paper
• lambda1, Isoperimetric inequalities for graphs, and superconcentrators

  1985cited by this paper
• il , , lsoperimetric Inequalities for Graphs , and Superconcentrators

  1985cited by this paper
• Expanders obtained from affine transformations

  1985cited by this paper
• Difference equations, isoperimetric inequality and transience of certain random walks

  1984cited by this paper
• On the complexity of a concentrator

  1973cited by this paper
• Ramanujan Graphs

  1965cited by this paper
• q-Difference Equations

  1910cited by this paper

• Quantum LDPC Codes of Almost Linear Distance via Iterated Homological Products

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

  2025influential citation
• Tight Bounds for the Zig-Zag Product

  2024cites this paper
• SIGACT News Complexity Theory Column

  2024cites this paper
• Binary Codes with Distance Close to Half

  2024cites this paper
• New Explicit Constant-Degree Lossless Expanders

  2023cites this paper
• Derandomized Squaring: An Analytical Insight into Its True Behavior

  2023cites this paper
• When Can an Expander Code Correct Ω(n) Errors in O(n) Time?

  2023cites this paper
• Pseudorandomness of the Sticky Random Walk

  2023cites this paper
• One stride ahead Advancements in Dispersed Graph Coloring

  2023cites this paper
• Pseudorandom Linear Codes are List Decodable to Capacity

  2023cites this paper
• Random Walks on Rotating Expanders

  2023cites this paper
• Pseudorandomness of expander random walks for symmetric functions and permutation branching programs

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

  2022influential citation
• List-Decoding Random Walk XOR Codes Near the Johnson Bound

  2022cites this paper
• Analyzing Ta-Shma’s Code via the Expander Mixing Lemma

  2022cites this paper
• List-Decoding XOR Codes Near the Johnson Bound

  2022cites this paper
• New near-linear time decodable codes closer to the GV bound

  2022cites this paper
• Expander Random Walks: The General Case and Limitations

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

  2021cites this paper
• Near-Optimal Cayley Expanders for Abelian Groups

  2021cites this paper
• Explicit Abelian Lifts and Quantum LDPC Codes

  2021cites this paper
• Explicit Expanders of Every Degree and Size

  2020cites this paper
• Explicit near-Ramanujan graphs of every degree

  2019cites this paper
• High-Dimensional Expanders from Expanders

  2019cites this paper
• Deterministic tensor completion with hypergraph expanders

  2019cites this paper
• 2 Review of Ramanujan and near-Ramanujan families

  2019cites this paper
• Some New Constructions and Bounds for Locally Generated Quantum Codes

  2018cites this paper
• Efficient quantum tensor product expanders and unitary t-designs via the zigzag product.

  2018influential citation
• Explicit, almost optimal, epsilon-balanced codes

  2017influential citation
• Conditional Expectation Bounds with Applications in Cryptography

  2017cites this paper
• Expansion in Lifts of Graphs

  2015cites this paper
• Gaps Between Almost-Primes and a Construction of Almost-Ramanujan Graphs

  2015cites this paper
• Almost-Ramanujan graphs and prime gaps

  2014cites this paper
• A key-distribution mechanism for wireless sensor networks using Zig-Zag product

  2012cites this paper
• Combinatorial algorithms for distributed graph coloring

  2011cites this paper
• Pseudorandomness I

  2009cites this paper
• On Construction of Almost-Ramanujan Graphs

  2009influential citation
• On the Connectivity of Key-Distribution Strategies in Wireless Sensor Networks

  2009cites this paper
• A Combinatorial Approach for Key-Distribution in Wireless Sensor Networks

  2008cites this paper
• On the Expansion of Graphs

  year unknowncites this paper