Institute for Theoretical Computer Science, Tsinghua University
简介:
Abstract
Circuit complexity saw great progress in the 1980'ies
In this talk we will give some results on small-depth circuits and formulas. We sketch several of the proofs and point to some open problems.
Bio of the Speaker
Johan Håstad was born in 1960 in Sweden. He got his Ph.D in mathematics at MIT in 1986 and remained at MIT for a post-doc until 1988 when he joined the Royal Institute of Technology in Stockholm, Sweden. He obtained a full professorship in 1991 and has remained at Stockholm but was a visiting scientist at the Institute for Advanced Study for the academic year 2000/01. Johan Håstad is a member of the Royal Academy of Sciences of Sweden since 2001.
