CAREER: Probabilistic and Algebraic Techniques for Computational Complexity Theory

职业：计算复杂性理论的概率和代数技术

• 批准号: 9734164
• 负责人: D Sivakumar
• 金额: $ 20.19万
• 依托单位: University of Houston
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1998
• 资助国家: 美国
• 起止时间: 1998-05-01 至 2000-04-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9734164&HistoricalAwards=false
• 关键词: CAREER; Probabilistic; Algebraic; Techniques; Computational

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.

研究活动的重点是开发新的工具和技术来解决计算复杂性理论中的基本问题。一个推力是寻找适应的概率方法的保罗鄂尔多斯统一复杂性理论。 第二个重点是调查复杂性理论中的各种问题与鲁棒纠错码的各种结构和算法问题以及相关的代数和几何结构之间的联系。 除了对复杂性理论的贡献外，这项研究还可能对概率方法、去随机化和编码理论做出贡献。教育活动围绕着设计新千年的理论计算机科学本科课程的更广泛的目标。 其动机源于程序正确性的日益重要性，以及设计与计算机科学不断变化的角色相关并反映其变化的理论课程的需要。 教育活动整合和统一离散数学，自动机和形式语言理论，程序验证和正确性，以及计算复杂性理论。 一个亮点是自动机理论作为教学程序正确性的有效操场的新应用。教育活动还包括开发算法工程课程，其愿景是在算法设计和实现中整合研究，教育，实验和培训，并具有特定目标，为大规模数据集开发基础算法的超高效实现。