Construction of expanders and superconcentrators using Kolmogorov complexity

DOI10.1002/1098-2418(200008)17:1%3C64::AID-RSA5%3E3.0.CO;2-3MaRDI QIDQ4500485zbMATH OpenOpenAlexFDO

Authors Uwe Schöning

Publication date 29 January 2001

Full work available at URL https://doi.org/10.1002/1098-2418(200008)17:1%3C64::aid-rsa5%3E3.0.co;2-3

zbMATH Keywords

expander graphsKolmogorov complexity

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Approximating Kolmogorov complexity
• scientific article; zbMATH DE number 3974293
• Compressibility and Kolmogorov complexity
• Kolmogorov complexity cores
• scientific article; zbMATH DE number 4086981
• Kolmogorov Complexity: Sources, Theory and Applications
• On the Kolmogorov complexity of arbitrary objects
• Constructive dimension equals Kolmogorov complexity
• Kolmogorov complexity

Cites work

• Better expanders and superconcentrators
• Eigenvalues and expanders
• Expanders that beat the eigenvalue bound
• Expanders, randomness, or time versus space
• Explicit constructions of linear-sized superconcentrators
• Generalized Connection Networks for Parallel Processor Intercommunication
• Generalized Connectors
• Hard examples for resolution
• scientific article; zbMATH DE number 3864514 (Why is no real title available?)
• scientific article; zbMATH DE number 18979 (Why is no real title available?)
• scientific article; zbMATH DE number 41062 (Why is no real title available?)
• scientific article; zbMATH DE number 1263215 (Why is no real title available?)
• scientific article; zbMATH DE number 1010621 (Why is no real title available?)
• scientific article; zbMATH DE number 1361471 (Why is no real title available?)
• Many hard examples for resolution
• On using deterministic functions to reduce randomness in probabilistic algorithms
• Ramanujan graphs
• Space bounds for a game on graphs
• Superconcentrators

Cited in

(5)

• Note on ``Smaller explicit superconcentrators
• scientific article; zbMATH DE number 3864514 (Why is no real title available?)
• ON CONSTRUCTION OF ALMOST-RAMANUJAN GRAPHS
• Expanders and Diffusers
• Smaller superconcentrators of density 28

This page was built for publication: Construction of expanders and superconcentrators using Kolmogorov complexity

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