Power and Limitations of Conceptually Simple Algorithms

概念简单算法的威力和局限性

基本信息

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

项目摘要

Theoretical computer science has been hugely successful in terms of both design of new efficient and practical algorithms, as well as analysis and explanation of performance of existing algorithms. Yet, the gap between "theory" and "practice" remains. One of the most common criticisms is that worst-case analysis is often too pessimistic to reflect "practice". Prime examples of this phenomenon are linear programming and satisfiability problems. Another criticism is that negative results are often based on assumptions. Sometimes these assumptions are quite reasonable, such as P not equal to NP, but other times these assumptions are more controversial, such as strong exponential time hypothesis. Yet another criticism is that computational models might lack some practical features, e.g., extra side information that might be available to an algorithm. Side-information is often modelled in theory by an all-powerful oracle, where the "all-powerful" part is not very realistic. While there is no single "silver bullet" model that addresses all these concerns, there are many success stories in attempts to bridge practice and theory. This research program falls under this umbrella of trying to reduce the gap between theory and practice as it pertains to conceptually simple algorithms. Conceptually simple algorithms have many properties that make them desirable in practice, but they are hard to analyze. Part of the problem is that usually simple algorithms have bad worst-case behavior, but excellent empirical performance. An analysis consistent with such reality has to accurately model practical instances, which already is a very difficult task. Another problem is that the notion of simplicity is not well-defined. This makes negative answers to questions of the form "can this problem be solved by a simple algorithm?" impossible. The long-term goal of this project is to develop a formal theory of simple algorithms that would address the three criticisms mentioned above. Short-term goals consist of practical input modelling, algorithmic modelling with information-theoretic bottlenecks, and evaluation of conceptually simple algorithms for specific problems within various application domains, such as online advertising, scheduling, packing, and optimization.*****
理论计算机科学在设计新的高效和实用的算法以及分析和解释现有算法的性能方面取得了巨大的成功。然而,“理论”与“实践”之间的差距仍然存在。最常见的批评之一是,最坏情况分析往往过于悲观,无法反映“实践”。这种现象的主要例子是线性规划和可满足性问题。另一种批评是,负面结果往往是基于假设。有时这些假设是相当合理的,比如P不等于NP,但有时这些假设更具争议性,比如强指数时间假设。然而,另一个批评是,计算模型可能缺乏一些实用的特征,例如,可能对算法可用的额外的附加信息。侧面信息通常在理论上由全能的神谕建模,其中“全能”的部分并不十分现实。虽然没有单一的“银弹”模型可以解决所有这些问题,但在尝试将实践和理论联系起来方面,有许多成功的故事。这个研究项目属于这个伞下,试图减少理论和实践之间的差距,因为它涉及到概念上简单的算法。概念上简单的算法有许多特性,使它们在实践中是可取的,但它们很难分析。部分问题在于,通常简单的算法有糟糕的最坏情况,但却有出色的经验表现。与这种现实相一致的分析必须准确地模拟实际情况,这已经是一项非常困难的任务。另一个问题是简单性的概念没有明确定义。这使得“这个问题可以用一个简单的算法来解决吗?”这种形式的否定答案变得不可能。该项目的长期目标是开发一种简单算法的正式理论,以解决上面提到的三个批评。短期目标包括实际输入建模、具有信息论瓶颈的算法建模,以及对各种应用领域(如在线广告、调度、打包和优化)中特定问题的概念简单算法的评估。*****

项目成果

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

Pankratov, Denis其他文献

Low-Temperature Treatment of Boehmitic Bauxite Using the Bayer Reductive Method with the Formation of High-Iron Magnetite Concentrate.
  • DOI:
    10.3390/ma16134678
  • 发表时间:
    2023-06-28
  • 期刊:
  • 影响因子:
    3.4
  • 作者:
    Shoppert, Andrei;Valeev, Dmitry;Loginova, Irina;Pankratov, Denis
  • 通讯作者:
    Pankratov, Denis
Stabbing Planes
刺击飞机
  • DOI:
    10.48550/arxiv.1710.03219
  • 发表时间:
    2022
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Beame, Paul;Fleming, Noah;Impagliazzo, Russell;Pankratov, Denis;Pitassi, Toniann;Robere, Robert
  • 通讯作者:
    Robere, Robert

Pankratov, Denis的其他文献

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

{{ truncateString('Pankratov, Denis', 18)}}的其他基金

Power and Limitations of Conceptually Simple Algorithms
概念简单算法的威力和局限性
  • 批准号:
    RGPIN-2019-06971
  • 财政年份:
    2022
  • 资助金额:
    $ 2.4万
  • 项目类别:
    Discovery Grants Program - Individual
Power and Limitations of Conceptually Simple Algorithms
概念简单算法的威力和局限性
  • 批准号:
    RGPIN-2019-06971
  • 财政年份:
    2021
  • 资助金额:
    $ 2.4万
  • 项目类别:
    Discovery Grants Program - Individual
