Theoretical foundation of sublinear-time algorithms

亚线性时间算法的理论基础

基本信息

  • 批准号:
    RGPIN-2015-03907
  • 负责人:
  • 金额:
    $ 2.48万
  • 依托单位:
  • 依托单位国家:
    加拿大
  • 项目类别:
    Discovery Grants Program - Individual
  • 财政年份:
    2016
  • 资助国家:
    加拿大
  • 起止时间:
    2016-01-01 至 2017-12-31
  • 项目状态:
    已结题

项目摘要

Many areas of science are currently undergoing a dramatic transformation: with rapid advances in data collection technologies, molecular biologists can now measure the level of expression of every gene in a cell; physicists can now record the details of collisions of subatomic particles; astronomers can now obtain detailed pictures of the farthest reaches of the universe; etc. The rich datasets that can now be collected offer many exciting scientific opportunities, but they also introduce significant new computational challenges. Sublinear-time algorithms are one of the powerful tools that will help us meet these challenges. A sublinear-time algorithm is an algorithm that produces its output after inspecting only a tiny fraction of its input and executing a number of computational steps that is asymptotically smaller than the size of the input. The research described in this proposal aims to provide a solid theoretical foundation for the development and the analysis of these algorithms. This will be done by developing new algorithmic techniques for designing sublinear-time algorithms, new mathematical tools to analyze these algorithms and establish their limitations, and new connections to other areas of theoretical computer science.
许多科学领域目前正在发生巨大的变化:随着数据收集技术的迅速发展,分子生物学家现在可以测量细胞中每一个基因的表达水平;物理学家现在可以记录亚原子粒子碰撞的细节;天文学家现在可以获得宇宙最远处的详细照片;现在可以收集的丰富的数据集提供了许多令人兴奋的科学机会,但它们也引入了重大的新的计算挑战。次线性时间算法是帮助我们应对这些挑战的强大工具之一。亚线性时间算法是指只需要检测输入的一小部分,并执行一系列渐近小于输入的计算步骤就能产生输出的算法,本文的研究旨在为这些算法的开发和分析提供坚实的理论基础。这将通过开发新的算法技术来设计次线性时间算法,新的数学工具来分析这些算法并确定其局限性,以及与理论计算机科学其他领域的新联系来实现。

项目成果

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

Blais, Eric其他文献

Blais, Eric的其他文献

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

{{ truncateString('Blais, Eric', 18)}}的其他基金

New Methods for the Analysis of Randomized Algorithms
随机算法分析的新方法
  • 批准号:
    RGPIN-2022-03329
  • 财政年份:
    2022
  • 资助金额:
    $ 2.48万
  • 项目类别:
    Discovery Grants Program - Individual
Theoretical foundation of sublinear-time algorithms
亚线性时间算法的理论基础
  • 批准号:
    RGPIN-2015-03907
  • 财政年份:
    2021
  • 资助金额:
    $ 2.48万
  • 项目类别:
    Discovery Grants Program - Individual
Theoretical foundation of sublinear-time algorithms
亚线性时间算法的理论基础
  • 批准号:
    RGPIN-2015-03907
  • 财政年份:
    2020
  • 资助金额:
    $ 2.48万
  • 项目类别:
    Discovery Grants Program - Individual
Theoretical foundation of sublinear-time algorithms
亚线性时间算法的理论基础
  • 批准号:
    RGPIN-2015-03907
  • 财政年份:
    2019
  • 资助金额:
    $ 2.48万
  • 项目类别:
    Discovery Grants Program - Individual
Theoretical foundation of sublinear-time algorithms
亚线性时间算法的理论基础
  • 批准号:
    RGPIN-2015-03907
  • 财政年份:
    2018
  • 资助金额:
    $ 2.48万
  • 项目类别:
    Discovery Grants Program - Individual
Theoretical foundation of sublinear-time algorithms
亚线性时间算法的理论基础
  • 批准号:
    RGPIN-2015-03907
  • 财政年份:
    2017
  • 资助金额:
    $ 2.48万
  • 项目类别:
    Discovery Grants Program - Individual
Theoretical foundation of sublinear-time algorithms
亚线性时间算法的理论基础
  • 批准号:
    RGPIN-2015-03907
  • 财政年份:
    2015
  • 资助金额:
    $ 2.48万
  • 项目类别:
    Discovery Grants Program - Individual
