) I worked on questions in computational complexity theory, in collaboration with Prof. Osamu Watanabe and his group at the Tokyo Institute of Technology. Computational complexity theory studies the nature and limits of efficient computation. Boolean circuits are one widely studied model of computation. This project focused on two specific questions in the area of Boolean circuit complexity. The first question concerned the relative power of general circuits versus the subclass of formulas (treelike circuits). Intuitively, formulas are memoryless: each subcomputation is used only once. This means that formulas are unable to implement simple dynamic programming algorithms, for instance which solve st-connectivity. However, there is no known mathematical proof that formulas are weaker than circuits by more than a polynomial factor. One achievement of this project is a super-polynomial separation in the power of formulas versus circuits in the restricted bounded-depth setting. A second question studied in this project concerns monotone circuits (Boolean circuits with no negation gates). A result of my PhD work is a lower bound for the average-case monotone circuit complexity of the k-clique problem on a mixture of random graphs G(n,p) and G(n,2p) for p an appropriate threshold function. An initial goal of my postdoc was to show a lower bound at G(n,p) alone. While this question remains open, using techniques developed during my postdoc at Tokyo Tech, I was recently able to achieve an average-case lower bound against polynomial-size monotone formulas. This is the first correlation bound in the monotone setting under any product distribution. In other joint work with Prof. Watanabe and Prof. Kawachi, we studied an information-theoretic query complexity problem (an abstract search problem). Our results imply lower bounds on search-to-decision reduction in a certain black-box setting.
