From expanders to hitting distributions and simulation theorems

DOI10.4230/LIPICS.MFCS.2018.4MaRDI QIDQ5005099zbMATH OpenOpenAlexFDO

Authors Alexander Kozachinskiy

Publication date 4 August 2021

Full work available at URL https://arxiv.org/abs/1802.04014

zbMATH Keywords

expandershitting distributionssimulation theorems

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Simulation theorems via pseudo-random properties
• scientific article; zbMATH DE number 1263224
• Expanders that beat the eigenvalue bound: Explicit construction and applications
• Partition expanders
• Monotone expanders: constructions and applications

Cites work

• Communication Complexity
• Cumulative space in black-white pebbling and resolution
• Deterministic communication vs. partition number
• Entropy waves, the zig-zag graph product, and new constant-degree expanders
• Lower bounds for elimination via weak regularity
• Query-to-communication lifting for BPP
• Ramanujan graphs
• Rectangles are nonnegative juntas
• Separation of the monotone NC hierarchy
• Structure of protocols for XOR functions

Cited in

(3)

• Simulation theorems via pseudo-random properties
• Lifting Theorems for Equality
• Query-to-communication lifting for BPP using inner product

This page was built for publication: From expanders to hitting distributions and simulation theorems

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