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.

世界上产生的数据规模的增长速度快于处理数据的能力的增长速度。处理这种数据洪流的一种方法涉及次线性算法，该算法旨在估计数据的某些特征，而不需要存储，有时甚至不需要查看整个数据集。次线性算法包括分布测试（例如，估计彩票是否公平）、流算法（例如，查找网络上最常见的 URL）和属性测试（例如，估计网络的最大度）。对于这些问题，计算机科学家仔细研究了解决方案的复杂性如何随着问题参数的增加而增长——例如，估计彩票是否公平需要抽奖次数，该次数与可能抽奖号码数量的平方根成正比。但迄今为止的结果还无法分析具体实例的解决方案复杂性（例如，对于有 366 个可能数字的生日彩票，需要多少样本来验证公平性？）。该项目旨在通过寻找不仅具有良好渐近标度而且具有良好常数因子的解决方案来改变这一现状。开发具有良好常数因子的次线性算法将需要新的算法技术。次线性算法文献基于几种广泛使用的技术，例如概率放大，这些技术简单、通用且在常数因子范围内是最优的，并且在常数因子范围内显着次优。通过用更细粒度的技术取代这些技术，该项目旨在开发在实践中具有更好性能的新算法。该项目还旨在通过确定哪些输入分布被证明是最难解决的，来凭经验测量算法的最坏情况性能。通过在实践中测试不同的算法，该项目将发现并比较不同算法选择的实际影响。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。