AF: Small: Analysis of Boolean Functions

AF:小:布尔函数分析

基本信息

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

项目摘要

This award is dedicated to the new research on the analysis of Boolean functions. Boolean functions (i.e., mappings from n bits to 1 bit) are one of the most basic objects of study in computer science: they arise in areas as diverse as cryptography, error-correcting codes, learning theory, and circuit design. One of the most effective tools for studying Boolean functions is by considering their Fourier transform and related analytic properties. The PI has been at the forefront of research on analysis of Boolean functions over the last decade and will further develop theory and applications via an attack on three important unsolved problems:1. The Fourier Entropy-Influence Conjecture on how "spread out" the Fourier coefficients of a Boolean function can be. Proving this conjecture would have important consequences for learning theory.2. The Aaronson-Ambainis Conjecture on influences of low-degree Boolean functions. This conjecture has direct relevance to understanding the power of quantum computation.3. The Gotsman-Linial Conjecture on functions computable by the sign of a low-degree polynomial. This is a major problem in the field of concrete complexity.Analysis of Boolean functions has had broad application throughout computer science; it has also had interdisciplinary application through its use in mathematics, statistical physics, and economics. The PI will further develop and spread the impact of the area by writing the first textbook on analysis of Boolean functions. The textbook will be released freely, in installments on a blog. This will not only enhance the connection between research and education, it will foster learning for computer scientists (and aspiring computer scientists) regardless of status and geographic location. Finally, the PI will continue to make broader impact through advising and guiding graduate students and postdoctoral researchers, and through widely disseminating research results.
该奖项致力于布尔函数分析的新研究。布尔函数(即从n位到1位的映射)是计算机科学中最基本的研究对象之一:它们出现在密码学、纠错码、学习理论和电路设计等各种领域。研究布尔函数最有效的工具之一是考虑它们的傅里叶变换和相关的分析性质。在过去的十年里,PI一直处于布尔函数分析研究的前沿,并将通过对三个尚未解决的重要问题的攻击来进一步发展理论和应用:1.关于布尔函数的傅里叶系数如何“展开”的傅里叶熵-影响猜想。证明这一猜想将对学习理论产生重要的影响。Aaronson-Ambainis猜想对低次布尔函数的影响。这一猜想与理解量子计算的力量有直接关系。关于可由低次多项式符号计算的函数的Gotsman-Linial猜想布尔函数分析在整个计算机科学中有着广泛的应用,它还通过在数学、统计物理和经济学中的应用而得到了跨学科的应用。PI将通过编写第一本关于布尔函数分析的教科书来进一步发展和传播这一领域的影响。教科书将在博客上以分期付款的方式免费发布。这不仅将加强研究和教育之间的联系,还将促进计算机科学家(和有抱负的计算机科学家)的学习,无论他们的地位和地理位置如何。最后,通过对研究生和博士后研究人员的建议和指导,以及通过广泛传播研究成果,PI将继续产生更广泛的影响。

项目成果

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

Ryan O'Donnell其他文献

Learning monotone decision trees in polynomial time
在多项式时间内学习单调决策树
Linear programming programming, width-1 CSPs, and robust satisfaction.
线性编程、宽度 1 CSP 和稳健的满意度。
  • DOI:
  • 发表时间:
    2012
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Gabor Kun;Ryan O'Donnell;Suguru Tamaki;Yuichi Yoshida;Yuan Zhou
  • 通讯作者:
    Yuan Zhou
Mo1881 CHRONIC INHALATION EXPOSURE TO PARTICULATE MATTER ALTERS THE INTESTINAL MICROBIOME.
  • DOI:
    10.1016/s0016-5085(23)03143-8
  • 发表时间:
    2023-05-01
  • 期刊:
  • 影响因子:
  • 作者:
    Candace Chang;Rajat Gupta;Farzaneh Sedighian;Kyung-In Baek;David H. Gonzalez;Amirhosein Mousavi;Tien S. Dong;William Katzka;Jocelyn Castellanos;Venu Lagishetty;Srinivasa Reddy;Mohamad Navab;Constantinos Sioutas;Tzung Hsiai;Jesus A.A. Araujo;Jonathan P. Jacobs;Ryan O'Donnell
  • 通讯作者:
    Ryan O'Donnell
