12 lines
1.3 KiB
TeX
12 lines
1.3 KiB
TeX
%root main.tex
|
|
|
|
\section{$\rpoly$ cancellations due to $\bi$ constraint}
|
|
|
|
\paragraph{Problem Definition}
|
|
Since $\bi$ has the constraint that all tuples from the same block are mutually exclusive from one another, it is the case that there exist query polynomials $\poly$ such that $\rpoly$ will cancel out monomials that violate this condition. Let us assume that we have the following $\poly = \poly_1 \cdot \poly_2$, where $\poly_1 = \sum_{i = 1}^\numvar \tup^{1_i}$ and $\poly_2 = \sum{j = 1}^\numvar \tup^{2_j}$, and $\tup^{a_i}$ is a monomial as defined in \Cref{def:monomial}, i.e., every term in $\tup^{a_i}$ is a single variable factor of the monomial as opposed to allowing product of sums. Note that each $\tup^{a_i}$ has at most a degree of $k$ and that each of its variables are associated with a particular block $\block$. We can assume WLOG that each monomial $\tup^{a_i}$ has at most one variable from each block since any $\tup^{a_i}$ having non-identitcal variables from the same $\block$ can easily be pruned in a $O(\numvar)$ scan.
|
|
|
|
\paragraph{High Level Description of Solution}
|
|
We claim that we can compute the number of cancelations in $O(\numvar\cdot \log{\numvar})$ time.
|
|
|
|
Before digging into the details of computing the exact number of cancellations of $\rpoly$, we describe the high-level details of the solution.
|