AF: Small: Communication and Resource Tradeoffs
AF: Small: Communication and Resource Tradeoffs
批准号:
1524246
负责人:
Paul Beame
金额:
$40.0万
依托单位:
依托单位国家:
美国
项目类别:
Standard Grant
财政年份:
2015
资助国家:
美国
项目状态:
已结题
起止时间:
2015-08-15 至 2019-07-31
中文摘要
这个项目将专注于计算复杂性中的几个问题,涉及计算资源之间的权衡。其中包括在大规模并行系统上进行数据分析所需的通信负载、处理器和通信轮次之间的权衡分析,分析数据的基本统计属性所需的计算时间和内存(空间)之间的权衡,以及非确定性与确定性在时间和空间之间权衡中的作用的分析。该项目还将专注于计算由简单电路类别计算的函数的问题。目前,云数据中心的大部分计算都是在大规模并行的基础上进行的。尽管有一些编程构造可以方便地使用这种计算能力,但人们对这些构造有效地使用这种并行计算体系结构的程度了解有限。关于大规模并行系统的通信负载的项目工作集中在对这个问题的广泛理解上,理想的情况是在这个过程中开发更有效的算法。使用这些数据中心的高效算法至关重要,因为数据中心的能源需求在电网总使用量中所占的比例越来越大。这个项目关于寻找解决计算问题所需的时间和空间之间的权衡的部分涉及促进对如何最有效地使用这些资源的基本理解。它还将研究一个特殊情况,涉及对一个在计算复杂性中具有更广泛兴趣的公开问题的有限时间计算:检查一个问题的答案的证明比确定答案是或否容易多少?最后,分析计数问题的项目部分的动机既有关于什么简单电路可以计算的基本问题,也有潜在的关于不确定环境的有效推理的应用。
英文摘要
This project will focus on several problems in computational complexity involving tradeoffs among computational resources. These include an analysis of tradeoffs between the communication load, processors, and rounds of communication required to do data analysis on massively parallel systems, an analysis of tradeoffs between the computation time and memory (space) needed to analyze basic statistical properties of data, and an analysis of the role of nondeterminism versus determinism in tradeoffs between time and space. The project will also focus on counting problems for functions computed by simple classes of circuits.A large portion of computations today is being done on a massively parallel basis in cloud data centers. Though there are programming constructs that are convenient for using this computing power, there is only a limited understanding of the extent to which these constructs are using this parallel computing architecture efficiently. The project work on communication load for massively parallel systems focuses on developing a broad understanding of this question, ideally developing more efficient algorithms in the process. Efficient algorithms to use these data centers are critical since the energy requirements of data centers are an increasingly significant portion of the total use of the electric grid. The part of this project on finding tradeoffs between time and space required to solve computational problems involves advancing the fundamental understanding of how to use these resources most efficiently. It also will examine a special case involving time-bounded computation of an open question of much wider general interest in computational complexity: How much easier is it to check a proof of an answer to a problem than to determine whether that answer is yes or no? Finally, the portion of the project on the analysis of counting problems is motivated both by fundamental questions about what simple circuits can compute and by potential application to efficient reasoning about uncertain environments.
期刊论文(2)
专著(0)
科研奖励(0)
会议论文
Stabbing Planes
刺击飞机
DOI:
10.48550/arxiv.1710.03219
发表时间:
2022
期刊:
ArXivorg
影响因子:
--
作者:
[Beame, Paul, Fleming, Noah, Impagliazzo, Russell, Pankratov, Denis, Pitassi, Toniann, Robere, Robert]
通讯作者:
Robere, Robert
AF: Small: Complexity of Representations for Inference
-
批准号:2006359
-
项目类别:Standard Grant
-
资助金额:$35.0万
-
财政年份:2020
-
负责人:Paul Beame
-
依托单位:
SHF: Small: Efficient Verification of Nonlinear Arithmetic
-
批准号:1714593
-
项目类别:Standard Grant
-
资助金额:$45.0万
-
财政年份:2017
-
负责人:Paul Beame
-
依托单位:
AF: Small:Tradeoffs among Measures in Computational and Proof Complexity
-
批准号:1217099
-
项目类别:Standard Grant
-
资助金额:$44.0万
-
财政年份:2012
-
负责人:Paul Beame
-
依托单位:
AF: Large: Collaborative Research: Reliable Quantum Communication and Computation in the Presence of Noise
-
批准号:1111382
-
项目类别:Continuing Grant
-
资助金额:$128.63万
-
财政年份:2011
-
负责人:Paul Beame
-
依托单位:
Travel Support for IEEE Symposium on Foundations of Computer Science (FOCS 2011)
-
批准号:1147364
-
项目类别:Standard Grant
-
资助金额:$1.2万
-
财政年份:2011
-
负责人:Paul Beame
-
依托单位:
Travel Support for the Symposium on Foundations of Computer Science (FOCS 2010)
-
批准号:1049485
-
项目类别:Standard Grant
-
资助金额:$1.5万
-
财政年份:2010
-
负责人:Paul Beame
-
依托单位:
AF: Small: Graph Isomorphism and Quantum Random Walks by Anyons
-
批准号:0916400
-
项目类别:Standard Grant
-
资助金额:$0.0万
-
财政年份:2009
-
负责人:Paul Beame
-
依托单位:
Semi-algebraic complexity and models for massive data set processing
-
批准号:0830626
-
项目类别:Continuing Grant
-
资助金额:$41.45万
-
财政年份:2008
-
负责人:Paul Beame
-
依托单位:
Communication Complexity, Proof Complexity, and Approximation
-
批准号:0514870
-
项目类别:Continuing Grant
-
资助金额:$20.0万
-
财政年份:2005
-
负责人:Paul Beame
-
依托单位:
ITR: Inference in AI, Verification, and Theory: A Unified Approach
-
批准号:0219468
-
项目类别:Continuing Grant
-
资助金额:$49.0万
-
财政年份:2002
-
负责人:Paul Beame
-
依托单位:
Lower Bounds for Time-space Tradeoffs, Data Structures, and Proof Complexity
-
批准号:0098066
-
项目类别:Standard Grant
-
资助金额:$29.7万
-
财政年份:2001
-
负责人:Paul Beame
-
依托单位:
Computational and Proof Complexity Bounds
-
批准号:9800124
-
项目类别:Standard Grant
-
资助金额:$21.3万
-
财政年份:1998
-
负责人:Paul Beame
-
依托单位:
Computational Complexity Lower Bounds
-
批准号:9303017
-
项目类别:Continuing Grant
-
资助金额:$19.32万
-
财政年份:1994
-
负责人:Paul Beame
-
依托单位:
PYI: Resource Bounds and Parallel Computation.
-
批准号:8858799
-
项目类别:Continuing Grant
-
资助金额:$27.45万
-
财政年份:1988
-
负责人:Paul Beame
-
依托单位:
国内基金
海外基金
登录
查看更多内容
昼夜节律性small RNA在血斑形成时间推断中的法医学应用研究
-
批准号:
-
项目类别:省市级项目
-
资助金额:--
-
批准年份:2024
-
负责人:
-
依托单位:
tRNA-derived small RNA上调YBX1/CCL5通路参与硼替佐米诱导慢性疼痛的机制研究
-
批准号:
-
项目类别:省市级项目
-
资助金额:10.0万元
-
批准年份:2022
-
负责人:张祥忠
-
依托单位:
Small RNA调控I-F型CRISPR-Cas适应性免疫性的应答及分子机制
-
批准号:32000033
-
项目类别:青年科学基金项目
-
资助金额:24.0万元
-
批准年份:2020
-
负责人:林平
-
依托单位:
Small RNAs调控解淀粉芽胞杆菌FZB42生防功能的机制研究
-
批准号:31972324
-
项目类别:面上项目
-
资助金额:58.0万元
-
批准年份:2019
-
负责人:高学文
-
依托单位:
变异链球菌small RNAs连接LuxS密度感应与生物膜形成的机制研究
-
批准号:81900988
-
项目类别:青年科学基金项目
-
资助金额:21.0万元
-
批准年份:2019
-
负责人:毛梦莹
-
依托单位:
肠道细菌关键small RNAs在克罗恩病发生发展中的功能和作用机制
-
批准号:31870821
-
项目类别:面上项目
-
资助金额:56.0万元
-
批准年份:2018
-
负责人:陈江宁
-
依托单位:
基于small RNA 测序技术解析鸽分泌鸽乳的分子机制
-
批准号:31802058
-
项目类别:青年科学基金项目
-
资助金额:26.0万元
-
批准年份:2018
-
负责人:麻慧
-
依托单位:
Small RNA介导的DNA甲基化调控的水稻草矮病毒致病机制
-
批准号:31772128
-
项目类别:面上项目
-
资助金额:60.0万元
-
批准年份:2017
-
负责人:吴建国
-
依托单位:
基于small RNA-seq的针灸治疗桥本甲状腺炎的免疫调控机制研究
-
批准号:81704176
-
项目类别:青年科学基金项目
-
资助金额:20.0万元
-
批准年份:2017
-
负责人:赵继梦
-
依托单位:
水稻OsSGS3与OsHEN1调控small RNAs合成及其对抗病性的调节
-
批准号:91640114
-
项目类别:重大研究计划
-
资助金额:85.0万元
-
批准年份:2016
-
负责人:何祖华
-
依托单位: