AF: Small: Rehabilitating Constants in Sublinear Algorithms

点击翻译按钮获取中文摘要

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.