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.

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

项目成果

Erasure-Resilient Sublinear-Time Graph Algorithms

抗擦除次线性时间图算法

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

Erasures versus errors in local decoding and property testing

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

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

Approximating the Distance to Monotonicity of Boolean Functions

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

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

Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps

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

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