课题基金 / 基金详情

Geometry and representation theory in computational complexity

Geometry and representation theory in computational complexity
计算复杂性中的几何和表示论
批准号:
121425861
负责人:
Professor Dr. Peter Bürgisser
金额:
$0.0万
依托单位:
依托单位国家:
德国
项目类别:
Priority Programmes
财政年份:
2009
资助国家:
德国
项目状态:
已结题
起止时间:
2008-12-31 至 2014-12-31

项目摘要

项目成果

Professor Dr. Peter Bürgisser的其他基金

相似基金

相关文献

中文摘要
翻译
几何复杂性理论是一种利用代数几何和表示理论来证明基本复杂性下界的方法。考虑的最突出的问题是永久与行列式的问题和矩阵乘法的复杂性。值得注意的是,这两个问题都可以重新表述为明确的轨道闭合问题。人们试图通过展示障碍物来分离所考虑的轨道闭包,这些障碍物是发生在一个轨道闭包的坐标环中的不可约表示,而不是在另一个轨道闭包中。几何复杂性计划在过去几年中获得了可见性和动力,正如许多出版物所记载的那样。一些适度的下限已被证明使用这种方法。另一方面,显然需要开发更有力的工具来开展工作。我们希望深化对我们已经开始的尝试的分析,并探索其他途径。
英文摘要
Geometric complexity theory is an approach towards proving fundamental complexity lower bounds by means of algebraic geometry and representation theory. The most prominent questions considered are the permanent versus determinant problem and the complexity of matrix multiplication. It is remarkable that both questions can be restated as explicit orbit closure problems. One tries to separate the orbit closures under consideration by exhibiting obstructions, which are irreducible representations occuring in the coordinate ring of one orbit closure, but not in the other. The geometric complexity program has gained visibility and momentum in the past years, as documented by numerous publications. Some modest lower bounds have been proven using this approach. On the other hand, it has become clear that more powerful tools need to be developed for proceeding. We want to deepen the analyses of our attempts already started and to explore other routes.
期刊论文(0)
专著(0)
科研奖励(0)
会议论文
Geglättete Analyse von Konditionszahlen
  • 批准号:
    40997669
  • 项目类别:
    Research Grants
  • 资助金额:
    $0.0万
  • 财政年份:
    2007
  • 负责人:
    Professor Dr. Peter Bürgisser
  • 依托单位:
Computational complexity, topology, and singularities
  • 批准号:
    5379865
  • 项目类别:
    Research Grants
  • 资助金额:
    $0.0万
  • 财政年份:
    2002
  • 负责人:
    Professor Dr. Peter Bürgisser
  • 依托单位:
国内基金
海外基金
稀疏表示及其在盲源分离中的应用研究
  • 批准号:
    61104053
  • 项目类别:
    青年科学基金项目
  • 资助金额:
    23.0万元
  • 批准年份:
    2011
  • 负责人:
    杨祖元
  • 依托单位:
约化群GL(n, F)的表示--F是非阿基米德局部域
  • 批准号:
    10701034
  • 项目类别:
    青年科学基金项目
  • 资助金额:
    18.0万元
  • 批准年份:
    2007
  • 负责人:
    覃瑜君
  • 依托单位:
信号盲处理的稀疏表示方法
  • 批准号:
    60475004
  • 项目类别:
    面上项目
  • 资助金额:
    23.0万元
  • 批准年份:
    2004
  • 负责人:
    李远清
  • 依托单位: