ALGOUK - A Network for Algorithms and Complexity in the UK

ALGOUK - 英国的算法和复杂性网络

• 批准号: EP/R005613/1
• 负责人: Iain Stewart
• 金额: $ 13.85万
• 依托单位: Durham University
• 依托单位国家: 英国
• 项目类别: Research Grant
• 财政年份: 2017
• 资助国家: 英国
• 起止时间: 2017 至 无数据
• 项目状态: 已结题
• 来源: https://gtr.ukri.org/projects?ref=EP%2FR005613%2F1
• 关键词: ALGOUK; Network; Algorithms; Complexity; UK

The notion of an algorithm is perhaps the key foundational concept in Computer Science, with the measurement of the resources used by algorithms and their implementations, that is, their computational complexity, central to their study and application. As the amount of available data explodes across science, technology, and society, and new potential applications emerge, never has it been so important that research in algorithmics, the science of algorithms, translates into effective implementations and that the weight of algorithmics research is brought to bear on new potential applications. Algorithmics is absolutely central within modern-day Computer Science. Research in algorithmics has two broad strands: obtaining better and better upper bounds as regards the resources used within a solution to a given problem; and proving better and better lower bounds as to the resources required for any such solution. The study of upper bounds obviously translates into practical advances; however, so can the study of lower bounds, and more generally complexity-theoretic (completeness) results, in areas such as cryptography and pseudorandomness. The real-world interface with algorithmics inspires new algorithmic analyses, when, for instance, new problems are thrown up or new practically-imposed restrictions forbid existing methodologies; in addition, complexity-theoretic completeness results for real-world problems inspire the search for new heuristic, randomized, approximate, and fixed-parameter algorithms that translate to effective practical solutions.The study of algorithmics traditionally takes place within Theoretical Computer Science although there are myriad interfaces both within Computer Science and without.However, often deep theoretical insights and advances do not rapidly percolate 'upwards' into real-world implementations and 'sideways' into other academic domains. On the other hand, algorithmic problems emerging within industry, science, and society do not always percolate 'downwards' to the theoreticians who have the tools and techniques to provide improved algorithmic solutions. Moreover, the boundary between Computer Science and other subjects is becoming ever more fluid; for instance, aspects of computation are becoming increasingly embedded in core Mathematics and new algorithmic aspects of topics such as combinatorics, probability, algebra, and topology, are rapidly emerging. In short, there are massive opportunities for research in algorithmics to be transformative across science, technology, and society. The key aim of the AlgoUK network of researchers is to facilitate multi-faceted interactions within the UK's algorithmic research community and also inter-disciplinary interactions between these researchers and those in industry and other subjects such as Mathematics, Biology, and Chemistry. The founding research groups, and hosting sites for the workshops, are at Durham, Kings College London, Leicester, Liverpool, Royal Holloway, and Warwick, but the network is open to all who wish to engage with it.

算法的概念可能是计算机科学中关键的基础概念，对算法及其实现所使用的资源进行测量，即计算复杂性，是算法研究和应用的核心。随着科学、技术和社会中可用数据量的爆炸式增长，以及新的潜在应用的出现，算法研究，算法科学，转化为有效的实现，以及算法研究的重要性被带到新的潜在应用中，这一点从未如此重要。算法绝对是现代计算机科学的核心。算法的研究有两大方面：在给定问题的解决方案中获得越来越好的资源上限；并且越来越好地证明了解所需资源的下界。上界的研究显然转化为实际的进步；然而，在密码学和伪随机等领域，下界和更一般的复杂性理论（完备性）结果的研究也是如此。现实世界与算法的界面激发了新的算法分析，例如，当新的问题被抛出或新的实际强加的限制禁止现有的方法；此外，现实世界问题的复杂性理论完备性结果激发了对新的启发式、随机化、近似和固定参数算法的探索，这些算法可以转化为有效的实际解决方案。算法的研究传统上是在理论计算机科学中进行的，尽管在计算机科学内部和外部都有无数的接口。然而，深刻的理论见解和进步往往不会迅速“向上”渗透到现实世界的实施中，也不会“横向”渗透到其他学术领域。另一方面，在工业、科学和社会中出现的算法问题并不总是“向下”渗透到拥有提供改进算法解决方案的工具和技术的理论家那里。此外，计算机科学与其他学科之间的界限正变得越来越模糊；例如，计算的各个方面正越来越多地嵌入核心数学，新的算法方面的主题，如组合学、概率论、代数和拓扑学，正在迅速出现。简而言之，算法研究在科学、技术和社会领域都有巨大的变革机会。AlgoUK研究人员网络的主要目标是促进英国算法研究界的多方面互动，以及这些研究人员与工业和其他学科（如数学、生物和化学）的跨学科互动。这些研讨会的创始研究小组和主办地点分别位于达勒姆、伦敦国王学院、莱斯特、利物浦、皇家霍洛威和沃里克，但该网络对所有希望参与其中的人开放。

项目成果

Temporal flows in temporal networks

• DOI: 10.1016/j.jcss.2019.02.003
• 发表时间: 2019-08-01
• 期刊: JOURNAL OF COMPUTER AND SYSTEM SCIENCES
• 影响因子: 1.1
• 作者: Akrida, Eleni C.;Czyzowicz, Jurek;Spirakis, Paul G.
• 通讯作者: Spirakis, Paul G.

On the Hardness of Energy Minimisation for Crystal Structure Prediction*

关于晶体结构预测的能量最小化的难度*

• DOI: 10.3233/fi-2021-2096
• 发表时间: 2022
• 期刊: Fundamenta Informaticae
• 影响因子: 0.8
• 作者: Adamson D

The temporal explorer who returns to the base

返回基地的时空探索者

• DOI: 10.1016/j.jcss.2021.04.001
• 发表时间: 2021
• 期刊: Journal of Computer and System Sciences
• 影响因子: 1.1
• 作者: Akrida E

How fast can we reach a target vertex in stochastic temporal graphs?

我们能够以多快的速度到达随机时间图中的目标顶点？

• DOI: 10.1016/j.jcss.2020.05.005
• 发表时间: 2020
• 期刊: Journal of Computer and System Sciences
• 影响因子: 1.1
• 作者: Akrida E