AF: Small: Sublinear Algorithms for Real Data

次线性算法领域旨在为处理大数据建立算法基础。在只阅读一小部分数据的情况下，我们可以了解数据的哪些全局属性？如果数据有噪音怎么办？我们能否快速恢复损坏的数据点，同时确保数据的某些全局属性？该项目特别关注用于实值数字数据的次线性算法以及与其相关的现实世界挑战。有效地利用大数据可以提供显著的社会效益。该项目有可能改变处理和分析真实价值数据的方式，以及处理敏感数据集的隐私的方式。此外，该项目还包括旨在确保工作的更广泛影响和改善劳动力培训的教育活动。他们包括给研究生提供建议和指导；继续在宾夕法尼亚州立大学建立强大的理论基础小组；包括在PI的研究生课程中关于次线性算法的拟议研究的结果；通过演讲和出版物广泛传播这项研究的结果，更广泛地传播算法和计算思想；通过提供针对计算机科学和数学的女性的指导和教育活动来促进多样性。虽然在次线性算法和关于布尔函数、代码(更广泛地说，代数属性)、图形和离散分布的性质测试方面已经建立了成功的研究路线，但最近的几个次线性算法的应用需要使用真实的数据。这些课程包括研究Lipschitz函数及其在数据保密方面的应用，以及研究子模函数及其在经济学中的应用。为了充分发挥其潜力，次线性算法需要能够处理实值数据。这个项目的目的是为这一领域的研究奠定基础。这将需要开发新的工具，并将开辟新的联系和新的应用领域。研究工作分为三个部分：1.Lipschitz函数的测试和局部重构及其在数据保密中的应用；2.新的精度保证措施，重点是L_p度量；3.数据访问的新模型。

The area of sublinear algorithms aims to establish algorithmic foundations for processing big data. What global properties of the data can we understand while reading only a small portion of it? What if the data is noisy? Can we quickly restore a corrupted data point while ensuring some global property of the data? This project focuses specifically on sublinear algorithms for real-valued numeric data and on real-world challenges associated with it.Effectively exploiting big data can provide significant societal benefits. This project has the potential to change how real-valued data is processed and analyzed, and how privacy of sensitive datasets is handled. In addition, this project includes educational activities designed to ensure the work's broader impact and to improve workforce training. They include advising and mentoring graduate students; continuing to build a strong theoretical foundations group at Penn State; including the results of the proposed research in the PI's graduate course on sublinear algorithms; widely disseminating the results of this research and, more broadly, algorithmic and computational ideas via talks and publications; and fostering diversity by providing mentoring and educational activities targeted at women in computer science and mathematics.While there are established and successful lines of research in sublinear algorithms and property testing on Boolean functions, codes (and, more generally, algebraic properties), graphs, and discrete distributions, several recent applications of sublinear algorithms require working with real data. These include the study of Lipschitz functions with applications to data privacy and the study of submodular functions with applications to economics. To achieve their full potential, sublinear algorithms need to be able to handle real-valued data. The aim of this project is to lay the foundations for this area of study. This will require the development of new tools and will open up new connections and new areas of application. The research activities are grouped into three parts: 1. testing and local reconstruction of Lipschitz functions with applications to data privacy; 2. new measures for accuracy guarantees, with the focus on L_p metrics; and 3. new models for data access.