Events and Activities

In theoretical computer science, an increasingly important role is being played by sparse high-dimensional expanders (HDXs), of which we know two main constructions: "building" HDXs [Ballantine'00, ...] and "coset complex" HDXs [Kaufman--Oppenheim...

This talk will be about two related results, one in complexity theory and one in learning.

On the learning side, we investigate the sample complexity of smooth boosters - These are boosting algorithms that do not place too much weight on any given...

A valency argument is an elegant and well-known technique for proving impossibility results in distributed computing. It is an example of an extension-based proof, which is modelled as an interaction between a prover and a protocol. Even though...