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.
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.