Algorithms, Combinatorics and Optimization Seminar November 30, 2023 3:30pm — 4:30pm Location: In Person - Wean 8220 Speaker: KKAVE HOSSEINI , Assistant Professor, Department of Computer Science, University of Rochester https://www.cs.rochester.edu/u/shossei2/ On relaxations of “rank” for boolean matrices 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. Refreshments — 3:00 pm, Math Lounge / Wean 6220 Event Website: https://aco.math.cmu.edu/abs-23-24/nov30.html Add event to Google Add event to iCal
