RESEARCH STATEMENT

It is my strong believe that a deep study of the questions of what can and cannot be efficiently computed are some of the most important questions of our scientific community. The importance of studying computation in an abstract way is the main reason for my interest in the field of theoretical computer science, and complexity theory in particular. For all the wonderful results that theoretical computer science has given us, there is even more questions to be answered. Nothing will make me happier, but to see some of those questions answered or at least see theories which point to directions for possible solutions. My believe is that in addition to the techniques already developed within theoretical computer science, this search will involve more applications of results and ideas from other areas of mathematics like number theory, algebra, and analysis. Previous work In my dissertation I studied two somewhat opposing questions from complexity theory – an upper bound on the space-complexity of undirected st-connectivity, and a lower bound on the size of certain depth-three circuits computing the parity function. Undirected st-connectivity (UST-CONN) is the problem of checking whether two vertices of an undirected graph are connected by a path. Constructing an algorithm for this problem which uses space close to the optimal O(log n