AF: Small: RUI: Towards Resolving the Dynamic Optimality Conjecture.

AF：小：RUI：解决动态最优猜想。

• 批准号: 1910873
• 负责人: Mayank Goswami
• 金额: $ 40万
• 依托单位: CUNY Queens College
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-10-01 至 2024-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1910873&HistoricalAwards=false
• 关键词: AF; Small; RUI; Towards; Resolving

Searching is a fundamental problem in computer science, and faster search algorithms have been the focus of many researchers for decades. Being a basic primitive in all databases, fast searching in the age of big data has numerous applications in almost any field of data science. A binary search tree (BST) was one of the first and simplest data structures developed for searching, in which the keys in the database are stored in a binary tree, which allows an easy search algorithm to locate keys. In the real world, a sequence of searches come in an online fashion (the next search is revealed only after the current search is conducted), which led researchers to ask whether dynamically adjusting a BST may help access future (unknown) searches faster. While it may seem counterintuitive, for a wide variety of special search sequences, there exist online data structures that perform these searches almost as fast as the best offline algorithm -- one that knew all the searches in advance. Two such data structures are Splay Trees, developed by Sleator and Tarjan [1985] , and Greedy developed by Lucas [1988] and Munro [2000]. The dynamic optimality conjecture states that one of these online algorithms, in fact, accesses all sequences almost as fast as the optimal offline algorithm. This conjecture, widely regarded as one of fundamental problems in data structures, remains unresolved after 35 years. In this project the PI proposes three avenues to attack this conjecture. This project aims at producing the next generation of researchers and promoting under-represented groups in science and technology. Because of the simplicity of the conjecture, many undergraduate students will be able to understand it, appreciate the field of data structures, and thereby be motivated to pursue a career in computer science. The PI already has minority undergraduate and graduate students involved in this project. CUNY Queens College is a Hispanic-serving institution. The PI is committed to engaging more undergraduate students and women in research.The dynamic optimality conjecture is perhaps one of the most elusive unsolved problems in data structures. It postulates the existence of an online binary search tree (BST) which is O(1) competitive with the optimal offline self-balancing BST (called OPT). It is one of the simplest cases of instance optimality, and has been particularly elusive in that highly restricted consequences of the conjecture had remained open for three decades. The traversal conjecture and the weighted dynamic finger property are two recently settled conjectures (the former being resolved by the PI and his co-authors). After overcoming these last-remaining barriers, one needs a new set of barriers that will get us closer to proving or disproving dynamic optimality for the two main candidates, Splay trees and Greedy. The PI maps out a plan to attack this conjecture.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.

搜索是计算机科学中的一个基本问题，数十年来，更快的搜索算法一直是许多研究人员的重点。作为所有数据库中的基本原始性，大数据时代的快速搜索在几乎任何数据科学领域都有许多应用程序。二进制搜索树（BST）是开发用于搜索的第一个也是最简单的数据结构之一，其中数据库中的密钥存储在二进制树中，该键允许简单的搜索算法找到键。在现实世界中，一系列搜索是以在线方式进行的（下一个搜索仅在进行当前搜索之后才揭示），这导致研究人员询问动态调整BST是否可以帮助访问未来（未知）搜索速度更快。尽管对于各种特殊的搜索序列而言，这似乎是违反直觉的，但是存在在线数据结构，这些搜索几乎与最好的离线算法一样快，该算法预先知道所有搜索。 Sleator和Tarjan [1985]开发的两个数据结构是张开树，以及由Lucas [1988]和Munro [2000]开发的贪婪。动态最优性猜想指出，这些在线算法之一实际上，所有序列几乎与最佳离线算法一样快。这种猜想被广泛认为是数据结构中的基本问题之一，在35年后仍未解决。在这个项目中，PI提出了三种途径来攻击这一猜想。 该项目旨在生产下一代研究人员，并促进科学技术的代表性不足的群体。由于猜想的简单性，许多本科生将能够理解它，欣赏数据结构领域，从而有动力从事计算机科学职业。 PI已经有少数本科生和研究生参与了该项目。 CUNY皇后学院是一家西班牙裔服务机构。 PI致力于使更多的本科生和女性参与研究。动态最佳猜想可能是数据结构中最难以捉摸的未解决问题之一。它假设存在在线二进制搜索树（BST），该树与最佳离线自动平衡BST（称为OPT）具有竞争性。它是实例最佳性最简单的案例之一，并且特别难以捉摸，因为猜想的高度限制后果已经开放了三十年。遍历猜想和加权动态手指特性是两个最近的猜想（前者是由PI和他的合着者解决的）。在克服了这些最后的障碍之后，人们需要一套新的障碍，这将使我们更接近证明或反驳两种主要候选人的动态最佳性，即暴跌树和贪婪。 PI绘制了一项攻击这一猜想的计划。该奖项反映了NSF的法定任务，并被认为是值得通过基金会的知识分子优点和更广泛影响的审查标准来评估值得支持的。

项目成果

Batched Predecessor and Sorting with Size-Priced Information in External Memory

批处理前驱和外部存储器中按大小定价的信息排序

• DOI: 10.1007/978-3-030-61792-9_13
• 发表时间: 2021
• 期刊: Latin American Symposium on Theoretical Informatics
• 作者: Bender, Michael A;Goswami, Mayank;Medjedovic, Dzejla;Montes, Pablo;Tsichlas, Kostas
• 通讯作者: Tsichlas, Kostas

Topological Detection of Trojaned Neural Networks

• 发表时间: 2021-06
• 期刊: ArXiv
• 作者: Songzhu Zheng;Yikai Zhang;H. Wagner;Mayank Goswami;Chao Chen

Stability of SGD: Tightness Analysis and Improved Bounds

• 发表时间: 2021-02
• 作者: Yikai Zhang;Wenjia Zhang-;Sammy Bald;Vamsi Pingali;Chao Chen;Mayank Goswami

Learning to Segment from Noisy Annotations: A Spatial Correction Approach

• DOI: 10.48550/arxiv.2308.02498
• 发表时间: 2023-07
• 期刊: ArXiv
• 作者: Jiacheng Yao;Yikai Zhang;Songzhu Zheng;Mayank Goswami;P. Prasanna;Chao Chen

Obtaining Approximately Optimal and Diverse Solutions via Dispersion

通过分散获得近似最优且多样化的解

• 发表时间: 2022
• 期刊: Latin American Symposium on Theoretical Informatics
• 作者: Gao, Jie;Goswami, Mayank;C.S., Karthik;Tsia, Meng-Tsung;Tsai, Shih-Yu;Yang Hao-Tsung
• 通讯作者: Yang Hao-Tsung