57 KAM Mathematical Colloquium
Prof. Nati Linial
Hebrew University, Jerusalem
COMPLEXITY MEASURES OF SIGN MATRICES
streda 8. unora 2006 v 10:40, poslucharna S5, druhe patro
KAM MFF UK
Malostranske nam. 25
118 00 Praha 1
Abstract
Why is our progress in computational complexity so slow? We claim that computational complexity ought to be investigated within a broader context. There are too few general mathematical tools to systematically deal with complexity, even though understanding complexity is one of the most important challenges of modern science. We have initiated a systematic study of complexity measures of matrices and matrices of +-1 in particular. The measures we consider come from a variety of mathematical disciplines including Banach Space theory, Communication Complexity and Machine Learning.
This talk is based on joint papers with Adi Shraibman and with
Shraibman, Schechtmand and Mendelson.
O přednášejícím
Nathan (Nati) Linial absolvoval Hebrejskou Universitu v Jeruzaleme, kde je v soucasne dobe profesorem informatiky. Jeho vedecke zajmy jsou neobycejne siroke a zahrnuji kombinatoriku, teorii algoritmu, geometrii, aplikace matematicke analyzy a molekularni biologii. Soubory jeho clanku a prednasek o expanderech, o metrickych problemech Ramseyova typu, o nahodnych nakrytich grafu a o aplikacich Fourierovy analyzy jsou velmi zname a pomohly k zavedeni (a popularite) uvedenych oblasti. Prof. Linial prednesl zvanou prednasku na Mezinarodnim matematickem kongresu v roce 2002 v Pekingu. Je castym hostem prednich svetovych pracovisť (uvedme napr. Stanford, IBM, MIT, UC Berkeley, UC San Diego, Rutgers, Microsoft). V soucasnosti prednasi na MFF cyklus prednasek v ramci projektu DOCCOURSE, ktery je venovan aplikacim Fourierovy analyzy v informatice a kombinatorice. N. Linial je znamy svymi velmi peknymi prednaskami. Jeho kolokvium je venovano jeste jinemu okruhu jeho zajmu - matematickym souvislostem teorie slozitosti - a je urceno siroke matematicke a informaticke verejnosti.
