Computer Science/Discrete Mathematics

In this talk, I will discuss the solution to several problems in two closely related settings: set families in 2^[n] with many disjoint pairs, and low-rank matrices with many zero entries.

Highlights include a resolution of an old question of Daykin...

We propose an extension of Yao's standard two-party communication model, where Alice and Bob respectively hold probability distributions p and q over inputs to a function f, rather than singleton inputs. Their goal is to estimate E[f(x,y)] to within...

The Linear Ordering Principle (LOP) is a total search problem that generalizes the task of finding the minimum element of a given order to settings in which the order need not be total. Building on this, Korten and Pitassi (FOCS 2024) introduced the...

Two vector spaces of the same finite dimension are related by a linear isomorphism; that’s how the dimension is defined. Similarly, two simple subalgebras over complex numbers that are closed under conjugate transpose are related by a unitary...