AF: Small: Rehabilitating Constants in Sublinear Algorithms

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

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.