Speaker: Kaave Hosseini, Assistant Professor, University of Rochester

Abstract:
Boolean matrices are a popular way to model relationships between data points in computer science and mathematics. A fundamental feature of such data is its intrinsic dimensionality, captured by a parameter called dimension complexity (also known as sign-rank) which informally speaking, is the smallest dimension in which the data can be “linearized.” Despite having been studied for decades, dimension complexity is notoriously difficult to analyze, and several basic questions remain open.

In this talk, I will describe a line of work developing a framework for studying dimension complexity using topology, and its success in addressing problems in learning theory and communication complexity. I will then explain how investigating the limitations of this approach led to new progress on classical problems in combinatorial topology, convex geometry, and graph theory.

This talk is based on several projects, with collaborators including Florian Frick, Gabriel Hart, Hamed Hatami, Xiang Meng, Eric Myzelev, Arya Narnapatti, and Aliaksei Vasileuski.

Bio:
Kaave Hosseini is an Assistant Professor in the Department of Computer Science at the University of Rochester. Previously he was a Postdoctoral Associate in the Department of Mathematical Sciences at Carnegie Mellon University. He obtained his Ph.D. in Computer Science from UC San Diego under the supervision of Shachar Lovett. Before that, he did his BSc in Mathematics and Computer Science at Sharif University of Technology, Tehran.

Prof. Hosseini is interested in theoretical computer science and additive combinatorics. "Usually, the problems I work on have to do with the interplay between algebraic, analytic, and combinatorial structure."