Construction of expanders and superconcentrators using Kolmogorov complexity

DOI<64::AID-RSA5>3.0.CO;2-3 10.1002/1098-2418(200008)17:1<64::AID-RSA5>3.0.CO;2-3zbMath0953.68065OpenAlexW1512371369MaRDI QIDQ4500485

Uwe Schoening

Publication date: 29 January 2001

Full work available at URL: https://doi.org/10.1002/1098-2418(200008)17:1<64::aid-rsa5>3.0.co;2-3

zbMATH Keywords

Kolmogorov complexityexpander graphs

Mathematics Subject Classification ID

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

Related Items (3)

Smaller superconcentrators of density 28 ⋮ Note on ``Smaller explicit superconcentrators ⋮ ON CONSTRUCTION OF ALMOST-RAMANUJAN GRAPHS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On using deterministic functions to reduce randomness in probabilistic algorithms
• Expanders, randomness, or time versus space
• Ramanujan graphs
• Eigenvalues and expanders
• Explicit constructions of linear-sized superconcentrators
• Many hard examples for resolution
• Hard examples for resolution
• Better expanders and superconcentrators
• Superconcentrators
• Space bounds for a game on graphs
• Generalized Connectors
• Generalized Connection Networks for Parallel Processor Intercommunication
• Expanders that beat the eigenvalue bound

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