Power and Limitations of Conceptually Simple Algorithms
概念简单算法的威力和局限性
  • 批准号:
    RGPIN-2019-06971
  • 财政年份:
    2020
  • 资助金额:
    $ 2.4万
  • 项目类别:
    Discovery Grants Program - Individual
Power and Limitations of Conceptually Simple Algorithms
概念简单算法的威力和局限性
  • 批准号:
    DGECR-2019-00335
  • 财政年份:
    2019
  • 资助金额:
    $ 2.4万
  • 项目类别:
    Discovery Launch Supplement
Information Complexity Theory
信息复杂性理论
  • 批准号:
    471780-2015
  • 财政年份:
    2017
  • 资助金额:
    $ 2.4万
  • 项目类别:
    Postdoctoral Fellowships
Information Complexity Theory
信息复杂性理论
  • 批准号:
    471780-2015
  • 财政年份:
    2016
  • 资助金额:
    $ 2.4万
  • 项目类别:
    Postdoctoral Fellowships
Information Complexity Theory
信息复杂性理论
  • 批准号:
    471780-2015
  • 财政年份:
    2015
  • 资助金额:
    $ 2.4万
  • 项目类别:
    Postdoctoral Fellowships
The power and limitations of practical algorithms
实用算法的力量和局限性
  • 批准号:
    376986-2009
  • 财政年份:
    2009
  • 资助金额:
    $ 2.4万
  • 项目类别:
    Postgraduate Scholarships - Master's
The power of local search
本地搜索的力量
  • 批准号:
    366610-2008
  • 财政年份:
    2008
  • 资助金额:
    $ 2.4万
  • 项目类别:
    University Undergraduate Student Research Awards

相似海外基金

Collaborative Research: Prospects and limitations of predicting a potential collapse of the Atlantic meridional overturning circulation
合作研究:预测大西洋经向翻转环流潜在崩溃的前景和局限性
  • 批准号:
    2343204
  • 财政年份:
    2024
  • 资助金额:
    $ 2.4万
  • 项目类别:
    Standard Grant
Collaborative Research: Prospects and limitations of predicting a potential collapse of the Atlantic meridional overturning circulation
合作研究:预测大西洋经向翻转环流潜在崩溃的前景和局限性
  • 批准号:
    2343203
  • 财政年份:
    2024
  • 资助金额:
    $ 2.4万
  • 项目类别:
    Standard Grant
Collaborative Research: SaTC: CORE: Small: Understanding the Limitations of Wireless Network Security Designs Leveraging Wireless Properties: New Threats and Defenses in Practice
协作研究:SaTC:核心:小型:了解利用无线特性的无线网络安全设计的局限性:实践中的新威胁和防御
  • 批准号:
    2316720
  • 财政年份:
    2023
  • 资助金额:
    $ 2.4万
  • 项目类别:
    Standard Grant
Targeting breathing limitations to improve functional outcomes in HFpEF
针对呼吸限制以改善 HFpEF 的功能结果
  • 批准号:
    10663768
  • 财政年份:
    2023
  • 资助金额:
    $ 2.4万
  • 项目类别:
AF:Small: Algorithms and Limitations for Matrix Multiplication
AF:Small:矩阵乘法的算法和限制
  • 批准号:
    2330048
  • 财政年份:
    2023
  • 资助金额:
    $ 2.4万
  • 项目类别:
    Standard Grant
Applying an equity lens to the design and conduct of a virtual exercise program for older adults with mobility limitations
应用公平视角为行动不便的老年人设计和实施虚拟锻炼计划
  • 批准号:
    497446
  • 财政年份:
    2023
  • 资助金额:
    $ 2.4万
  • 项目类别:
An empirical study on the reality and limitations of university-citizen reciprocity in civic engagement in university education
大学教育公民参与中大学与公民互惠的现实与局限性的实证研究
  • 批准号:
    23K18900
  • 财政年份:
    2023
  • 资助金额:
    $ 2.4万
  • 项目类别:
    Grant-in-Aid for Research Activity Start-up
Community reentry for older adults leaving prison with and without health limitations
有或没有健康限制的出狱老年人重返社区
  • 批准号:
    10741029
  • 财政年份:
    2023
  • 资助金额:
    $ 2.4万
  • 项目类别:
Collaborative Research: SaTC: CORE: Small: Understanding the Limitations of Wireless Network Security Designs Leveraging Wireless Properties: New Threats and Defenses in Practice
协作研究:SaTC:核心:小型:了解利用无线特性的无线网络安全设计的局限性:实践中的新威胁和防御
  • 批准号:
    2316719
  • 财政年份:
    2023
  • 资助金额:
    $ 2.4万
  • 项目类别:
    Standard Grant
Peripheral Limitations in Pulmonary Hypertension and Effects of Muscle Training
肺动脉高压的外周局限性和肌肉训练的影响
  • 批准号:
    10661187
  • 财政年份:
    2023
  • 资助金额:
    $ 2.4万
  • 项目类别:
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了