Seminar • Algorithms and Complexity • Notions of “Rank” for Boolean Matrices

Please note: This seminar will take place in M3 4206 and online.

Kaave Hosseini, Assistant Professor
Department of Computer Science, University of Rochester

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?”. Surprisingly, this meta question is not yet fully understood. I will try to answer some of these pairwise relations using different tools such as Fourier analysis, topology, and also ideas from discrete geometry.

It turns out that study of this meta question connects many different branches of mathematics and equivalent stories are to be told in learning theory, communication complexity, convex geometry, theory of dimensionality reduction, etc. For example, in learning theory one related question is: if a binary concept class is learnable via large margin classifiers (such as SVM) does it imply that it is learnable via linear programming, and vice versa? In communication complexity, one question is whether one can turn a public-randomness protocol into a private-randomness protocol without a super constant overhead, if one allows the error probability to get arbitrarily close to 1/2.

To attend this seminar in person, please go to M3 4206. You can also attend virtually using Zoom at https://uwaterloo.zoom.us/j/7091329932?pwd=M1pIVkJyc2dDdmp3emNLV1RpQ2crQT09.