Using white dwarf merger simulations and observations of double degenerates to verify sub-Chandrasekhar SNIa models and explain new transients
使用白矮星合并模拟和双简并观测来验证亚钱德拉塞卡 SNIa 模型并解释新的瞬变
  • 批准号:
    425794-2012
  • 财政年份:
    2012
  • 资助金额:
    $ 2.48万
  • 项目类别:
    Alexander Graham Bell Canada Graduate Scholarships - Doctoral
Investigation of close binary white dwarfs as Type Ia supernovae progenitors
研究作为 Ia 型超新星前身的紧密双星白矮星
  • 批准号:
    411278-2011
  • 财政年份:
    2011
  • 资助金额:
    $ 2.48万
  • 项目类别:
    Alexander Graham Bell Canada Graduate Scholarships - Master's
Population synthesis studies of double degenerate systems
双简并系统的种群合成研究
  • 批准号:
    398611-2010
  • 财政年份:
    2010
  • 资助金额:
    $ 2.48万
  • 项目类别:
    University Undergraduate Student Research Awards

相似海外基金

2024 - 2025 National Science Foundation (NSF) Computer and Information Science and Engineering (CISE) Research Experiences for Undergraduates (REU) Principal Investigator Workshops
2024 - 2025 美国国家科学基金会 (NSF) 计算机与信息科学与工程 (CISE) 本科生研究经验 (REU) 首席研究员研讨会
  • 批准号:
    2407231
  • 财政年份:
    2024
  • 资助金额:
    $ 2.48万
  • 项目类别:
    Continuing Grant
What Works Policy Fellowship - Youth Futures Foundation Understanding What Makes for Quality Work Fellowship UKRI Policy Fellowship
什么有效的政策奖学金 - 青年未来基金会 了解什么是高质量工作奖学金 UKRI 政策奖学金
  • 批准号:
    ES/Y005007/1
  • 财政年份:
    2024
  • 资助金额:
    $ 2.48万
  • 项目类别:
    Fellowship
Aston University and Aston Villa Foundation KTP23_24R3
阿斯顿大学和阿斯顿维拉基金会 KTP23_24R3
  • 批准号:
    10084135
  • 财政年份:
    2024
  • 资助金额:
    $ 2.48万
  • 项目类别:
    Knowledge Transfer Network
Open Access Block Award 2024 - Kings College Hospital NHS Foundation Trust
2024 年开放访问区块奖 - 国王学院医院 NHS 基金会信托
  • 批准号:
    EP/Z532940/1
  • 财政年份:
    2024
  • 资助金额:
    $ 2.48万
  • 项目类别:
    Research Grant
Conference: A Virtual Workshop for Two-Year College Geoscience Faculty to Develop National Science Foundation Grant Proposals
会议:两年制大学地球科学教师制定国家科学基金会拨款提案的虚拟研讨会
  • 批准号:
    2349758
  • 财政年份:
    2024
  • 资助金额:
    $ 2.48万
  • 项目类别:
    Standard Grant
Manchester Metropolitan University and Northern Care Alliance NHS Foundation Trust KTP 23_24 R2
曼彻斯特城市大学和北方护理联盟 NHS 基金会信托 KTP 23_24 R2
  • 批准号:
    10076811
  • 财政年份:
    2024
  • 资助金额:
    $ 2.48万
  • 项目类别:
    Knowledge Transfer Partnership
FMSG: Cyber: Learning Foundation Models for Manufacturing Design Automation
FMSG:网络:制造设计自动化的学习基础模型
  • 批准号:
    2328032
  • 财政年份:
    2024
  • 资助金额:
    $ 2.48万
  • 项目类别:
    Standard Grant
SBIR Phase I: An Artificial Intelligence System to Accelerate Semiconductor Production using Physics-embedded Lithographic Foundation Model
SBIR 第一阶段:使用物理嵌入式光刻基础模型加速半导体生产的人工智能系统
  • 批准号:
    2336079
  • 财政年份:
    2024
  • 资助金额:
    $ 2.48万
  • 项目类别:
    Standard Grant
Construction of Integrated Story Foundation Dataset for Automatic Generation Using Hierarchical Structure
利用层次结构自动生成集成故事基础数据集的构建
  • 批准号:
    23K11772
  • 财政年份:
    2023
  • 资助金额:
    $ 2.48万
  • 项目类别:
    Grant-in-Aid for Scientific Research (C)
Construction of Personalized and Decentralized Oriented Sightseeing Recommendation and Planning Foundation
个性化、去中心化的旅游推荐与规划基础建设
  • 批准号:
    23H03404
  • 财政年份:
    2023
  • 资助金额:
    $ 2.48万
  • 项目类别:
    Grant-in-Aid for Scientific Research (B)
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了