Topics in Theoretical Computer Science

点击翻译按钮获取中文摘要

This project studies important open problems in each of several domains of theoretical computer science: circuit complexity, simulating randomness, parallel computation, computational and combinatorial geometry, and computational number theory. These problems are related in that they can be attacked using similar mathematical methods. For each topic, progress is expected either by generating more efficient algorithms for the tasks in question, or by providing lower bounds that highlight features of the underlying structure.