权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

AF: Small: Parallels in Approximability of Discrete and Continuous Optimization Problems

AF：小：离散和连续优化问题的近似性的相似性

基本信息

批准号：
1816372
负责人：
Madhur Tulsiani
金额：
$ 49.72万
依托单位：
Toyota Technological Institute at Chicago
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2018
资助国家：
美国
起止时间：
2018-10-01 至 2022-09-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1816372&HistoricalAwards=false
关键词：
AF Small Parallels Approximability Discrete

项目摘要

Optimization problems arise naturally in many areas such as scheduling, artificial intelligence, software engineering, control of robotic systems, statistics and machine learning. Many of these problems require too long to solve exactly - a common approach for dealing with this has been to design techniques which can efficiently find approximate solutions that are 'good enough' for the task at hand. The study of what approximations are best possible, as well as methods for achieving them, has also led to many new ideas in theoretical computer science, leading to a rich mathematical theory. This project considers several such problems (arising in different areas) which represent challenges to our current understanding. The goal of the project is to develop unified techniques for solving and analyzing them. The project includes several opportunities for training and mentoring of graduate and undergraduate students. Another aim of the project is to develop a collaborative forum for theoretical computer science students in the Chicago area, which can be used to discuss technical ideas and develop expository material.This project considers various problems in discrete and continuous optimization, which represent bottlenecks for algorithmic techniques for designing approximation algorithms, as well as for techniques proving hardness of approximation. The difficulty of understanding many of these problems arises from the fact that many of them only impose a relatively weak global constraint on the solutions, which is hard to exploit algorithmically and also not amenable to techniques for proving inapproximability. The project considers several continuous optimization problems which offer an ideal testbed for the development of new algorithmic techniques, while still capturing the bottlenecks in proving inapproximability of related discrete problems. The aim of this project is to examine such problems from the following perspectives: (1) average-case hardness and lower bounds for the Sum-of-Squares hierarchy of convex relaxations; (2) techniques and barriers for proving inapproximability; and (3) conditions under which good approximations are achievable.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

优化问题在调度、人工智能、软件工程、机器人系统控制、统计学和机器学习等许多领域自然出现。许多这样的问题需要很长时间才能精确地解决——处理这个问题的一个常见方法是设计能够有效地找到“足够好”的近似解的技术。研究什么样的近似是最好的，以及实现它们的方法，也导致了理论计算机科学中的许多新思想，导致了丰富的数学理论。这个项目考虑了几个这样的问题（出现在不同的领域），这些问题对我们目前的理解构成了挑战。该项目的目标是开发解决和分析这些问题的统一技术。该项目包括对研究生和本科生进行培训和指导的几个机会。该项目的另一个目标是为芝加哥地区的理论计算机科学学生开发一个合作论坛，可以用来讨论技术思想和开发说明性材料。本项目考虑离散和连续优化中的各种问题，这些问题代表了设计近似算法的算法技术以及证明近似硬度的技术的瓶颈。理解这些问题的困难来自于这样一个事实，即它们中的许多只对解决方案施加了相对较弱的全局约束，这很难在算法上利用，也不适合证明不可近似性的技术。该项目考虑了几个连续优化问题，为新算法技术的发展提供了理想的测试平台，同时仍然抓住了证明相关离散问题不可逼近性的瓶颈。本项目的目的是从以下几个方面来研究这些问题：(1)凸松弛的平方和层次的平均情况硬度和下界；（二）证明不可近似性的技术和障碍；(3)实现良好近似的条件。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

期刊论文数量（10）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Concentration of polynomial random matrices via Efron-Stein inequalities

通过 Efron-Stein 不等式进行多项式随机矩阵的集中

DOI：
发表时间：
2023
期刊：
Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA
影响因子：
0
作者：
Rajendran, Goutham;Tulsiani, Madhur
通讯作者：
Tulsiani, Madhur

Separating the NP-Hardness of the Grothendieck Problem from the Little-Grothendieck Problem

将 Grothendieck 问题的 NP 难度与 Little-Grothendieck 问题分开

DOI：
10.4230/lipics.itcs.2022.22
发表时间：
2022
期刊：
Leibniz international proceedings in informatics
影响因子：
0
作者：
Bhattiprolu, Vijay and
通讯作者：
Bhattiprolu, Vijay and

Approximability of p → q Matrix Norms: Generalized Krivine Rounding and Hypercontractive Hardness

DOI：
10.1137/1.9781611975482.83
发表时间：
2019-01
期刊：
Numerische Mathematik
影响因子：
2.1
作者：
V. Bhattiprolu;Mrinalkanti Ghosh;V. Guruswami;Euiwoong Lee;Madhur Tulsiani
通讯作者：
V. Bhattiprolu;Mrinalkanti Ghosh;V. Guruswami;Euiwoong Lee;Madhur Tulsiani

Near-linear time decoding of Ta-Shma’s codes via splittable regularity

通过可分割正则性对 Ta-Shma 码进行近线性时间解码