CAREER: Combinatorial and algebraic models of computation

职业：计算的组合和代数模型

• 批准号: 9874862
• 负责人: Anna Gal
• 金额: $ 20万
• 依托单位: University of Texas at Austin
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1999
• 资助国家: 美国
• 起止时间: 1999-07-15 至 2004-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9874862&HistoricalAwards=false
• 关键词: CAREER; Combinatorial; algebraic; models; 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.

GALCCR-9874862 THIS项目研究布尔函数的计算组合和代数模型。这样的模型是布尔电路和公式，分支程序，跨度程序和通信复杂性的模型。这些模型中计算问题的复杂性在重要的计算资源方面对应于它们的固有复杂性。本研究中解决的主要问题是：寻找证明复杂性下降的新方法，随机性和伪界性在布尔函数的复杂性中的作用以及上述模型中的错误容忍问题。该项目的教育组成部分包括开发有关容错和错误校正代码的上层本科课程，以及开发复杂性理论中一系列研究生研究课程。