一句话：提出在线结构理论的算子框架，统一在线算法、可计算分析、Weihrauch 归约与反推数学等。
本文提出一个在线结构理论的统一框架，其核心是用算子处理输入，并允许输入为任意复杂度的可数对象。该框架推广了可计算性理论与复杂性理论中独立出现的若干概念：一方面把在线算法与可计算分析联系起来，说明在线算法可视为可计算分析的一个子领域，反过来也丰富可计算分析；另一方面引入 Weihrauch 归约等可计算分析工具来分析有限但一致的组合问题，并将反推数学有限化，以刻画无限组合问题的有限类似物的精细结构。此外，该框架还融合 EX 学习、分布式计算等领域的相似思想。
We introduce a framework for online structure theory. Our approach generalises notions arising independently in several areas of computability theory and complexity theory. We suggest a unifying approach using operators where we allow the input to be a countable object of an arbitrary complexity. We give a new framework which (i) ties online algorithms with computable analysis, (ii) shows how to use modifications of notions from computable analysis, such as Weihrauch reducibility, to analyse finite but uniform combinatorics, (iii) show how to finitize reverse mathematics to suggest a fine structure of finite analogs of infinite combinatorial problems, and (iv) see how similar ideas can be amalgamated from areas such as EX-learning, computable analysis, distributed computing and the like. One of the key ideas is that online algorithms can be viewed as a sub-area of computable analysis. Conversely, we also get an enrichment of computable analysis from classical online algorithms.
@article{paperbot1296,
title = {Foundations of Online Structure Theory II: The Operator Approach},
author = {Rod Downey and Alexander Melnikov and Keng Meng Ng},
journal = {Logical Methods in Computer Science},
volume = {Volume 17, Issue 3},
year = {2021},
doi = {10.46298/lmcs-17(3:6)2021}
}