Three Topics in Combinatorics with Relations to Theoretical Computer Science

与理论计算机科学相关的组合学的三个主题

• 批准号: 0400960
• 负责人: Ravindran Kannan
• 金额: $ 13.1万
• 依托单位: Yale University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2004
• 资助国家: 美国
• 起止时间: 2004-05-15 至 2008-04-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0400960&HistoricalAwards=false
• 关键词: Three; Topics; Combinatorics; Relations; Theoretical

We intend to study three topics in combinatorics which are related totheoretical computer science. We will study the diameter problem forgraphs of polytopes aiming at a polynomial upper bound, and also try tofind versions of the simplex algorithm with sub-exponential worst casebehavior. We will study Boolean functions, their Fourier transform and howit relates to questions in probability and complexity. We will also try tofind general methods to relate the solution of a positive integerprogramming problem and its linear programming relaxation.Combinatorics have now become the central mathematical discipline intheoretical computer science (and various applied areas of computerscience as well). The role of combinatorics in computer science today isquite similar to the role of logic in the early days of computation.Problems from theoretical computer science enriched and enforcedcombinatorial thinking and areas which were regarded as having clear intellectual merit have gained surprising real-life applications. Linearprogramming and the simplex algorithm are among the most importantapplications of computers and in our earlier work as well as the plannedresearch. We intend to study fundamental questions concerning linearprogramming. Another area of our research, the Fourier analysis of Booleanfunctions is a relatively new area which we helped to develop in the past. In view of the importance of Fourier analysis in other areas we should nothave been surprised to see its recent applications in combinatorics andcomplexity theory and we intend to explore further connections.

我们打算学习三个与理论计算机科学有关的组合学主题。我们将针对多项式上界研究多面体图的直径问题，并尝试找到具有亚指数最坏情况行为的单纯形算法版本。我们将学习布尔函数，它们的傅立叶变换以及它与概率和复杂性问题的关系。我们也将试图找到一般方法来联系一个正整数规划问题的解决方案和它的线性规划松弛。组合数学现在已经成为理论计算机科学（以及计算机科学的各种应用领域）的中心数学学科。今天组合学在计算机科学中的作用与逻辑在计算早期的作用非常相似。理论计算机科学中的问题丰富并加强了组合思维，被认为具有明显智力价值的领域已经获得了令人惊讶的实际应用。 线性规划和单纯形算法是计算机最重要的应用之一，在我们早期的工作以及计划的研究中也是如此。我们打算研究有关线性规划的基本问题。我们研究的另一个领域，布尔函数的傅立叶分析是一个相对较新的领域，我们在过去帮助开发。 鉴于傅立叶分析在其他领域的重要性，我们不应该对它最近在组合学和复杂性理论中的应用感到惊讶，我们打算探索进一步的联系.