CAREER: Combinatorial and algebraic models of computation

这个项目研究布尔函数的组合和代数计算模型。这些模型是布尔电路和公式、分支程序、跨度程序和通信复杂性模型。这些模型中计算问题的复杂性与其在重要计算资源方面的固有复杂性相对应。本文研究的主要问题是：寻找证明复杂度下界的新方法，随机性和伪随机性在布尔函数复杂度中的作用，以及上述模型中的容错问题。该项目的教育部分包括开发一门关于容错和纠错码的高级本科课程，以及开发一系列复杂性理论的研究生研究课程。

GalCCR-9874862This project studies combinatorial and algebraic models of computation for Boolean functions. Such models are Boolean circuits and formulae, branching programs, span programs and models of communication complexity. The complexity of computational problems in these models corresponds to their inherent complexity in terms of important computational resources.The main questions addressed in this research are: finding new methods for proving complexity lower bounds, the role of randomness and pseudorandomness in the complexity of Boolean functions, and issues of fault tolerance in the above models. The educational component of the project includes the development of an upper level undergraduate course on fault tolerance and error correcting codes, and development of a series of graduate research courses in complexity theory.