From 465f95de2891eef5f6bd63e646d74adaf9fe9b09 Mon Sep 17 00:00:00 2001
From: Marcin Chrzanowski <mc370754@students.mimuw.edu.pl>
Date: Sun, 18 Dec 2022 15:31:21 +0100
Subject: Shorten sections

---
 presentation/presentation.md | 39 +++++++++++++--------------------------
 1 file changed, 13 insertions(+), 26 deletions(-)

(limited to 'presentation')

diff --git a/presentation/presentation.md b/presentation/presentation.md
index ec491e9..9652d3d 100644
--- a/presentation/presentation.md
+++ b/presentation/presentation.md
@@ -5,17 +5,17 @@
 ## Question Answering
 
 * Fix a function $f : \mathcal{S} \times \mathcal{Q} \to \mathcal{A}$
-* A *preprocessing* algorithm that on input $S \in \mathcal{S}$ outputs an
-  indexing structure $S'$ (doesn't need to be in $\mathcal{S}$).
-* An *answering* algorithm that on input $Q \in \mathcal{Q}$, together with
-  $S'$, outputs $f(S, Q)$.
+* *preprocessing*: on input $S \in \mathcal{S}$ output an indexing structure
+  $S'$.
+* *answering*: on input $Q \in \mathcal{Q}$, $S'$ outputs $f(S, Q)$.
 
 ## Question Answering - Time Complexity
 
 * Let $n = |S|$, $m = |Q|$.
-* If the preprocessing algorithm works in time $f(n)$ and the answering
-  algorithm works in time $g(n, m)$, we notate the full algorithm's time
-  complexity as $\langle f(n), g(n, m) \rangle$.
+* Preprocessing algorithm works in time $f(n)$
+* Answering algorithm works in time $g(n, m)$
+* Notate the full algorithm's time complexity as $\langle f(n), g(n, m)
+  \rangle$.
 
 ## Example: LCA
 
@@ -46,28 +46,15 @@ singletons.
 
 # Prior Work
 
-## Naïve Solutions - Model Checking
-
-* Introduce unary relations $U_i$.
-* For question $\vec{W}$, label elements of $W_i$ with $U_i$.
-* If we can answer MSO model checking on trees in time $f(n)$, we can answer
-  questions in $O(f(n))$.
-
-## Naïve Solution - Courcelle
+## Reduce to Model Checking
 
 * Courcelle: MSO model checking over structures of bounded treewidth is
   $O_{\varphi}(n)$.
-* So we can solve MSO query answering in $\langle O(1), O_{\varphi}(n) \rangle$.
-
-## Naïve Solution - Amarilli et al.
-
-* Amarilli et al.: algorithm that preprocess a tree in time $O_{\varphi}(n)$,
-  then allows relabeling in time $O_{\varphi}(\log{n})$, answers model checking
-  in $O(1)$ for the updated tree.
-* Preprocess tree according to Amarilli.
-* For a question $\vec{W}$, run an update for each vertex in $\vec{W}$, get the
-  answer.
-* So an $\langle O_{\varphi}(n), O_{\varphi}(m \log{n}) \rangle$ solution.
+    * MSO query answering in $\langle O(1), O_{\varphi}(n) \rangle$.
+* Amarilli et al.: $O_{\varphi}(n)$ preprocessing, $O_{\varphi}(\log{n})$
+  relabeling.
+    * MSO query answering in $\langle O_{\varphi}(n), O_{\varphi}(m \log{n})
+      \rangle$.
 
 ## Kazana
 
-- 
cgit v1.2.3