%root: main.tex

\paragraph{Outline of 1st ICDT Introduction Submission}

\begin{outline}[enumerate]
	\1 Problem Introduction and Background
		\2 Set-\abbrPDB notation, concepts, common (known) results \isIncluded{I. B. vi.}
			\3 \notIncluded{Dichotomy} \isIncluded{Can be included in I. B. vi.}
			\3 Exact Computation \sharpphard \isIncluded{I. B. vi.}
		\2 Formal definition of expected result multiplicity \isIncluded{Can be included in I. C. ii. a.}
		\2 \notIncluded{Example} \isIncluded{Can be used potentially sometime after I. C. ii. a.; maybe around D.}
			\3 Assumed setting of {\emph set inputs} \isIncluded{I. D.}
			\3 \notIncluded{Example based on explaining and motivating formal definition of expected result multiplicity}
	\1 \notIncluded{Discussion of set-\abbrPDB\xplural} \isIncluded{Perhaps this might be useful around I. B. vi.}
		\2 \notIncluded{Lineage from PosBool$[\vct{X}]$}
		\2 \notIncluded{Encoding of possible worlds via $\vct{X}$}
		\2 \notIncluded{Computing probability can be done using only the lineage}
	\1 \notIncluded{Discussion of bag-\abbrPDB\xplural} \isIncluded{Might be useful around I. C.} 
		\2 \notIncluded{Link to $\domN[\vct{X}]$}
		\2 \notIncluded{Link to computing the expected count of a lineage polynomial}
		\2 \notIncluded{Example to illustrate computing an expected count over a lineage polynomial}
	\1 \isIncluded{Computing expected multiplicity for an \abbrSOP representation versus a factorized representation -- I. B. iii. and I. B. iv.}
		\2 Linear for \abbrSOP
		\2 Introduce the problem by asking if it's linear in the size of the representation for factorized representation produced by such query optimizations as projection push-down.
		\2 State our theoretical results (informally) that it is not linear in general
	\1 \notIncluded{Contributions}
		\2 \notIncluded{Hardness results for the expected multiplicity problem}
			\3 \notIncluded{Reduction to counting $\kElem$-matchings}
		\2 \isIncluded{Introduce our approximation algorithm and its guarantees -- I. B. v.}
		\2 \notIncluded{Generalization to bag-\abbrPDB\xplural}
		\2 \notIncluded{Result over $\raPlus$ queries }
		\2 \isIncluded{Higher moments I. C. e.}
	\1 \notIncluded{Overview of our techniques}
		\2 \notIncluded{Informal introduction to $\rpoly$ with example}
		\2 \notIncluded{Definition of reduced polynomial}
		\2 \notIncluded{Equivalence of $\rpoly$ and computing $\expct$}
		\2 \notIncluded{Further details into the technique of obtaining our hardness result}
	\1 \notIncluded{Paper organization}
		\2 \notIncluded{Also includes evaluation semantics figure}
\end{outline}