The Taub Faculty of Computer Science Events and Talks

More than twenty years ago, Capalbo, Reingold, Vadhan and Wigderson gave the first (and up to date only) explicit construction of a bipartite expander with almost full combinatorial expansion. The construction incorporates zig-zag ideas together with extractor technology, and is rather complicated. We give an alternative construction that builds upon recent constructions of hyper-regular, high-dimensional expanders. The new construction is, in our opinion, simple and elegant. Beyond demonstrating a new, surprising, and intriguing, application of high-dimensional expanders, the construction employs new ideas which we hope may lead to progress on the still remaining open problems in the area Joint work with Itay Cohen and Roy Roth from Tel-Aviv University.