The ACO Seminar (2023–2024)

In this talk I will discuss a few well-known complexity parameters for boolean matrices that are relaxations of rank (over the reals). These are approximate rank, sign-rank/dimension complexity, margin/discrepancy, gamma2 norm, and approximate-gamma2. The focus of this talk is to study the meta-question: "what is the relationship between these parameters?". It turns out that study of this meta-question connects many different areas and equivalent stories are to be told in learning theory, communication complexity, convex geometry, theory of dimensionality reduction, etc. I will try to answer some of these pairwise relations using different tools such as Fourier analysis, topology, and also ideas from discrete geometry.