CAREER: Probabilistic and Algebraic Techniques for Computational Complexity Theory

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

The focus of the research activity is developing new tools and techniques for attacking fundamental problems in computational complexity theory. One thrust is the search for adaptations of the probabilistic method of Paul Erdos to uniform complexity theory. A second thrust is the investigation of the connections between various questions in complexity theory and various structural and algorithmic questions concerning robust error-correcting codes, and related algebraic and geometric structures. In addition to contributions to complexity theory, this research has the potential for making contributions to the probabilistic method; derandomization and coding theory. The educational activities are centered around the broader goal of designing an undergraduate curriculum in theoretical computer science for the new millennium. The motivation stems from the growing importance of program correctness, and from the need to design theory curricula relevant to and reflecting the changing role of computer science. The educational activity integrates and unifies discrete mathematics, automata and formal language theory, program verification and correctness, and computational complexity theory. A highlight is a novel application of automata theory as an effective playground for teaching program correctness. The educational activities also include developing a curriculum in algorithm engineering, with a vision to integrate research, education, experimentation and training in algorithm design and implementation, and with specific goals to develop ultra-efficient implementations of fundamental algorithms for massive data sets.