#матлог #учёба #спецсеминар

Kolmogorov seminar on complexity (for receive the zoom link, please email nikolay.vereshchagin@gmail.com)

Date: Dec 16, 2024. Time: 18:30 (MSK), 16:30 (CET)
Speaker: Andrey Storozhenko, UCLA
Title: The communication complexity of approximating matrix rank (sequel)

It was shown that if Alice and Bob have n times n matrices A and B over a finite field, then deciding, if A + B have full rank requires n^2 log |F| bits, for deterministic protocols. Next time there will be a lower bound against randomized protocols (and probably for the approximate version of the problem).

➰ ВК