Methods used to deliver adjunctive probiotic treatment during the non-surgical management of periodontitis: A scoping review
在牙周炎非手术治疗期间用于提供辅助益生菌治疗的方法:范围审查
  • DOI:
    10.1016/j.jdent.2025.105623
  • 发表时间:
    2025-04-01
  • 期刊:
  • 影响因子:
    5.500
  • 作者:
    Ryan O'Donnell;Richard Holliday;Nick Jakubovics;Ellie Benfield
  • 通讯作者:
    Ellie Benfield

Ryan O'Donnell的其他文献

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

{{ truncateString('Ryan O'Donnell', 18)}}的其他基金

FET: Small: Foundations of Quantum State Learning and Testing
FET:小型:量子态学习和测试的基础
  • 批准号:
    1909310
  • 财政年份:
    2019
  • 资助金额:
    $ 47.64万
  • 项目类别:
    Standard Grant
AF: Small: The Complexity of Random CSPs
AF:小:随机 CSP 的复杂性
  • 批准号:
    1717606
  • 财政年份:
    2017
  • 资助金额:
    $ 47.64万
  • 项目类别:
    Standard Grant
AF: Small: Harmonic Analysis for Quantum Complexity
AF:小:量子复杂性的谐波分析
  • 批准号:
    1618679
  • 财政年份:
    2016
  • 资助金额:
    $ 47.64万
  • 项目类别:
    Standard Grant
AF: Small: CSPs --- Approximability versus Time
AF:小:CSP --- 近似性与时间
  • 批准号:
    1319743
  • 财政年份:
    2013
  • 资助金额:
    $ 47.64万
  • 项目类别:
    Standard Grant
AF: Small : Collaborative Research: The Polynomial Method for Learning
AF:小:协作研究:多项式学习方法
  • 批准号:
    0915893
  • 财政年份:
    2009
  • 资助金额:
    $ 47.64万
  • 项目类别:
    Standard Grant
CAREER: Optimal Approximability
职业:最佳逼近性
  • 批准号:
    0747250
  • 财政年份:
    2008
  • 资助金额:
    $ 47.64万
  • 项目类别:
    Continuing Grant

相似国自然基金

昼夜节律性small RNA在血斑形成时间推断中的法医学应用研究
  • 批准号:
  • 批准年份:
    2024
  • 资助金额:
    0.0 万元
  • 项目类别:
    省市级项目
tRNA-derived small RNA上调YBX1/CCL5通路参与硼替佐米诱导慢性疼痛的机制研究
  • 批准号:
    n/a
  • 批准年份:
    2022
  • 资助金额:
    10.0 万元
  • 项目类别:
    省市级项目
Small RNA调控I-F型CRISPR-Cas适应性免疫性的应答及分子机制
  • 批准号:
    32000033
  • 批准年份:
    2020
  • 资助金额:
    24.0 万元
  • 项目类别:
    青年科学基金项目
Small RNAs调控解淀粉芽胞杆菌FZB42生防功能的机制研究
  • 批准号:
    31972324
  • 批准年份:
    2019
  • 资助金额:
    58.0 万元
  • 项目类别:
    面上项目
变异链球菌small RNAs连接LuxS密度感应与生物膜形成的机制研究
  • 批准号:
    81900988
  • 批准年份:
    2019
  • 资助金额:
    21.0 万元
  • 项目类别:
    青年科学基金项目
肠道细菌关键small RNAs在克罗恩病发生发展中的功能和作用机制
  • 批准号:
    31870821
  • 批准年份:
    2018
  • 资助金额:
    56.0 万元
  • 项目类别:
    面上项目
基于small RNA 测序技术解析鸽分泌鸽乳的分子机制
  • 批准号:
    31802058
  • 批准年份:
    2018
  • 资助金额:
    26.0 万元
  • 项目类别:
    青年科学基金项目
Small RNA介导的DNA甲基化调控的水稻草矮病毒致病机制
  • 批准号:
    31772128
  • 批准年份:
    2017
  • 资助金额:
    60.0 万元
  • 项目类别:
    面上项目
基于small RNA-seq的针灸治疗桥本甲状腺炎的免疫调控机制研究
  • 批准号:
    81704176
  • 批准年份:
    2017
  • 资助金额:
    20.0 万元
  • 项目类别:
    青年科学基金项目
水稻OsSGS3与OsHEN1调控small RNAs合成及其对抗病性的调节
  • 批准号:
    91640114
  • 批准年份:
    2016
  • 资助金额:
    85.0 万元
  • 项目类别:
    重大研究计划

相似海外基金

Collaborative Research: AF: Small: Graph Analysis: Integrating Metric and Topological Perspectives
合作研究:AF:小:图分析:整合度量和拓扑视角
  • 批准号:
    2310412
  • 财政年份:
    2023
  • 资助金额:
    $ 47.64万
  • 项目类别:
    Standard Grant
Collaborative Research: AF: Small: Graph Analysis: Integrating Metric and Topological Perspectives
合作研究:AF:小:图分析:整合度量和拓扑视角
  • 批准号:
    2310411
  • 财政年份:
    2023
  • 资助金额:
    $ 47.64万
  • 项目类别:
    Standard Grant
AF: SMALL: Beyond Worst-Case Analysis for Computing with Polynomials
AF:SMALL:多项式计算的超越最坏情况分析
  • 批准号:
    2110075
  • 财政年份:
    2021
  • 资助金额:
    $ 47.64万
  • 项目类别:
    Standard Grant
AF: Small: Beyond Worst-Case Analysis
AF:小:超越最坏情况分析
  • 批准号:
    2006737
  • 财政年份:
    2020
  • 资助金额:
    $ 47.64万
  • 项目类别:
    Standard Grant
AF: Small: Expanding the Reach of Topological Data Analysis
AF:小:扩大拓扑数据分析的范围
  • 批准号:
    2049010
  • 财政年份:
    2020
  • 资助金额:
    $ 47.64万
  • 项目类别:
    Standard Grant
AF: Small: Expanding the Reach of Topological Data Analysis
AF:小:扩大拓扑数据分析的范围
  • 批准号:
    2007961
  • 财政年份:
    2020
  • 资助金额:
    $ 47.64万
  • 项目类别:
    Standard Grant
AF: Small: Metric Information Theory, Online Learning, and Competitive Analysis
AF:小:度量信息论、在线学习和竞争分析
  • 批准号:
    2007079
  • 财政年份:
    2020
  • 资助金额:
    $ 47.64万
  • 项目类别:
    Standard Grant
AF: Small: Collaborative Research: Reeb graph flows: Metrics, Drawings, and Analysis
AF:小型:协作研究:Reeb 图流:指标、绘图和分析
  • 批准号:
    1907591
  • 财政年份:
    2019
  • 资助金额:
    $ 47.64万
  • 项目类别:
    Standard Grant
AF: Small: Collaborative Research: Boolean Function Analysis Meets Stochastic Design
AF:小:协作研究:布尔函数分析与随机设计的结合
  • 批准号:
    1926872
  • 财政年份:
    2019
  • 资助金额:
    $ 47.64万
  • 项目类别:
    Standard Grant
AF: Small: Collaborative Research: Reeb graph flows: Metrics, Drawings, and Analysis
AF:小型:协作研究:Reeb 图流:指标、绘图和分析
  • 批准号:
    1907612
  • 财政年份:
    2019
  • 资助金额:
    $ 47.64万
  • 项目类别:
    Standard Grant
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了