Monotone expanders: constructions and applications

DOI10.4086/TOC.2010.V006A012MaRDI QIDQ3002825zbMATH OpenOpenAlexFDO

Authors Zeev Dvir, A. Wigderson

Publication date 24 May 2011

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4086/toc.2010.v006a012

zbMATH Keywords

\(k\)-page graphsexpanderpushdown graphszig-zag

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Monotone expansion
• Layouts of Expander Graphs
• Expander graphs and their applications
• Expansion in SL₂( R) and monotone expanders
• Local expanders

Cited in

(21)

• Monotonicity of auto-expansions
• Local expanders
• Expander construction in \(\mathrm{VNC}^1\)
• Lossless dimension expanders via linearized polynomials and subspace designs
• On exteriority notions in book embeddings and treewidth
• Partition expanders
• Layered separators in minor-closed graph classes with applications
• Constraints, MMSNP and expander relational structures
• Additive combinatorics: with a view towards computer science and cryptography -- an exposition
• Layouts of Expander Graphs
• Expansion in SL₂( R) and monotone expanders
• Expander construction in \(\mathsf{VNC}^1\)
• Subspace designs based on algebraic function fields
• From expanders to hitting distributions and simulation theorems
• scientific article; zbMATH DE number 7250144 (Why is no real title available?)
• Monotone expansion
• Connections between graphs and matrix spaces
• Must the communication graph of MPC protocols be an expander?
• On linear-algebraic notions of expansion
• Almost-Ramanujan expanders from arbitrary expanders via operator amplification
• Towards lower bounds on locally testable codes via density arguments

This page was built for publication: Monotone expanders: constructions and applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3002825)