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.