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本项目研究布尔函数计算的组合和代数模型。这些模型是布尔电路和公式，分支程序，跨度程序和通信复杂性模型。在这些模型中的计算问题的复杂性对应于其固有的复杂性方面的重要的计算resources.The主要问题在这项研究中解决的是：寻找新的方法来证明复杂性的下限，随机性和伪随机性的作用，布尔函数的复杂性，以及在上述模型的容错问题。该项目的教育部分包括编制关于容错和纠错码的高级本科课程，以及编制一系列关于复杂性理论的研究生研究课程。