Partition expanders

DOI10.1007/S00224-016-9738-5MaRDI QIDQ2363958zbMATH OpenOpenAlexFDO

Authors Dmitry Gavinsky, Pavel Pudlák

Publication date 17 July 2017

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

Full work available at URL https://doi.org/10.1007/s00224-016-9738-5

zbMATH Keywords

communication complexityexpanderspseudorandomness

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Partition expanders
• Splitting an Expander Graph
• scientific article; zbMATH DE number 1688365
• Pseudorandomness for network algorithms
• On multi-partition communication complexity

Cites work

• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Asymptotic enumeration by degree sequence of graphs with degrees \(o(n^{1/2})\)
• scientific article; zbMATH DE number 1342092 (Why is no real title available?)
• Monotone expanders: constructions and applications
• Nonlinear spectral calculus and super-expanders
• Pseudorandomness for network algorithms
• Random Cayley graphs and expanders
• Random Cayley graphs are expanders: a simple proof of the Alon-Roichman theorem
• Randomness conductors and constant-degree lossless expanders
• Simultaneous communication protocols with quantum and classical messages
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• The variation of the spectrum of a normal matrix
• Weighted sums of certain dependent random variables

Cited in

(6)

• Remarks on partitions into expanders
• Partition expanders
• scientific article; zbMATH DE number 5942192 (Why is no real title available?)
• Turning the Partition Crank
• Maximum transfer distance between partitions
• From expanders to hitting distributions and simulation theorems

This page was built for publication: Partition expanders

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