From b87418eb41bdd134d26d733c31f8dd2e6cc511f3 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Sat, 19 Apr 2008 14:45:04 +0200 Subject: [PATCH] Online verification is hard. --- PLAN | 1 - adv.tex | 11 +++++++---- 2 files changed, 7 insertions(+), 5 deletions(-) diff --git a/PLAN b/PLAN index 8495bd6..bef6665 100644 --- a/PLAN +++ b/PLAN @@ -51,7 +51,6 @@ TODO: Spanning trees: - cite Eisner's tutorial \cite{eisner:tutorial} -- \cite{pettie:onlineverify} online lower bound - move the remark on disconnected graphs? separate section? - mention graphs with non-unique weights? also in the separate section? - Some algorithms (most notably Fredman-Tarjan) do not need flattening diff --git a/adv.tex b/adv.tex index fe9ad19..4221348 100644 --- a/adv.tex +++ b/adv.tex @@ -1040,14 +1040,17 @@ Buchsbaum et al.~\cite{buchsbaum:verify} have recently shown that linear-time verification can be achieved even on the Pointer machine. They first solve the problem of finding the lowest common ancestors for a~set of pairs of vertices by batch processing: They combine an~algorithm of time complexity $\O(m\timesalpha(m,n))$ -based on the Union-Find data structure with the framework of topological graph +based on the Disjoint Set Union data structure with the framework of topological graph computations developed in Section \ref{bucketsort}. Then they use a~similar technique for finding the peaks themselves. \rem -The online version of this problem (build a~data structure for a~weighted tree -in linear time and then answer queries for individual paths in constant time) -is still open even for the RAM. +The online version of this problem has turned out to be more difficult. It calls for an~algorithm +that preprocesses the tree and then answers queries for peaks of paths presented online. Pettie +\cite{pettie:onlineverify} has proven an~interesting lower bound based on the inverses of the +Ackermann's function (see \ref{ackerinv}). If we want to answer queries within $t$~comparisons, we +have to invest $\Omega(n\log\lambda_t(n))$ time into preprocessing. This implies that with +preprocessing in linear time, the queries require $\Omega(\alpha(n))$ time. %-------------------------------------------------------------------------------- -- 2.39.2