CT-ISG: Cross-Leveraging Cryptography with Learning Theory
CT-ISG: Cross-Leveraging Cryptography with Learning Theory
批准号:
0716245
负责人:
Rocco Servedio
金额:
$0.0万
依托单位:
依托单位国家:
美国
项目类别:
Continuing Grant
财政年份:
2007
资助国家:
美国
项目状态:
已结题
起止时间:
2007-09-01 至 2011-08-31
中文摘要
这项研究涉及密码学和计算学习理论之间的联系的详细研究。密码学是关于如何处理信息以实现机密性、完整性、保密性等,而学习理论是关于从一些未知对象中高效地提取信息。学习理论为机器学习这一实际重要的领域提供了严格的基础,密码学在计算机安全的关键领域也扮演着类似的角色。在这项研究中,研究人员致力于根据计算学习理论中各种问题的假定难度来获得新的密码学结果,并通过密码学来获得新的学习结果,从而扩展和深化了当前对这两个领域以及它们之间的联系的理解。这项研究与一项通过教育产生更广泛影响的计划相结合,在哥伦比亚大学开发了一门关于密码学和学习理论之间联系的高级课程,并建议和指导一批不同的研究生发展为研究人员和教育工作者。更详细地说,这项研究涉及(I)从被广泛认为很难的学习问题中构建和应用新的密码原语,如公钥密码系统和伪随机发生器;(Ii)继续探索各种已被充分研究的概念类的平均案例学习能力,如决策树和DNF公式;(Iii)使用密码学的工具,将学习的计算难度应用于建立各种布尔函数类的学习的计算难度;(V)通过证明在一个模型中具有多项式时间算法的学习问题在另一个模型中是难以处理的(在密码假设下),努力获得多项式时间学习模型对之间的计算分离;以及(Vi)探索证明学习的计算难度所需的最小假设是什么这一基本问题。
英文摘要
This research involves a detailed study of the connections between Cryptography and Computational Learning Theory. Cryptography is about manipulating information in order to achieve confidentiality, integrity, privacy, etc., while learning theory is about efficiently extracting information from some unknown object. Learning theory provides a rigorous basis for the practically important field of machine learning, and cryptography plays a similar role for the crucial area of computer security. In this research the investigators work to obtain new cryptographic results based on the presumed hardness of various problems in computational learning theory, and work to obtain new learning results via cryptography, thus extending and deepening the current understanding of both areas and the connections between them. The research is integrated with a plan to achieve broader impact through education by developing an advanced course on the connections between cryptography and learning theory at Columbia University and advising and guiding a diverse group of graduate students in their development as researchers and educators.In more detail, the research involves (i) constructing and applying new cryptographic primitives, such as public-key cryptosystems and pseudorandom generators with very low circuit complexity, from learning problems that are widely believed to be hard; (ii) continuing ongoing work on exploring the average-case learnability of various well-studied concept classes such as decision trees and DNF formulas; (iii) applying computational hardness of learning to establishing computational hardness of learning for various Boolean function classes, using tools from cryptography; (v) working to obtain computational separations between pairs of well-studied learning models by showing that learning problems that have polynomial-time algorithms in one model are intractable (under a cryptographic assumption) in the other model; and (vi) exploring the foundational issue of what are the minimal assumptions required to prove computational hardness of learning.
期刊论文(0)
专著(0)
科研奖励(0)
会议论文
Collaborative Research: AF: Medium: Continuous Concrete Complexity
-
批准号:2211238
-
项目类别:Continuing Grant
-
资助金额:$60.0万
-
财政年份:2022
-
负责人:Rocco Servedio
-
依托单位:
AF: Medium: The Trace Reconstruction Problem
-
批准号:2106429
-
项目类别:Continuing Grant
-
资助金额:$120.0万
-
财政年份:2021
-
负责人:Rocco Servedio
-
依托单位:
NSF QCIS-FF: Columbia University Computer Science Department Proposal
-
批准号:1926524
-
项目类别:Continuing Grant
-
资助金额:$75.0万
-
财政年份:2020
-
负责人:Rocco Servedio
-
依托单位:
Student Travel Grant for 2019 Conference on Computational Complexity (CCC)
-
批准号:1919026
-
项目类别:Standard Grant
-
资助金额:$1.0万
-
财政年份:2019
-
负责人:Rocco Servedio
-
依托单位:
BIGDATA: F: Big Data Analysis via Non-Standard Property Testing
-
批准号:1838154
-
项目类别:Standard Grant
-
资助金额:$91.0万
-
财政年份:2019
-
负责人:Rocco Servedio
-
依托单位:
AF: Small: Collaborative Research: Boolean Function Analysis Meets Stochastic Design
-
批准号:1814873
-
项目类别:Standard Grant
-
资助金额:$16.63万
-
财政年份:2018
-
负责人:Rocco Servedio
-
依托单位:
Student Travel Support for CCC 2018
-
批准号:1822097
-
项目类别:Standard Grant
-
资助金额:$1.5万
-
财政年份:2018
-
负责人:Rocco Servedio
-
依托单位:
AF: Student Travel to CCC 2017
-
批准号:1724073
-
项目类别:Standard Grant
-
资助金额:$1.5万
-
财政年份:2017
-
负责人:Rocco Servedio
-
依托单位:
AF: Medium: Collaborative Research: Circuit Lower Bounds via Projections
-
批准号:1563155
-
项目类别:Continuing Grant
-
资助金额:$84.15万
-
财政年份:2016
-
负责人:Rocco Servedio
-
依托单位:
AF: Small: Linear and Polynomial Threshold Functions: Structural Analysis and Algorithmic Applications
-
批准号:1420349
-
项目类别:Standard Grant
-
资助金额:$45.0万
-
财政年份:2014
-
负责人:Rocco Servedio
-
依托单位:
AF: Small: Learning and Testing Classes of Distributions
-
批准号:1319788
-
项目类别:Standard Grant
-
资助金额:$47.19万
-
财政年份:2013
-
负责人:Rocco Servedio
-
依托单位:
Student Travel to STOC 2013
-
批准号:1319775
-
项目类别:Standard Grant
-
资助金额:$1.5万
-
财政年份:2013
-
负责人:Rocco Servedio
-
依托单位:
AF: Small: The Boundary of Learnability for Monotone Boolean Functions
-
批准号:1115703
-
项目类别:Standard Grant
-
资助金额:$35.0万
-
财政年份:2011
-
负责人:Rocco Servedio
-
依托单位:
AF: Small: Collaborative Research: The Polynomial Method for Learning
-
批准号:0915929
-
项目类别:Standard Grant
-
资助金额:$25.0万
-
财政年份:2009
-
负责人:Rocco Servedio
-
依托单位:
QnTM: Quantum Computational Learning
-
批准号:0523664
-
项目类别:Continuing Grant
-
资助金额:$28.0万
-
财政年份:2005
-
负责人:Rocco Servedio
-
依托单位:
CAREER: Efficient Learning Algorithms for Rich Function Classes
-
批准号:0347282
-
项目类别:Continuing Grant
-
资助金额:$40.0万
-
财政年份:2004
-
负责人:Rocco Servedio
-
依托单位:
Efficient Algorithms in Computational Learning Theory
-
批准号:0102075
-
项目类别:Fellowship Award
-
资助金额:$9.0万
-
财政年份:2001
-
负责人:Rocco Servedio
-
依托单位:
国内基金
海外基金
登录
查看更多内容
季铵盐类化合物通过ISG15驱动谷氨酰胺代谢重编程在多发性骨髓瘤硼替佐米敏感性中的作用及机制研究
-
批准号:82660054
-
项目类别:地区科学基金项目
-
资助金额:32.00万元
-
批准年份:2026
-
负责人:曾俊权
-
依托单位:
甘草苷通过IFN-I/ISG15信号通路促进卵巢颗粒细胞外泌体分泌延缓卵巢衰老的作用机制
-
批准号:
-
项目类别:省市级项目
-
资助金额:--
-
批准年份:2025
-
负责人:李璐邑
-
依托单位:
ISG15/LFA-1调控肿瘤相关巨噬细胞浸润促进胆囊癌免疫逃逸的机制研究
-
批准号:
-
项目类别:省市级项目
-
资助金额:--
-
批准年份:2025
-
负责人:蔡炜龙
-
依托单位:
ISG化修饰在系统性红斑狼疮心肌炎症与损伤中的作用与机制研究
-
批准号:82500361
-
项目类别:青年科学基金项目(C类)
-
资助金额:30.00万元
-
批准年份:2025
-
负责人:张文佳
-
依托单位:
白癜风在皮—心轴中通过ISG15对动脉粥样硬化的作用和机制研究
-
批准号:825B2099
-
项目类别:青年学生基础研究项目
-
资助金额:30.00万元
-
批准年份:2025
-
负责人:刘林
-
依托单位:
ISG15类泛素化修饰多囊泡小体介导KNG1-PI3K/Akt信号轴在葡萄膜炎内皮屏障损伤中的作用机制研究
-
批准号:JCZRQN202500743
-
项目类别:省市级项目
-
资助金额:--
-
批准年份:2025
-
负责人:
-
依托单位:
CREBRF/ISG15通过类泛素化影响猪颗粒细胞雌二醇合成的机制研究
-
批准号:32560788
-
项目类别:地区科学基金项目
-
资助金额:32.00万元
-
批准年份:2025
-
负责人:刘颖
-
依托单位:
ISG20L2介导核糖体RNA前体剪切促进肿瘤发生发展的作用与机制
-
批准号:32471350
-
项目类别:面上项目
-
资助金额:50.00万元
-
批准年份:2024
-
负责人:刘秀华
-
依托单位:
ISG15下调lncRNA RP11-5407.3介导细胞自噬促进子宫内膜癌进展的
作用及机制研究
-
批准号:
-
项目类别:省市级项目
-
资助金额:--
-
批准年份:2024
-
负责人:
-
依托单位:
肾周脂肪M2 巨噬细胞通过ISG15/LFA-1轴调控传入神经活性在肥
胖相关高血压中的作用及机制研究
-
批准号:
-
项目类别:省市级项目
-
资助金额:--
-
批准年份:2024
-
负责人:郭静
-
依托单位: