Computational complexity and logic

我计划继续我在计算复杂性和证明复杂性方面的研究。我目前在复杂性理论方面的工作是由从多项式时间中分离对数空间（确定性和非确定性）的问题激发的。我的合作者和我已经制定了一个计算问题（树评估问题），对于这个问题，我们有一个需要超对数空间的约束空间最优算法。我们使用分支程序模型的计算空间，其中一个超多项式下界的状态数意味着所需的分离。我们已经证明了这样一个限制分支程序的下限，并将努力逐步消除限制。在证明复杂性方面，我将继续与我的学生合作，了解证明组合定理所需概念的复杂性。

I plan on continuing my research in both computational complexity and proof complexity. My current work in complexity theory is motivated by the problem of separating logarithmic space (deterministic and nondeterministic) from polynomial time. My collaborators and I have formulated a computational problem (the Tree Evaluation Problem), for which we have a conjectured space-optimal algorithm requiring superlogarithmic space. We use the branching program model of computational space, for which a superpolynomial lower bound on the number of states implies the desired separation. We have proved such a lower bound for restricted branching programs, and will work toward gradually removing the restrictions.In proof complexity I will continue working with my students on projects motivated by understanding the complexity of concepts needed to prove combinatorial theorems.