AF: Small: Rehabilitating Constants in Sublinear Algorithms

AF：小：恢复次线性算法中的常数

基本信息

批准号：
2008868
负责人：
Eric Price
金额：
$ 50万
依托单位：
University of Texas at Austin
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2020
资助国家：
美国
起止时间：
2020-07-01 至 2024-06-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2008868&HistoricalAwards=false
关键词：
AF Small Rehabilitating Constants Sublinear

项目摘要

The scale of data produced in the world is growing faster than theability to process it. One approach for dealing with this data delugeinvolves sublinear algorithms, which are designed to estimate somefeature of data without needing to store, or sometimes even see, theentire data set. Sublinear algorithms include distribution testing(e.g., estimating if a lottery is fair or not), streaming algorithms(e.g., finding the most common URLs on the web), and property testing(e.g., estimating the maximum degree of a network). For theseproblems, computer scientists have carefully studied how thecomplexity of the solution grows with the problem parameters---forexample, estimating if a lottery is fair requires a number of drawsthat scales with the square root of the number of possible numbersdrawn. But results so far have not been able to analyze the solutioncomplexity for concrete instances (e.g., for a birthday lottery with366 possible numbers, how many samples are necessary to verifyfairness?). This project aims to change that, by finding solutionswith not only good asymptotic scaling, but good constant factors.Developing sublinear algorithms with good constant factors willrequire new algorithmic techniques. The sublinear-algorithmsliterature is based on several widespread techniques like probabilityamplification that are simple, general, and optimal up to constantfactors---and significantly suboptimal in their constant factors. Byreplacing these techniques with more fine-grained ones, this projectaims to develop new algorithms with better performance in practice.This project also aims to empirically measure the worst-caseperformance of algorithms, by identifying which input distributionsare provably hardest to solve. By testing different algorithms inpractice, the project will discover and compare the actual impact ofdifferent algorithmic choices.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.

世界上生产的数据规模的增长速度比打架性更快。一种处理这些数据漏洞的方法，旨在估算数据的某些信息而无需存储，甚至有时甚至看到Theentire数据集。套期值包括分布测试（例如，估计彩票是否公平），流算法（例如，在Web上找到最常见的URL）和属性测试（例如，估计网络的最大程度）。对于这些问题，计算机科学家已经仔细研究了解决方案的杂复杂性如何随着问题参数而生长 - 例如，估计彩票是否公平，是否需要许多绘制尺度，并具有可能数字数量的平方根。但是到目前为止，结果尚未能够分析混凝土实例的解决方案复杂性（例如，对于具有366个可能数字的生日彩票，需要多少个样品来验证FAIRNESS？）。该项目的目的是通过找到解决方案，不仅可以与良好的渐近缩放，而且良好的恒定因素。开发具有良好恒定因素的sublinear算法将重新推出新算法技术。 Sublinear-AlgorithMsliteration基于几种广泛的技术，例如简单，一般和最佳的概率放疗，直到常数依赖器 - - 在其常数因子中显着次优。通过将这些技术与更细粒度的技术替代，该项目可以在实践中开发具有更好性能的新算法。该项目还旨在通过验证算法最差的算法性能，通过识别哪种输入分布可证明最难解决的方法。通过测试不同的算法，该项目将发现并比较不同算法的选择的实际影响。该奖项反映了NSF的法定任务，并认为值得通过基金会的智力优点和更广泛的影响来通过评估来获得支持。

项目成果

期刊论文数量（5）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Robust Compressed Sensing MRI with Deep Generative Priors

DOI：
发表时间：
2021-08
期刊：
影响因子：
0
作者：
A. Jalal;Marius Arvinte;Giannis Daras;E. Price;A. Dimakis;Jonathan I. Tamir
通讯作者：
A. Jalal;Marius Arvinte;Giannis Daras;E. Price;A. Dimakis;Jonathan I. Tamir

High-dimensional Location Estimation via Norm Concentration for Subgamma Vectors

通过亚伽玛向量的范数浓度进行高维位置估计