AF: Small: Sublinear Algorithms for Visual Properties

AF：小：视觉属性的次线性算法

• 批准号: 1909612
• 负责人: Sofya Raskhodnikova
• 金额: $ 20万
• 依托单位: Trustees of Boston University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-10-01 至 2021-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1909612&HistoricalAwards=false
• 关键词: AF; Small; Sublinear; Algorithms; Visual

The area of sublinear algorithms aims to establish algorithmic foundations for processing big data. Sublinear algorithms produce quick, approximate answers after examining only a tiny fraction of their input. This project focuses specifically on sublinear algorithms for visual and geometric data, with the goal of laying foundations for studying such data in the sublinear context. This requires the development of new tools and will open up new connections as well as new areas of applications. Effectively exploiting big data can provide significant societal benefits. The research pursued by this project contributes the theoretical foundations necessary to take advantage of big data. It has the potential to change how visual data is processed and analyzed. The results of this research will be integrated into the investigator's graduate course on sublinear algorithms.The primary goal of this project is a systematic investigation of visual data in the sublinear context. Whereas there are established and successful lines of research in sublinear algorithms and property testing on functions, codes (and, more generally, algebraic properties), graphs, and discrete distributions, several potential applications of sublinear algorithms require working with visual and geometric data. Specifically, sublinear algorithms that can test basic visual properties, such as symmetry, convexity, and low genus have the potential to dramatically speed up image processing applications. Some of these properties have not been studied at all in the context of sublinear algorithms. This project investigates fundamental problems in testing visual properties, considers problems in higher dimensions, and studies new computational tasks with a focus on robustness. To achieve their full potential, sublinear algorithms need to be able to handle geometric and visual data.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.

次线性算法领域旨在建立处理大数据的算法基础。次线性算法在仅检查输入的一小部分后即可产生快速、近似的答案。该项目特别关注视觉和几何数据的次线性算法，目标是为在次线性背景下研究此类数据奠定基础。这需要开发新的工具，并将开辟新的连接以及新的应用领域。有效利用大数据可以带来显着的社会效益。该项目所进行的研究为利用大数据提供了必要的理论基础。它有可能改变视觉数据的处理和分析方式。这项研究的结果将被纳入研究者的次线性算法研究生课程中。该项目的主要目标是对次线性背景下的视觉数据进行系统研究。尽管在次线性算法和函数、代码（更一般地说，代数属性）、图形和离散分布的属性测试方面已经建立了成功的研究路线，但次线性算法的一些潜在应用需要使用视觉和几何数据。具体来说，可以测试对称性、凸性和低几何等基本视觉属性的次线性算法有可能显着加快图像处理应用程序的速度。其中一些属性根本没有在次线性算法的背景下进行过研究。该项目研究测试视觉属性的基本问题，考虑更高维度的问题，并研究新的计算任务，重点关注鲁棒性。为了充分发挥其潜力，次线性算法需要能够处理几何和视觉数据。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps

实值函数的最佳不一致性测试器：适应性有帮助

• DOI: 10.4086/toc.2020.v016a003
• 发表时间: 2020-09
• 期刊: Theory of Computing
• 影响因子: 1
• 作者: Baleshzar, Roksana;Chakrabarty, Deeparnab;Pallavoor, Ramesh Krishnan;Raskhodnikova, Sofya;Seshadhri, C.
• 通讯作者: Seshadhri, C.

Erasure-Resilient Sublinear-Time Graph Algorithms

抗擦除次线性时间图算法

• DOI: 10.4230/lipics.itcs.2021.80
• 发表时间: 2021-01
• 期刊: ITCS 2021
• 作者: Levi, Amit;Pallavoor, Ramesh Krishnan;Raskhodnikova, Sofya;Varma, Nithin
• 通讯作者: Varma, Nithin

Approximating the Distance to Monotonicity of Boolean Functions

近似布尔函数的单调性距离

• DOI: 10.1137/1.9781611975994.123
• 发表时间: 2020-01
• 期刊: SODA 2020
• 作者: Pallavoor, Ramesh Krishnan;Raskhodnikova, Sofya;Waingarten, Erik
• 通讯作者: Waingarten, Erik

Erasures versus errors in local decoding and property testing

本地解码和属性测试中的擦除与错误

• DOI: 10.1002/rsa.21031
• 发表时间: 2021-12
• 期刊: Random Structures & Algorithms
• 影响因子: 1
• 作者: Raskhodnikova, Sofya;Ron‐Zewi, Noga;Varma, Nithin
• 通讯作者: Varma, Nithin