Topic: sublinear algorithms

Join Tom Gur’s group to study classical and quantum complexity. Research directions include sublinear algorithms, property testing, cryptography, proof systems, locally testable codes, learning theory, harmonic analysis and additive combinatorics. The one-year project connects theoretical computer science with mathematical and quantum methods.

Communication complexity studies how cooperating parties solve computational problems while exchanging as little information as possible. This workshop addresses its core theory and applications to streaming and sublinear algorithms, data structures, distributed computation, learning, cryptography and game theory. Participants will connect methods from probability, combinatorics, graph theory, matrix analysis and information theory. Cross-disciplinary collaboration is intended to advance open problems, reveal relationships between these areas and support emerging researchers.