Collaborative Research: Theoretical and experimental approaches to search problems in group theory

协作研究:群论中搜索问题的理论和实验方法

基本信息

  • 批准号:
    0914778
  • 负责人:
  • 金额:
    $ 7.35万
  • 依托单位:
  • 依托单位国家:
    美国
  • 项目类别:
    Standard Grant
  • 财政年份:
    2009
  • 资助国家:
    美国
  • 起止时间:
    2009-09-15 至 2012-08-31
  • 项目状态:
    已结题

项目摘要

The objective of this proposal is to address various search problems in group theory. Decision problems in group theory have been studied for over 100 years now, since Dehn put forward, in the beginning of the 20th century, the three famous decision problems now often referred to as Dehn's problems: the word problem, the conjugacy problem, and the isomorphism problem. In general, decision problems are problems of the following nature: given a property P and an input O, find out whether or not the input O has the property P. On the other hand, search problems are of the following nature: given a property P and an input O with the property P, find a proof (sometimes called a "witness") of the fact that O has the property P. This is a substantial shift of paradigm, and in fact, studying search problems often gives rise to new research avenues in mathematics or computer science, very different from those prompted by addressing the corresponding decision problems.The potential broader impacts of the proposed research are extensive; the impact on the general area of information security can be singled out. The difficulty of several well-studied problems, e.g. integer factorization and the discrete logarithm problem underlie most current public-key cryptographic protocols used in real-life applications. Developing public-key protocols based upon other search problems, e.g. the conjugacy search problem whose difficulty has been well studied by group theorists, is prudent from the standpoint of robustness, particularly if factorization or related developments threaten the security of current protocols. The complexity of non-abelian infinite groups is a promising fertile ground for new protocols and there is a great deal of preliminary work required such as that proposed here.
这个建议的目的是解决各种搜索问题的群论。自Dehn在世纪初提出三个著名的决策问题--字问题、共轭问题和同构问题以来,群论中的决策问题的研究已有100多年的历史。一般来说,决策问题是具有以下性质的问题:给定一个属性P和一个输入O,找出输入O是否具有属性P。给定属性P和具有属性P的输入O,找到证据(有时称为“见证”)O具有属性P的事实。这是范式的实质性转变,事实上,对搜索问题的研究通常会在数学或计算机科学中产生新的研究途径,与解决相应的决策问题所产生的研究途径截然不同。2所提出的研究的潜在影响是广泛的; 3对信息安全的一般领域的影响可以单独列出。一些研究得很好的问题,如整数分解和离散对数问题的困难是当前大多数公钥密码协议在现实生活中使用的基础。 从鲁棒性的角度来看,基于其他搜索问题(例如,群论学家已经充分研究了其难度的共轭搜索问题)开发公钥协议是谨慎的,特别是如果因子分解或相关发展威胁到当前协议的安全性。非阿贝尔无限群的复杂性是一个有前途的肥沃土壤,新的协议,有大量的前期工作需要,如这里提出的。

项目成果

期刊论文数量(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 }}

Vladimir Shpilrain其他文献

Generalized primitive elements of a free group
  • DOI:
    10.1007/s000130050264
  • 发表时间:
    1998-10-01
  • 期刊:
  • 影响因子:
    0.500
  • 作者:
    Vladimir Shpilrain
  • 通讯作者:
    Vladimir Shpilrain
On Lie Algebras with Wild Automorphisms
  • DOI:
    10.1007/bf03322253
  • 发表时间:
    2013-04-17
  • 期刊:
  • 影响因子:
    1.200
  • 作者:
    Yuri Bahturin;Vladimir Shpilrain
  • 通讯作者:
    Vladimir Shpilrain
Recognizing automorphisms of the free groups
  • DOI:
    10.1007/bf01196426
  • 发表时间:
    1994-05-01
  • 期刊:
  • 影响因子:
    0.500
  • 作者:
    Vladimir Shpilrain
  • 通讯作者:
    Vladimir Shpilrain
On monomorphisms of free groups
  • DOI:
    10.1007/bf01195127
  • 发表时间:
    1995-06-01
  • 期刊:
  • 影响因子:
    0.500
  • 作者:
    Vladimir Shpilrain
  • 通讯作者:
    Vladimir Shpilrain
Linear average-case complexity of algorithmic problems in groups
群中算法问题的线性平均情况复杂度
  • DOI:
    10.1016/j.jalgebra.2025.01.013
  • 发表时间:
    2025-04-15
  • 期刊:
  • 影响因子:
    0.800
  • 作者:
    Alexander Olshanskii;Vladimir Shpilrain
  • 通讯作者:
    Vladimir Shpilrain

Vladimir Shpilrain的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

{{ truncateString('Vladimir Shpilrain', 18)}}的其他基金

International Conference on Geometric and Asymptotic Group Theory with Applications
几何和渐近群理论及其应用国际会议
  • 批准号:
    1928295
  • 财政年份:
    2019
  • 资助金额:
    $ 7.35万
  • 项目类别:
    Standard Grant
Conference: Geometric and Asymptotic Group Theory with Applications, September 15-19, New York, NY
会议:几何和渐近群理论及其应用,9 月 15 日至 19 日,纽约州纽约
  • 批准号:
    0805552
  • 财政年份:
    2008
  • 资助金额:
    $ 7.35万
  • 项目类别:
    Standard Grant
