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是否有助于更快地访问未来（未知）搜索。虽然这看起来似乎违反直觉，但对于各种特殊的搜索序列，存在在线数据结构，它们执行这些搜索的速度几乎与最好的离线算法一样快-一种预先知道所有搜索的算法。两种这样的数据结构是Splay Trees，由Sleator和Tarjan [1985]开发，以及Greedy，由Lucas [1988]和Munro [2000]开发。动态最优性猜想指出，这些在线算法之一，事实上，访问所有序列几乎一样快的最佳离线算法。这个猜想被广泛认为是数据结构中的基本问题之一，35年后仍然没有得到解决。在这个项目中，PI提出了三种方法来攻击这个猜想。 该项目旨在培养下一代研究人员，促进科学和技术领域代表性不足的群体。由于猜想的简单性，许多本科生将能够理解它，欣赏数据结构领域，从而有动力追求计算机科学的职业生涯。PI已经有少数民族本科生和研究生参与了这个项目。纽约市立大学皇后学院是一所为西班牙裔服务的机构。PI致力于吸引更多的本科生和女性参与研究。动态最优性猜想可能是数据结构中最难以捉摸的未解决问题之一。它假设存在一个在线二叉搜索树（BST），这是O（1）的最佳离线自平衡BST（称为OPT）的竞争。这是实例最优性的最简单的例子之一，并且特别难以捉摸，因为这个猜想的高度限制的结果已经开放了30年。遍历猜想和加权动态指属性是最近解决的两个猜想（前者由PI和他的合著者解决）。在克服了这些最后剩下的障碍之后，我们需要一组新的障碍，这将使我们更接近于证明或反驳两个主要候选者的动态最优性，即Splay树和Greedy。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

Stability of SGD: Tightness Analysis and Improved Bounds

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

Topological Detection of Trojaned Neural Networks

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

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