Date:  14:4015:20, Thursday, March 26, 2009 
Venue:  FIT Building 1315, Tsinghua University 
Title:  Hilbert's thirteenth problem and circuit complexity

Speaker:  Kristoffer Arnsfelt Hansen 
Biography: 
Kristoffer Arnsfelt Hansen received his PhD degree from Aarhus University in 2006. After this he spent one year as a postdoc at University of Chicago and is currently in a twoyear postdoc position at Aarhus University. Kristoffer's main research interest is computational complexity theory, in particular Boolean circuit complexity. Additional interests include algorithms and game theory.

Abstract: 
We study the following question, communicated to us by Mikl\'{o}s Ajtai: Can all explicit (e.g., polynomial time computable) functions $f: (\{0,1\}^w)3\rightarrow \{0,1\}^w$ be computed by word circuits of constant size? Here, a word circuit is an acyclic circuit where each wire holds a word (i.e., an element of $\{0,1\}^w$) and each gate $G$ computes some binary operation $g_G:(\{0,1\}^w)2 \rightarrow \{0,1\}^w$, defined for all word lengths $w$. As our main result, we present an explicit function so that its $w$'th slice for any $w \geq 8$ cannot be computed by word circuits with at most 4 gates. Also, we show that Ajtai's question may be difficult to answer in the negative by formally relating it to open problems concerning ACC$^0$ circuits.
Joint work with Oded Lachish and Peter Bro Miltersen.
