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.

Date:	14:40-15:20, Thursday, March 26, 2009

Venue:	FIT Building 1-315, 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 two-year 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.