Семинары: Нога Алон, Signrank and its applications in combinatorics and complexity

СЕМИНАРЫ


Лекции приглашенных математиков 24 июня 2015 г. 17:05, г. Москва, г. Долгопрудный, Институтский пер., 9, Новый корпус МФТИ, ауд. 239НК

Signrank and its applications in combinatorics and complexity Noga Alon Tel Aviv University
Аннотация: The sign-rank of a real matrix $A$ with no 0 entries is the minimum rank of a matrix $B$ so that $A_{i,j}B_{i,j} \gt 0$ for all $i,j$. The study of this notion combines combinatorial, algebraic, geometric and probabilistic techniques with tools from real algebraic geometry, and is related to questions in Communication Complexity, Computational Learning and Asymptotic Enumeration. I will discuss the topic and describe its background, several recent results from joint work with Morn and Yehudayoff, and some intriguing open problems. Website: https://mipt.ru/education/chairs/dm/education/lectures/lektsiya-professora-n-alona.php