论文标题
部分可观测时空混沌系统的无模型预测
Space Optimal Vertex Cover in Dynamic Streams
论文作者
论文摘要
储层计算是预测湍流的有力工具，其简单的架构具有处理大型系统的计算效率。然而，其实现通常需要完整的状态向量测量和系统非线性知识。我们使用非线性投影函数将系统测量扩展到高维空间，然后将其输入到储层中以获得预测。我们展示了这种储层计算网络在时空混沌系统上的应用，该系统模拟了湍流的若干特征。我们表明，使用径向基函数作为非线性投影器，即使只有部分观测并且不知道控制方程，也能稳健地捕捉复杂的系统非线性。最后，我们表明，当测量稀疏、不完整且带有噪声，甚至控制方程变得不准确时，我们的网络仍然可以产生相当准确的预测，从而为实际湍流系统的无模型预测铺平了道路。
We optimally resolve the space complexity for the problem of finding an $α$-approximate minimum vertex cover ($α$MVC) in dynamic graph streams. We give a randomised algorithm for $α$MVC which uses $O(n^2/α^2)$ bits of space matching Dark and Konrad's lower bound [CCC 2020] up to constant factors. By computing a random greedy matching, we identify `easy' instances of the problem which can trivially be solved by returning the entire vertex set. The remaining `hard' instances, then have sparse induced subgraphs which we exploit to get our space savings and solve $α$MVC. Achieving this type of optimality result is crucial for providing a complete understanding of a problem, and it has been gaining interest within the dynamic graph streaming community. For connectivity, Nelson and Yu [SODA 2019] improved the lower bound showing that $Ω(n \log^3 n)$ bits of space is necessary while Ahn, Guha, and McGregor [SODA 2012] have shown that $O(n \log^3 n)$ bits is sufficient. For finding an $α$-approximate maximum matching, the upper bound was improved by Assadi and Shah [ITCS 2022] showing that $O(n^2/α^3)$ bits is sufficient while Dark and Konrad [CCC 2020] have shown that $Ω(n^2/α^3)$ bits is necessary. The space complexity, however, remains unresolved for many other dynamic graph streaming problems where further improvements can still be made. \end{abstract}
