Algorithms in Finite Groups
有限群算法
基本信息
- 批准号:9732205
- 负责人:
- 金额:$ 20.56万
- 依托单位:
- 依托单位国家:美国
- 项目类别:Standard Grant
- 财政年份:1998
- 资助国家:美国
- 起止时间:1998-08-01 至 2002-07-31
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
This project investigates the design and analysis of asymptotically efficient algorithms for finite matrix groups. While three decades of work in computational group theory have resulted in a thorough understanding, both theoretical and practical, of many algorithmic aspects of permutation groups, virtually no efficient algorithms have been designed until recently in the potentially more important domain of matrix groups. This latter area, however, is currently experiencing explosive growth. This research focuses on theoretical aspects and polynomial time algorithms. Past experience shows that this approach has the potential of yielding important insights which may lead to efficient implementations. Indeed, algorithms inspired by the polynomial-time paradigm have made their way into the widely used group theory package GAP. The main objective is to map out the normal structure of a matrix group given by a list of generators. Components of this project include a number of problems to be handled in the more general context of "black-box groups" (the group operations are performed by a "black box"). A key ingredient is the black-box recognition of finite simple groups. Another component consists in "getting past" a simple top quotient. The methods include the statistical analysis of number theoretic properties of the orders of elements in finite simple groups (based on the classification of finite simple groups). One of the main obstacles seems to require the study of modular representations of simple groups. Combinatorial methods seem to be called for in the analysis of random sampling heuristics which are required for most existing matrix group algorithms.
本计画研究有限矩阵群之渐近有效演算法之设计与分析。 虽然三十年的工作在计算群论已经导致了一个彻底的理解,理论和实践,许多算法方面的置换群,几乎没有有效的算法已经设计,直到最近在潜在的更重要的领域矩阵群。然而,后一个领域目前正在经历爆炸性增长。 本研究的重点是理论方面和多项式时间算法。 过去的经验表明,这种方法有可能产生重要的见解,可能导致有效的实施。 事实上,受多项式时间范式启发的算法已经进入了广泛使用的群论软件包GAP。 主要目的是映射出由生成元列表给出的矩阵群的正规结构。这个项目的组成部分包括一些问题,需要在更一般的“黑盒组”(组操作由“黑盒”执行)的上下文中处理。一个关键的组成部分是黑盒识别有限简单的群体。另一个组成部分是“越过”一个简单的顶商。 方法包括有限单群中元素阶的数论性质的统计分析(基于有限单群的分类)。 其中一个主要的障碍似乎需要研究简单群的模表示。在分析随机抽样算法时,似乎需要组合方法,这是大多数现有矩阵组算法所必需的。
项目成果
期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
数据更新时间:{{ journalArticles.updateTime }}
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
数据更新时间:{{ journalArticles.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ monograph.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ sciAawards.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ patent.updateTime }}
Laszlo Babai其他文献
Laszlo Babai的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Laszlo Babai', 18)}}的其他基金
AF: Small: Symmetry and regularity in the theory of computing
AF:小:计算理论中的对称性和规律性
- 批准号:
1718902 - 财政年份:2017
- 资助金额:
$ 20.56万 - 项目类别:
Standard Grant
AF: Small: Group theory and combinatorial structures in computer science
AF:小:计算机科学中的群论和组合结构
- 批准号:
1423309 - 财政年份:2014
- 资助金额:
$ 20.56万 - 项目类别:
Standard Grant
AF: Small: Collaborative Research: Groups in Computer Science
AF:小型:协作研究:计算机科学小组
- 批准号:
1017781 - 财政年份:2010
- 资助金额:
$ 20.56万 - 项目类别:
Standard Grant
Collaborative Research: Groups in Computer Science
合作研究:计算机科学小组
- 批准号:
0830370 - 财政年份:2008
- 资助金额:
$ 20.56万 - 项目类别:
Standard Grant
Randomized Complexity Classes and Complexity in Finite Groups
随机复杂性类和有限群中的复杂性
- 批准号:
9014562 - 财政年份:1991
- 资助金额:
$ 20.56万 - 项目类别:
Continuing Grant
相似国自然基金
Finite-time Lyapunov 函数和耦合系统的稳定性分析
- 批准号:11701533
- 批准年份:2017
- 资助金额:22.0 万元
- 项目类别:青年科学基金项目
相似海外基金
Brauer groups and Neron Severi groups of surfaces over finite fields
有限域上的表面布劳尔群和 Neron Severi 群
- 批准号:
23K25768 - 财政年份:2024
- 资助金额:
$ 20.56万 - 项目类别:
Grant-in-Aid for Scientific Research (B)
Calculating the Essential p-Dimension of the Finite Simple Groups
计算有限单群的本质 p 维数
- 批准号:
2302822 - 财政年份:2023
- 资助金额:
$ 20.56万 - 项目类别:
Fellowship Award
Brauer groups and Neron Severi groups of surfaces over finite fields
有限域上的表面布劳尔群和 Neron Severi 群
- 批准号:
23H01071 - 财政年份:2023
- 资助金额:
$ 20.56万 - 项目类别:
Grant-in-Aid for Scientific Research (B)
Invariable generation in finite groups with applications to algorithmic number theory
有限群中的不变生成及其在算法数论中的应用
- 批准号:
EP/T017619/3 - 财政年份:2022
- 资助金额:
$ 20.56万 - 项目类别:
Fellowship
Representations of Finite Groups and Applications
有限群的表示及其应用
- 批准号:
2200850 - 财政年份:2022
- 资助金额:
$ 20.56万 - 项目类别:
Continuing Grant
Representations of finite reductive groups, character sheaves and theory of total positivity
有限约简群的表示、特征轮和总正性理论
- 批准号:
2153741 - 财政年份:2022
- 资助金额:
$ 20.56万 - 项目类别:
Standard Grant
Canonical dimension and actions of finite groups on algebraic varieties
代数簇上有限群的规范维数和作用
- 批准号:
498240045 - 财政年份:2022
- 资助金额:
$ 20.56万 - 项目类别:
Heisenberg Grants
Classification of Finite Simple Groups. Groups of even type of medium size.
有限简单群的分类。
- 批准号:
EP/V05547X/1 - 财政年份:2022
- 资助金额:
$ 20.56万 - 项目类别:
Fellowship
MPS-Ascend: Representation Theory of General Linear Groups over Finite Local Principal Ideal Rings
MPS-Ascend:有限局部主理想环上的一般线性群表示论
- 批准号:
2213166 - 财政年份:2022
- 资助金额:
$ 20.56万 - 项目类别:
Fellowship Award
Invariable generation in finite groups with applications to algorithmic number theory
有限群中的不变生成及其在算法数论中的应用
- 批准号:
EP/T017619/2 - 财政年份:2021
- 资助金额:
$ 20.56万 - 项目类别:
Fellowship