Conference: Geometric and Asymptotic Group Theory with Applications
会议:几何和渐近群理论及其应用
  • 批准号:
    0613035
  • 财政年份:
    2006
  • 资助金额:
    $ 7.35万
  • 项目类别:
    Standard Grant
Collaborative Research: Generic Properties of Groups, Geometric Invariants and Algorithms
协作研究:群的泛性、几何不变量和算法
  • 批准号:
    0405105
  • 财政年份:
    2004
  • 资助金额:
    $ 7.35万
  • 项目类别:
    Standard Grant

相似国自然基金

Research on Quantum Field Theory without a Lagrangian Description
  • 批准号:
    24ZR1403900
  • 批准年份:
    2024
  • 资助金额:
    0.0 万元
  • 项目类别:
    省市级项目
Cell Research
  • 批准号:
    31224802
  • 批准年份:
    2012
  • 资助金额:
    24.0 万元
  • 项目类别:
    专项基金项目
Cell Research
  • 批准号:
    31024804
  • 批准年份:
    2010
  • 资助金额:
    24.0 万元
  • 项目类别:
    专项基金项目
Cell Research (细胞研究)
  • 批准号:
    30824808
  • 批准年份:
    2008
  • 资助金额:
    24.0 万元
  • 项目类别:
    专项基金项目
Research on the Rapid Growth Mechanism of KDP Crystal
  • 批准号:
    10774081
  • 批准年份:
    2007
  • 资助金额:
    45.0 万元
  • 项目类别:
    面上项目

相似海外基金

Collaborative Research: Aeolian Grain Entrainment Over Flexible Vegetation Canopies: Theoretical Models, Laboratory Experiments and Fieldwork
合作研究:灵活植被冠层的风沙颗粒夹带:理论模型、实验室实验和实地考察
  • 批准号:
    2327916
  • 财政年份:
    2023
  • 资助金额:
    $ 7.35万
  • 项目类别:
    Continuing Grant
Collaborative Research: FET: Small: Theoretical Foundations of Quantum Pseudorandom Primitives
合作研究:FET:小型:量子伪随机原语的理论基础
  • 批准号:
    2329938
  • 财政年份:
    2023
  • 资助金额:
    $ 7.35万
  • 项目类别:
    Standard Grant
Collaborative Research: SHINE: Observational and Theoretical Studies of the Parametric Decay Instability in the Lower Solar Atmosphere
合作研究:SHINE:太阳低层大气参数衰变不稳定性的观测和理论研究
  • 批准号:
    2229101
  • 财政年份:
    2023
  • 资助金额:
    $ 7.35万
  • 项目类别:
    Standard Grant
Collaborative Research: A Simulation and Theoretical Analysis of Meteor Evolution over Scales Ranging from Sub-microseconds to Minutes
合作研究:亚微秒到分钟尺度的流星演化模拟与理论分析
  • 批准号:
    2301644
  • 财政年份:
    2023
  • 资助金额:
    $ 7.35万
  • 项目类别:
    Standard Grant
Collaborative Research: AF: SaTC: Medium: Theoretical Foundations of Lattice-Based Cryptography
合作研究:AF:SaTC:媒介:基于格的密码学的理论基础
  • 批准号:
    2312296
  • 财政年份:
    2023
  • 资助金额:
    $ 7.35万
  • 项目类别:
    Continuing Grant
Collaborative Research: A Comprehensive Theoretical Study of Cosmological Magnetic Fields and Turbulence: from the Early to Late Time Universe
合作研究:宇宙磁场和湍流的综合理论研究:从宇宙早期到晚期
  • 批准号:
    2307699
  • 财政年份:
    2023
  • 资助金额:
    $ 7.35万
  • 项目类别:
    Standard Grant
Collaborative Research: A Comprehensive Theoretical Study of Cosmological Magnetic Fields and Turbulence: from the Early to Late Time Universe
合作研究:宇宙磁场和湍流的综合理论研究:从宇宙早期到晚期
  • 批准号:
    2307698
  • 财政年份:
    2023
  • 资助金额:
    $ 7.35万
  • 项目类别:
    Standard Grant
NSF-BSF: Collaborative Research: CIF: Small: Neural Estimation of Statistical Divergences: Theoretical Foundations and Applications to Communication Systems
NSF-BSF:协作研究:CIF:小型:统计差异的神经估计:通信系统的理论基础和应用
  • 批准号:
    2308445
  • 财政年份:
    2023
  • 资助金额:
    $ 7.35万
  • 项目类别:
    Standard Grant
Collaborative Research: FET: Small: Theoretical Foundations of Quantum Pseudorandom Primitives
合作研究:FET:小型:量子伪随机原语的理论基础
  • 批准号:
    2329939
  • 财政年份:
    2023
  • 资助金额:
    $ 7.35万
  • 项目类别:
    Standard Grant
Collaborative Research: SHINE: Observational and Theoretical Studies of the Parametric Decay Instability in the Lower Solar Atmosphere
合作研究:SHINE:太阳低层大气参数衰变不稳定性的观测和理论研究
  • 批准号:
    2229100
  • 财政年份:
    2023
  • 资助金额:
    $ 7.35万
  • 项目类别:
    Standard Grant
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了