text:
\subsection{The Partitioned Matching Triangles Problem solves the Factored Zero Triangle Problem}

\begin{reminder}
{Theorem \ref{thm:czkc-to-ndmt}}
If (\#)Partitioned Matching Triangles (PMT) can be solved in $T(n)$ time, then we can solve (\#) \czkc[3]~in time $\tilde{O}(T(n)+n^2)$.
\end{reminder}
\begin{proof}
Let $G=(U,V,W)$ be an instance of \czkc[3], where each edge $e$ is a factored vector. For notation convenience let $uv[j]$ refer to the $j^{th}$ set of the factored vector on the edge from $u$ to $v$.

We define an instance of PMT~as a set of $g$ graphs $G_j$ for $j=1,\ldots,g$. We define $G_j$ as follows. For every $u\in U$ add a copy of $u$ in $G_j$ with color $u$. For every $v\in V$ and $w\in W$, add vertices $v_x$ and $w_x$ for all $x=-2^{b+1},\ldots,2^{b+1}$, with color $v$ and $w$ respectively. Note that since $b=o(\log{n})$, $G_j$ has $\tilde{O}(n)$ nodes.

Now we attach $u\in G_j$ to $v_x\in G_j$ if $x\in uv[j]$. We connect $v_x$ to $w_y$ if $y-x\in vw[j]$ and we connect $w_y$ to $u$ if $-y\in wu[j]$.

We prove that the \czkc[3]~instance and the PMT~instance are equivalent. For this, consider a zero triangle $uvw$, where the vectors $x_j\in uv[j]$, $y_j\in vw[j]$ and $z_j\in wu[j]$ are picked to have sum zero for each $j$. This corresponds to the triangles $uv_{x_j}w_{y_j+x_j}$ in $G_j$ for each $j$, where all these triangles are of color $(u,v,w)$. Conversely, any set of $g$ triangles of color $(u,v,w)$ in $G_j$s should be of the form $uv_{x_j}w_{y_j}$, and hence from the definition of the PMT~ instance we have that for each $j$, $x_j\in uv[j]$, $y_j-x_j\in vw[j]$ and $-y_j\in wu[j]$ and so they correspond to a zero $uvw$ triangle.
\end{proof}

\subsection{\texorpdfstring{$k$}{Lg}-Node Labeled st Connectivity is hard from Factored \texorpdfstring{Zero-$k$-Clique}{Lg}}
\input{kColorNodeLabled}

\subsection{\texorpdfstring{$k$}{Lg}-Edge Labeled st Connectivity is hard from Factored \texorpdfstring{$k$}{Lg} Function Problems \texorpdfstring{(F$k$-f)}{Lg}}
\input{kcolorEdgeLabel}

\subsection{\texorpdfstring{$(k+1)$}{Lg} Labeled Max Flow solves Factored Zero-\texorpdfstring{$k$}{Lg}-Clique}
\begin{reminder}{Theorem \ref{klmf}}
If $(k+1)$L-MF can be solved in $T(n)$ time, then we can solve \czkc~in time $\tilde{O}(T(n)+n^2)$.
\end{reminder}
\begin{proof}
We use the set gadgets from Theorem \ref{thm:knlstc-hardness} and instead of placing them serially, we make a parallel network $G'$ as shown in Figure \ref{fig:flow}. More particularly, let $SG_1,\ldots,SG_g$ be the set gadgets from Theorem \ref{thm:knlstc-hardness}. Add $s_1,\ldots,s_g$ with a source node $s$ to the graph. Add $t_1,\ldots,t_g$ with a sink node $t$ to the graph. This completes the definition of the vertices of $G'$.

We attach $s$ to all $s_j$ and all $t_j$ to $t$ with label $l^*$ for $j=1,\ldots, g$. For each $j$, we attach $s_j$ to all the nodes in the first layer of $SG_j$, which is a copy of $V_1$. Let the label of any $s_ju$ edge be $u$ where $u\in V_1$.
Connect all the nodes in the last layer of $SG_j$ to $t_j$ for all $j$. Suppose that the last layer of $SG_j$ corresponds to $V_y$. Let the label of any edge $u_yt_j$ be $u_y$. Let the label of any edge $(r,z)$ in any set gadget $SG_j$ be the same as the color of $r$, since $G'$ is supposed to be an edge-labeled graph. All the edges are unit capacitated. This completes the definition of $G'$.

\begin{figure}[ht]
    \centering
    \includegraphics[width=0.6\textwidth]{flow.pdf}
    \caption{$(k+1)$ labeled max flow instance structure.}
    \label{fig:flow}
\end{figure}

First note that the maximum flow is at most $g$ since the outdegree of $s$ is $g$ and the graph is unit-capacitated. So the flow going through each set gadget is at most $1$, which means that there is at least one path from $s_j$ to $t_j$ through $SG_j$. From Theorem \ref{thm:knlstc-hardness} any zero weight $k$-clique corresponds to $g$ paths, one in each set gadget, using $k$ labels corresponding to the $k$ vertices of the clique. So any zero weight $k$-clique corresponds to a $(k+1)$ labeled flow of size $g$ from $s$ to $t$. Conversely, if there is a $(k+1)$ labeled flow of size $g$ from $s$ to $t$, it must correspond to (at least) one path from $s_j$ to $t_j$ in $SG_j$ for each $j$ with all the $g$ paths having the same $k$ labels, which corresponds to a zero $k$-clique by Theorem \ref{thm:knlstc-hardness}.
\end{proof}

\subsection{Regular Expression Matching is hard from Factored OV}

We are going to reduce \ckov[2]~to regular expression matching. First, we define type and depth of a regular expression. Intuitively, the structure of the operations in a regular expression is called its \textit{type}, which is represented by a tree with nodes labeled with operations. Let $\bullet$ be an arbitrary operator. A tree $T$ with root node $\bullet$ means that all the first level operations of a regular expression $E$ of are $\bullet$, i.e. $E=A_1\bullet A_2\bullet\ldots\bullet A_\ell$, where $A_i$s are regular expressions. The type of each $A_i$ can be the subtree with any of the children of the root node as its root. The \textit{depth} of a regular expression is the longest root-leaf path in the type tree of the regular expression.

We reduce (\#)\ckov[2]~to (\#)regular expression matching where the pattern is a depth 5 pattern of type $T_0$ shown in Figure \ref{fig:regex-type}, and we give an $O(mn)$ algorithm for counting such patterns in $O(mn)$ time (Theorem \ref{thm:regexcounting} in the Appendix).

\begin{figure}[ht]
    \centering
    \includegraphics[width=0.3\textwidth]{regex.pdf}
    \caption{Type $T_0$ of the regular expression of Theorem \ref{thm:regex}. Where ``$|$" is the OR operator, ``$\cdot$" is the concatenation operator, and $*$ is the Kleen star operator.}
    \label{fig:regex-type}
\end{figure}

\begin{reminder}{Theorem \ref{thm:regex}}
Let $R$ be an integer where $\lg{(R)}$ is subpolynomial. If you can solve (\# mod ${R}$) regular expression matching in $T(n)$ time, then you can solve (\# mod $R$) \ckov[2]~in $\tilde{O}(T(n)+n)$ time.
\end{reminder}

\begin{proof}
We use the proof of Theorem $1$ in \cite{regularexpression} that shows hardness for patterns of type ``$|\cdot|$", where ``$|$" is the OR operator, ``$\cdot$" is the concatenation operator and the type tree is a path of length two with node $|,\cdot$ and $|$ respectively. In \cite{regularexpression} authors start with any $2OV$ instances $(A,C)$ where $A=\{a^1,\ldots,a^n\}$ and $C=\{c^1,\ldots,c^n\}$ are sets of $n$ vectors of dimension $d$ and reduce it to an instance of regular expression matching with pattern $p$ constructed from $A$ (and independent from $C$) and text $t$ constructed from $C$ (and independent from $A$) both of $O(dn)$ size, where any orthogonal pair $(a,c)$ with $a\in A$ and $c\in C$ corresponds to an alignment of $p$ on a substring of $t$, and conversely any alignment of $p$ on $t$ corresponds to an orthogonal pair $(a,c)$. More particularly, pattern $p=VG(a^1)|\ldots|VG(a^n)$ consists of the OR of vector gadgets $VG(a)=CG(a_1)\cdot \ldots \cdot CG(a_d)$ where $CG$ is a coordinate gadget and $a_i$ is the $i$th bit of vector $a$. Each coordinate gadget is aligned on a single bit. The text $t=VG'(c^1)2\ldots 2VG'(c^n)$ consists of vector gadgets $VG'(c)=c_1c_2\ldots c_d$ which is the bit representation of the vector $c$. We have that $a^i\cdot c^j=0$ iff there is an alignment of $VG(a^i)$ on $VG'(c^j)$. As a result, the number of orthogonal pairs in $(A,C)$ is the number of subset alignments of $p$ on $t$.

We use the above construction for our factored vectors. Note that if $w$ is a factored vector, for any $j\in \{1,\ldots,g\}$ we can construct a pattern (or a text) of length $O(|w[j]|b)$ using the vectors in $w[j]$ which have length $b$.

Consider an instance $(U,V)$ of \ckov[2]~where $U=\{u^1,\ldots,u^n\}$ and $V=\{v^1,\ldots,v^n\}$ are sets of $n$ factored vectors. We construct the pattern $P$ using $U$ and the text $T$ using $V$. We first construct the pattern. Let $p_i[j]$ be the pattern corresponding to $u^i[j]$ using the construction of \cite{regularexpression} for  $i=1,\ldots,n$ and $j=1,\ldots,g$. Note that the symbols used in $p_i[j]$ are $0,1$. Let $p'_i[j]=[0|1|2]^*\cdot p_i[j]\cdot [0|1|2]^*$, where ``$*$" is the Kleen star operator.
Define the ``pattern factored vector gadget" $PVG(i)$ for $u^i$ as follows:
$$
PVG(i)=p'_i[1]\cdot 3\cdot p'_i[2]\cdot 3\cdot \ldots \cdot 3 \cdot p'_i[g]
$$
Let the pattern $P$ be the following:
$$
P=PVG(1)|PVG(2)|\ldots|PVG(n)
$$
Note that the length of $P$ is $\tilde{O}(n)$, since we have that  $|p_i[j]|=O(|u^i[j]|)=O(2^b.b)=o(n)$, $|p'_i[j]|=O(p_i[j])$ and the number of occurrence of the symbol $3$ is $(g-1)n$. The number of symbols in a $*$ expression is also $O(gn)$ since the number of $*$ expressions is $2ng$. So the total number of symbols in $P$ is $\tilde{O}(n)$, and as a result the length of $P$ is $\tilde{O}(n)$.

Now we construct the text. Let $t_i[j]$ be the text corresponding to $v^i[j]$ using the construction in \cite{regularexpression} for $i=1,\ldots,n$ and $j=1,\ldots,g$.  Note that the symbols used in $t_i[j]$ are $0,1,2$. Define the ``text factored vector gadget" $TVG(i)$ for $v_i$ as follows:
$$
TVG(i)=t_i[1]3t_i[2]3\ldots 3t_i[g]
$$
Let the pattern $T$ be the following:
$$
T=TVG(1)4TVG(2)4\ldots 4TVG(n)
$$
Similar to $P$, the length of $T$ is $\tilde{O}(n)$.

Now we have to show that there is a one to one correspondence between orthogonal vectors in the \ckov[2]~instance and the number of subset alignments of $P$ on $T$. First consider an orthogonal pair $(u_i,v_j)$, where for each $k=1,\ldots,g$ the vector chosen from $u^i[k]$ is the $r_k$th vector $u^i[k][r_k]$, and the vector chosen from $v^j[k]$ is the $s_k$th vector $v^j[k][s_k]$. So we have that for each $k$, $u^i[k][r_k].v^j[k][s_k]=0$. This means that there is a subset alignment of $p_i[k]$ on $t_j[k]$ corresponding to $u^i[k][r_k]$ and $v_j[k][s_k]$ for all $k$. We use the $[0|1|2]^*$ parts of $p'_i[k]$ to cover the rest of $t_j[k]$ and thus we get a full alignment of $p'_i[k]$ on $t_j[k]$. Having these alignments for each $k$, they extend uniquely to a full alignment of $PVG(i)$ on $TVG(i)$.

Conversely, suppose that there is a subset alignment of $P$ on $T$. Note that the first level of the pattern consists of ORs, so any alignment should choose some $i\in \{1,\ldots,n\}$ and align $PSG(i)$ on $T$. On the other hand, symbol $4$ is not used in the pattern $P$. So $P$ should be aligned on $TSG(j)$ for some $j$. So assume that in this subset alignment, $PSG(i)$ is aligned on $TSG(j)$. Since there are exactly $g-1$ symbols ``$3$" that are concatenated in $PSG(i)$ and there are exactly $g-1$ symbols ``$3$" in $TSG(j)$, the $3$s should be aligned to each other. So $p'_i[k]$ is fully aligned to $t_j[k]$. Recall that $p'_i[k]=[0|1|2]^*\cdot p_i[k]\cdot [0|1|2]^*$. So $p_i[k]$ should be aligned to $t_j[k]$. So by the construction of \cite{regularexpression} there are unique $r_k$ and $s_k$ where the vector gadget for $u^i[k][r_k]$ is fully aligned to the vector gadget for $v^j[k][s_k]$, which means that these two vectors are orthogonal. Since this is true for every $k$, $u^i$ and $v^j$ are orthogonal, and hence the number of factored orthogonal vectors in the \ckov[2]~instance equals to the number of subset alignments of $P$ on $T$.
\end{proof}

\subsection{Longest Common Subsequence and Edit Distance}
\label{subsec:lcs}
\input{lcs}
\subsection{Graphs}

\subsection{Algorithms for Factored Problems}
\label{subsubsec:WCReductionsCompressed}

These algorithms are straightforward be case they are simply brute force.

\begin{lemma}
\ckfunc[]~can be solved in $\tilde{O}(n^k)$ time.
\end{lemma}
\begin{proof}

For \ckfunc[], we want to run $\circledcirc(v_1,\ldots,v_k)$ on every set of $k$ vectors.
To do this we need to compute $\circ(v_1[i],\ldots,v_k[i])$ for all $i \in [0,g]$. Running $\circ(\cdot)$ takes $O( \Pi_{j\in[1,k]}|v_j[i]|)$ time. We can use the upper bound $|v_j[i]| \leq 2^b$. So computing $\circ(\cdot)$ takes at most $O(2^{bk})$ time. Thus, computing $\circledcirc(\cdot)$ takes at most $O(g \cdot 2^{bk})$.

Thus, computing \ckfunc[]~ takes at most $O(n^k \cdot g \cdot 2^{bk})$ time. We bounded $g$ and $b$ to be $o(\lg(n))$ so $g \cdot 2^{bk}$ is subpolynomial.
Thus, \ckfunc[]~ takes at most $\tilde{O}(n^k)$ time.
\end{proof}

\begin{lemma}
\cfkc[]~(\#\cfkc[]) can be solved in time $\tilde{O}(n^k)$.
\end{lemma}
\begin{proof}
For every $k$ tuple of nodes in the graph we want to evaluate $\circledcirc( \cdot )$. If we can evaluate $\circledcirc( \cdot )$ in $\tilde{O}(1)$ time then we can count or detect in  $\tilde{O}(n^k)$ time.

Evaluating $isClique(\cdot) $ can be done in $\tilde{O}(1)$ time. Evaluating the multiplication, given the results of the function $\circ(\cdot)$ can be done in $\tilde{O}(g)$ time.
Evaluating $\circ(\cdot)$ should require at most $\tilde{O}(2^{\binom{k}{2}b})$ time as the function $f$ has a total truth table size of $2^{\binom{k}{2}b}$ and we simply need to evaluate how many entries of the truth table are $1$ while we simultaneously have that vector.

Finally, we note that $g = \tilde{O}(1)$ and $2^{\binom{k}{2}b} = \tilde{O}(1)$. So evaluating $\circledcirc( \cdot )$ can be done in $\tilde{O}(1)$ time.
\end{proof}

\subsection{Algorithms for Problems Harder than Factored Problems }
\begin{theorem}
Counting partitioned matching triangles  (\#PMT) can be solved in $\tilde{O}(n^3)$ time.
\end{theorem}
\begin{proof}
Let the $g$ graphs be $G_1,\ldots,G_g$ in our PMT~instance, and let $n_r^j$ be the number of nodes of color $r$ in $G_j$. For all triple of colors $(c_1,c_2,c_3)$ and all $j$, we count the number of
triangles of these colors in $G_j$. We can do this by inspecting every triple of nodes of color $(c_1,c_2,c_3)$ in time $n_{c_1}^jn_{c_2}^jn_{c_3}^j$. Since $\sum_r n_r^j=n$ for all $j$, we have that $\sum_{j=1}^g \sum_{(c_1,c_2,c_3)} n_{c_1}^jn_{c_2}^jn_{c_3}^j = O(gn^3)=\tilde{O}(n^3)$.
\end{proof}

\begin{theorem}
(Counting mod $R$) \kNLstC~has a $\tilde{O}(|C|^k + |C|^{k-2}|E|)$ time algorithm for all $k\geq 2$ (when $\lg(R)$ is sub-polynomial).
\label{thm:algForknlstc}
\end{theorem}
\begin{proof}
We can guess the $k$ colors and use BFS to discover if s is connected to t. This takes $O(|E|)$ time.

If we are counting instead of detecting paths from $s$ to $t$ then we want to extend the BFS approach by associating an additional number to each node. Every node will keep a value of the number of paths from $s$ to that node  mod $R$. These numbers will require a sub-polynomial number of bits to represent as $\lg(R)$ is bounded to be subpolynomial. In a layered graph we can compute the number of paths from $s$ to a node $v$ in layer $i$ by summing the number of paths from $s$ to $u$ for all $u$ that are neighbors of $v$ that are in layer $i-1$. We can go through the graph by computing these numbers layer by layer staring at layer $L_0$. This also takes $O(|E|)$ time.

Let $E_{c_i,c_j}$ be the set of all edges between nodes of colors $c_i$ and $c_j$. Let $E_{s,c_i}$ be the set of all edges between $s$ and nodes with color $c_i$. Let $E_{t,c_i}$ be the set of all edges between $t$ and nodes with color $c_i$.

Our running time is:
$$\sum_{c_1, c_2,\ldots,c_k \in C} \left( \left( \sum_{i\in [1,k]} |E_{s,c_i}|+ |E_{t,c_i}|\right) + \sum_{i,j \in [1,k]} |E_{c_i,c_j}|\right). $$

We know that $|E_{s,c_i}|+|E_{t,c_i}| \leq 2$ from the problem definition. We also know that $|E_{c_i,c_i}| =0$. So we can simplify to:
$$\tilde{O} \left( k|C|^k + k^2 \sum_{c_1, c_2,\ldots,c_k \in C} |E_{c_1,c_2}| \right). $$
Then we can use the fact that $\sum_{c_1,c_2 \in C} |E_{c_1,c_2}| = |E|$ and that $k$ is a constant to get:
$$\tilde{O} \left( |C|^k + |C|^{k-2}|E|\right). $$
\end{proof}

\begin{theorem}
There is an algorithm for (counting mod $R$) \kELstC[]~that runs in time $\tilde{O}(|C|^{k-1}|E|)$ (when $\lg(R) =n^{o(1)}$).
\label{thm:kelstcALG}
\end{theorem}
\begin{proof}
We do an exhaustive search for all $k$ colors. Once we guess $k$ colors $c_1, \ldots ,c_k$ then we simply run a $O(|E|)$ time algorithm for (directed/undirected) reachability on this input. If we are counting paths mod $R$ then we use the fact that the graph is a directed acyclic graph to count the number of paths from $s$ to every node, so we can go through a normal breadth first search but keeping the count mod $R$. Because $\lg(R) = n^{o(1)}$ we can track these sums in sub-polynomial time.

We start by sorting our edges by their color (so that given a guess of colors we can in $k \lg(n)$ time give pointers to the full set of all edges of that color). Let $e(c)$ be the number of edges of color $c$. Then our running time can be given as:
$$\sum_{c_1,\ldots,c_k \in [1,|C|]} e(c_1) + \ldots + e(c_k) + k\lg(n).$$
Consider a particular one of the additive parts of this sum: $\sum_{c_1,\ldots,c_k \in [1,n]} e(c_i).$ This can be re-written as:
$$\sum_{c_1,\ldots, c_{i-1}, c_{i+1}, \ldots ,c_k \in [1,|C|]} \left( \sum_{c_i \in [1,|C|]} e(c_i) \right).$$
Which is
$$\sum_{c_1,\ldots, c_{i-1}, c_{i+1}, \ldots ,c_k \in [1,|C|]} |E| = |C|^{k-1}|E|.$$

So the total running time is $k |C|^k + k|C|^{k-1} |E| \lg(R) \lg(n) + |E|\lg(n)$. The $k |C|^k$ time comes from running all of our small instances.  The $k \lg(n)$ coming from the need to give pointers into where our $k$ colors of edges are stored. The factor of $\lg(R)$ comes from tracking the count mod $R$ in the counting version.  And finally, the $|E|\lg(n)$ comes from sorting our edges according to color.
\end{proof}

\begin{theorem}
There is an algorithm for detecting $(k+1)$L-MF* on an $n$-node graph that runs in $\tilde{O}(n^k)$ time.
\end{theorem}
\begin{proof}
First we run a max flow algorithm on the graph to obtain the value $|F|$ of the max flow. Since the graph is unit-capacitated, this can be done in $O(n\sqrt{m})=O(n^2)$ time.

Recall that the edges connected to the source $s$ and the sink $t$ have a special label $l^*$. So this label must be among the $k+1$ labels. Now for any choice of $k$ labels $l_1,\ldots,l_k$, we consider the subgraph induced on the edges with labels in $l_1,\ldots,l_k,l^*$, and we run a max flow algorithm on this graph. If the max flow value on this graph equals $|F|$, we are done. Otherwise if all these graphs have maximum flow less than $|F|$, there is no max flow with $k+1$ labels. Note that the max flow in each small graph takes $o(n)$ time since for each label the number of edges with that label is $o(n)$.
\end{proof}

Now we turn to regular expressions matching problem, and state an efficient algorithm for counting the number of alignments of the pattern on sub-strings of the text. First we state two lemmas.

\begin{lemma}
\label{lem:nfa-fast}
Let $M$ be an NFA with no cycles of length more than $1$. Let a computation of a string $t$ in $M$ be a sequence of states from the start state to the accept state of $M$ that produces $t$.
Then given a text $T$ and a fixed integer $R$ where $\log{R}$ is sub-polynomial, there is an algorithm that computes the number of computations of substrings of $T$ in $M$ mod $R$ in $O(m|T|)$ time, where $m$ is the number of edges of $M$.
\end{lemma}

\begin{proof}
All numbers are taken mod $R$. Let $Q$ be the set of states of $M$, and let $\Delta: Q \times \Sigma\rightarrow P(Q)$ be the transition function of $M$, where $\Sigma$ is the alphabet, and $P(Q)$ is the power set of $Q$. Recall that we have an edge from state $s$ to state $s'$ if $s'\in \Delta(s,\sigma)$ for $\sigma \in \Sigma \cup \{\epsilon\}$,
where $\epsilon$ is the empty string. Note that for any state $s\in Q$, $s\notin \Delta(s,\epsilon)$. We can assume that there is only one accept state with no outgoing edge (and hence no self-loops).

Since $M$ has no cycles other than self-loops, it has a topological ordering $s_1,s_2,\ldots,s_r$ where $s_1$ is the start state, $s_r$ is the accept state, $r$ is the number of states of $M$ and there is no edge from state $s_i$ to $s_j$ if $i>j$. We compute the number of computations of substrings of $T$ in $M$ by dynamic programming. Let $|T|=n$, and let $T_i$ be the postfix of $T$ starting at $i$ for $i=1,\ldots,n+1$, where $T_{n+1}$ is the empty string. Let $M_i$ be the NFA obtained from $M$ by having $s_i$ as the start state.
For $i = 1,\ldots,r$ and $j=1,\ldots,|T|$, let $f(i,j)$ be the number of computations of prefixes of $T_j$ by $M_i$. So $\sum_{j=1}^n f(1,j)$ is what we have to compute.

As the base case, we have that $f(r,n+1)=1$. Let $N_{out}(s_i)$ be the set of outgoing neighbors of $s_i$, i.e. we have that $s_j\in N_{out}(s_i)$ if there is an edge from $s_i$ to $s_j$. Similarly we define $N_{in}(s_i)$ to be the set of incoming neighbors of $s_i$.

Fix $i,j$. Suppose that we have computed $f(i',j')$ for all $i'\ge i$ and $j'\ge j$ where $i'+j'>i+j$. We compute $f(i,j)$ as follows.
$$
f(i,j)=\sum_{s_{\ell}\in \Delta(s_i,T[j])} f(i+1,\ell) + \sum_{s_\ell\in \Delta(s_i,\epsilon)} f(i,\ell)
$$
Note that $s_i\notin \Delta(s_i,\epsilon)$, so we can compute this sum, which takes $O(|N_{out}(s_i)|)$ to compute. Hence the computation of all $f(i,j)$s takes $O(mn)$ time.
\end{proof}

\begin{lemma}
\label{lem:regex-has-nfa}
If $E$ is a regular expression of the type $T_0$ (see Figure \ref{fig:regex-type}), there is an NFA equivalent to $E$ that has no cycle of length more than $1$. This MFA has $O(|E|)$ edges.
\end{lemma}
\begin{proof}
Let a sub-type of a regular expression type $T$ be a type shown by a sub-tree of the tree of $T$. We show that for any regular expression of type $T_0$ or any sub-type of $T_0$, there is an NFA equivalent to $E$ that has no cycle length more than $1$. Recall that $\epsilon$ is the empty string.

So let $E$ be a regular expression of any sub-type of $T_0$. We construct the NFA of $E$ in a recursive manner. As the base case, suppose that $E$ has length $1$. So it consists of only one symbol $a$, for which a two state NFA suffices: Let $s_1$ be the starting state and $s_2$ be the accept state, and let $e$ be an edge from $s_1$ to $s_2$ with value $a$ (equivalently, the transition function $\Delta$ is $\Delta(s_1, a)=\{s_2\}$).

If $E$ has length more than $1$, it is of the form $A\bullet B$ or $A*$, where $\bullet$ is one of the operators concatenation ($``\cdot"$) or OR ($``|"$), and $A$ and $B$ are two regular expressions of a sub-type of $T_0$. Let $M_A$ and $M_B$ be the NFAs corresponding to $A$ and $B$ respectively, with $s_A,s_B$ as the corresponding start states and $t_A,t_B$ as the corresponding accept states.

So we have three cases:

\begin{enumerate}
    \item Concatenation: suppose that $\bullet=\cdot$. Define $M$ to be the MFA that consists of $M_A$ and $M_B$, with an edge added from $t_A$ to $s_B$ with value $\epsilon$. Let $s_A$ be the start state of $M$ and $t_B$ be the accept state of $M$.
    \item Or: suppose that $\bullet=|$. Let $s$ be a new state, which has an edge of value $\epsilon$ to $s_A$ and $s_B$. Mark $s$ as the start state of $M$. Let $t$ be a new state, where there is an edge from $t_A$ and $t_B$ to $t$ with value $\epsilon$. Let $t$ be the accept state.
    \item Star: Suppose that $E=A^*$. Since $E$ is of a subtype of $T_0$, $A$ must be of type $``|"$. So it is the OR of some symbols. Let the set of these symbols be $Q_A$. Then define $M$ to have $3$ states, $s_E$ as the start state, $t_E$ as the accept state, and $s$ as a middle state where there is a self-loop from $s$ to itself with all symbols in $Q_A$ as its values, an edge from $s_A$ to $s$ and an edge form $s$ to $t_A$ with empty string $\epsilon$ as their value.
\end{enumerate}
It is straightforward to see that this NFA is equivalent to $E$, so that each alignment of $E$ on a text is equivalent to a computation of the text by the NFA $M$. Note that in each case we add $O(1)$ edges. So the total number of edges is $O(|E|)$.
\end{proof}

Combining Lemma \ref{lem:nfa-fast} and \ref{lem:regex-has-nfa} gives us the following Theorem.

\begin{theorem}
\label{thm:regexcounting}
Given a regular expression $E$, a text $T$ and a fixed integer $R$ where $\log{R}$ is sub-polynomial, there is an algorithm that counts the number of alignments of $E$ on substrings of $T$ mod $R$ in $O(|T||E|)$ time.
\end{theorem}

\begin{theorem}
\label{thm:algKWLCS}
There is an algorithm for \#\kwlcs~mod $R$ which runs in $\tilde{O}(n^k)$ time when $\lg(R) = o(\lg(n))$.
\end{theorem}
\begin{proof}
Take $P_1, \ldots, P_k$ to be the input sequences. Recall that $w(P_\ell[i])$ is the weight of the symbol at position $i$ in the $\ell^{th}$ string.

We will use dynamic programming. We will have a cell in our table for every $k$ tuples of locations in the strings $i_1, \ldots, i_k$. Every cell will contain two pieces of information:
\begin{itemize}
    \item $\ell(i_1,\ldots, i_k)$ the length of the longest common subsequence(s) of the substrings $P_1[:i_1], \ldots, P_k[:i_k]$.
    \item $C(i_1, \ldots, i_k)$ is the count of the number of longest common subsequences mod $R$. This will have a $n^{o(1)}$ bit representation due to our restriction on $R$.
\end{itemize}

We start by initializing all cells associated with locations $i_1, \ldots, i_k$ where any $i_j=0$. These cells are initialized to $\ell(i_1,\ldots, i_k)=0$  and $C(i_1, \ldots, i_k)=1$, as there is only one way to have a zero length string.

Let the total sum of a cell be $\sum_{j=1}^k i_j$, we will fill cells out in order by there total sum, starting with zero and moving to $kn$. Any cell that has a $i_j$ value equal to zero will be left with its initialization.

When filling the cell there are two cases: when $P_1[i_1]=P_2[i_2]= \ldots = P_k[i_k]$, and when that isn't true. We define some helpful notation. Let $\vec{v} =i_1, \ldots, i_k $ and let $eq_\ell(\vec{v},\vec{u})$ be a function that returns $1$ if $\ell(\vec{v}) = \ell(\vec{u})$. Let $\vec{v}_{(-1)}$ be the vector $i_1-1, \ldots, i_k-1$. Let $S(\vec{v})$ be a set of all vectors $\vec{u}$ such that for all indices $j$ we have that $\vec{u}[j] = \vec{v}[j] + \{0,-1\}$ excluding $\vec{v}$ and $\vec{v}_{(-1)}$. So all the smaller neighboring vectors of $\vec{v}$, excluding the strictly smaller vector (note these may differ from $\vec{v}$ in $1, 2, \ldots, k-1$ locations). By our order of computation all cells associated with $S(\vec{v})$ and $\vec{v}_{(-1)}$ will have been computed by the time we are computing the cell $\vec{v}$.

\textbf{
We will start with the case where  $P_1[i_j]\ne P_2[i_{j'}]$.} Our length is the maximal length seen so far.
$$\ell(i_1,\ldots, i_k) = \max_{\vec{u} \in S(\vec{v})}\left(\ell(\vec{u})\right).$$
This is maximizing over all possible previous choices of longest common subsequence. We know our current last symbols can't all be included in the LCS.

For setting $C$:
We want to look only at entries that are longest common subsequences, so naively you might think to just sum all the counts from the earlier cells that hit our max length of $\ell(\vec{v})$. But, we will have an inclusion exclusion issue. Consider the case of $k=2$, i.e. $2$-LCS. If $C(i-1,j)= x$, $C(i,j-1)= y$, and $C(i-1,j-1)= z$ then $C(i,j) = x+y-z$. This is because $x$ captures both all the longest sequences between $P_1[:i-1]$ and $P_2[:j-1]$ as well as those that use the symbol in location $P_1[i]$. The parallel statement is true for $y$. So we are double counting those longest common subsequences that appear in both $P_1[:i-1]$ and $P_2[:j-1]$, so we subtract out that double counting. In order to handle this smoothly we will define a more involved version of $S(\vec{v})$. Let $S_r(\vec{v})$ contain the subset of vectors $\vec{u} \in S(\vec{v}) \cup \vec{v}_{(-1)}$ where $\left(\sum_{j=1}^k \vec{v}[j]\right)-\left(\sum_{j=1}^k \vec{u}[j]\right) = r$. So $S_r(\vec{v})$ is the set of vectors that have $r$ indices that are smaller than $\vec{v}$. Now, after all this lead up, our value for $C$ is the following:
$$C(\vec{v}) = \sum_{r=1}^{k} (-1)^r \sum_{\vec{u}\in S_r(\vec{v})}  eq_{\ell}(\vec{v},\vec{u})C(\vec{u}).$$
We need to mod this by $R$ so that the total bits in the representation is not too large.

So in $\tilde{O}(2^kR)$ time per cell we can compute \#\klcs. There are a total of $n^k$ cells so the total time for this algorithm is $\tilde{O}(n^k)$.

\textbf{
Now we will deal with the case of $P_1[i_1]=P_2[i_2]= \ldots = P_k[i_k]$.} First let us set $\ell(\cdot)$:
$$\ell(i_1,\ldots, i_k) = \ell(i_1-1,i_2-1,\ldots, i_k-1) +w(P_1[i_1]).$$
This works because we have a matching symbol. Our new longest common subsequence at this location will have a length one longer than the longest sequence that existed using none of the current symbols.

For setting $C$:
We want to count two non-overlapping sets. One set is the weighted longest common subsequences at location $\vec{v}_{(-1)}$. The other set is all the strings that use some but not all of the symbols from our current location $\vec{v}$. For counting this we need inclusion exclusion like before.
$$C(\vec{v}) = C(\vec{v}_{(-1)}) + \sum_{r=1}^{k} (-1)^r \sum_{\vec{u}\in S_r(\vec{v})}  eq_{\ell}(\vec{v},\vec{u})C(\vec{u}).$$
This counts all longest sequences that include the current symbols indicated by $\vec{v}$ by including the count of $C(\vec{v}_{(-1)})$, it also counts all alternate ways to achieve a longest common subsequence of this length using at least one of these symbols by the summation. We need to mod this by $R$ so that the total bits in the representation is not too large.
\end{proof}

\begin{corollary}
\label{cor:algKLCS}
There is an algorithm for \# \klcs~mod $R$ which runs in $\tilde{O}(n^k)$ time when $\lg(R) = o(\lg(n))$.
\end{corollary}
\begin{proof}
The \#\klcs~problem is a special case of \#\kwlcs~problem where $w(\cdot)$ is the constant function that returns $1$.
\end{proof}
\subsection{Factored Versions are Harder}
\label{subsec:compressedVsUncompressed}

Consider any problem where we have $k$ sets of vectors $V_1,\ldots,V_k$ and we want to compute the number of $k$-tuples of vectors $v_1\in V_1,\ldots, v_k\in V_k$ of length $l=bg$, such that $\hat{f}(v_1,\ldots,v_k)=1$, for some function $\hat{f}:\{0,1\}^{l\times k}\rightarrow \{0,1\}$. Call this problem $k$-$\hat{f}$. Note that \ksum, $k$XOR, and $k$OV are examples of such problems. We show that these problems can be solved using their factored version.

For any vector $v$ of length $bg$ and for any $j=1,\ldots,g$, let $v^j$ be the subvector of $v$ that starts at the $(j-1)b+1$th bit and ends at the $jb$th bit. Suppose that there is a function $f:\{0,1\}^{b\times k}\rightarrow \{0,1\}$ such that $\hat{f}(v_1,\ldots,v_k)=1$ if and only if $\Pi_{j=1}^g f(v_1^j,\ldots,v_k^j)=1$. We call $f$ the factored version of $\hat{f}$. In other words, the function $\hat{f}$ can be applied more locally, on subvectors of length $g$. Note that for most problems including the problems we work with, this property holds.

Now we can easily reduce $k$-$\hat{f}$ to \ckfunc[]. Let the resulting \ckfunc[]~instance be the following: For any $bg$ length vector $v$ in the $k$-$\hat{f}$ instance, let the factored version of $v$ have sets $v[j]=\{v^j\}$. By the property mentioned, it is straightforward to see that this instance of \ckfunc[]~is equivalent to $k$-$\hat{f}$.

For the \ksum~problem it is less obvious how to solve it with \cksum[]. For the \ksum~problem we can use the nearly linear hash functions to reduce all numbers to the range $[-n^k,n^k]$ \cite{Patrascu10}. Additionally, we can reduce \ksum~in the range $[-n^k,n^k]$ to a version where every number is instead a vector with $g$ numbers with $b$ bits each \cite{losingWeight}, where $g \cdot b = k \lg(n)$. We consider a sum of $k$ vectors to be a zero sum if the vectors sum to the zero vector. To ask if $k$ numbers of length $k\lg(n)$ sum to zero, we can instead ask if $k$ vectors sum to the zero vector where the vectors have length $g$ and the numbers are each $b$ bits. But, we need to guess the $g-1$ carries, this is a total of $O(k^g)$ guesses. If $g = o(\lg(n))$ this is sub-polynomial, and so we can go through all these guesses. This vectorized version of the \ksum~problem can be directly solved by \cksum[]~as mentioned above.

Similar to the approach for solving $k$-$\hat{f}$ problems using \ckfunc[], we can reduce Z$k$C to \czkc. Here the function $\hat{f}$ (which is the sum function) gets $\binom{k}{2}$ vectors as input instead of $k$ vectors, and these vectors should have the property that they form the edges of a $k$-clique in the graph. If $f$ is the factored version of $\hat{f}$, then we have that $\hat{f}(e_1,\ldots,e_{\binom{k}{2}})=1$ and $e_1,\ldots ,e_{\binom{k}{2}}$ are the edges of a $k$-clique if and only if $\Pi_{j=1}^g f(e_1^j,\ldots,e_{\binom{k}{2}}^j)=1$ and $e_1,\ldots e_{\binom{k}{2}}$ are edges of a $k$-clique. So again, the \czkc~instance that is equivalent to the Z$k$C instance is that for each vector $e$ of an edge, we let $e[j]=\{e^j\}$.
So we have the following theorem. Note that our reductions form a one-to-one correspondence between each solution in a $k$-$\hat{f}$ instance and the corresponding \ckfunc[]~instance, and hence they work for the counging version of our problems as well.

\begin{reminder}{Theorem \ref{thm:unfactoredToFactored}}
In $O(n)$ time, one can reduce an instance of size $n$ of $k$-OV, $k$-XOR, $k$-SUM and Z$k$C to a single call to an instance of size $\tilde{O}(n)$  of \ckov[], \ckxor[], \cksum[]~and \czkc~respectively.
\end{reminder}
\begin{proof}
We can split a number or vector in the original problem into a vector with $g$ numbers of length $b$. This reduction step is trivial for \kOV, Z$k$C, and \kXOR. To be explicit:
\begin{itemize}
    \item \kOV: Let $d = o(\lg^2(n))$ be the dimension. Given $k$ lists of $n$ vectors $L_1,\ldots,L_k$ we will produce $k$ lists of factored vectors $L_1',\ldots,L'_k$. Let $v[x:y]$ be a vector formed by taking all the bits from $x^{th}$ bit to the $y^{th}$ bit. For every vector $v_i \in L_i$ take the vector $v_i[bj +1, b(j+1)] = v_i^j$ where $b = \sqrt{d}$ and $j \in [1,g]$ where $g = \sqrt{d}$. We create a factored vector $v_i'$ from $v_i$ by creating a vector where the $j^{th}$ subset of $\{0,1\}^b$ is just a set with the single vector $v_i^j$.
    \item \kXOR: There is a random reduction for \kXOR~which shrinks the vectors to length $d=k\lg(n)$ bits. Given two lists of $n$ vectors $L_1$ and $L_2$ we will produce two lists of factored vectors $L_1'$ and $L_2'$. Let $v[x:y]$ be a vector formed by taking all the bits from $x^{th}$ bit to the $y^{th}$ bit. For every vector $v_i \in L_i$ take the vector $v_i[bj +1, b(j+1)] = v_i^j$ where $b = \sqrt{d}$ and $j \in [1,g]$ where $g = \sqrt{d}$. We create a factored vector $v_i'$ from $v_i$ by creating a vector where the $j^{th}$ subset of $\{0,1\}^b$ is just a set with the single vector $v_i^j$.
    \item Z$k$C~and \ksum: We reduce the range of numbers with linear hash functions to the range $[-n^k,n^k]$. We want to split each $k\lg(n)$ bit number into $g=\sqrt{k\lg(n)}$ numbers length $b = \sqrt{k\lg(n)}$ bits. If we guess all $g$ caries then we can replace the question of if $k$ (${\binom{k}{2}}$) numbers sum to zero to if $g$ sets of $k$ (${\binom{k}{2}}$) numbers each sum to zero (see \cite{losingWeight}). So, for all $O(k^{g})$ possible guesses of carries we form a factored vector for an edge by having $g$ subsets of $\{0,1\}^b$ that each have one number. The $j^{th}$ set has the $j^{th}$ number created by splitting the original number (possibly updated by our guess of the carry).

\end{itemize}
\end{proof}

\subsection{Worst-Case to Average-Case Reductions for Factored Problems}
\label{subsec:WCtoACforCompressed}

We will use our framework from Section \ref{sec:Framework}
 to show that these factored versions are as hard on average as they are in the worst case.

  \paragraph{\#\ckfunc[]}

We give a polynomial for \#\ckfunc[]. We represent every factored vector $v$ with $g2^b$ variables. The variable $x_{v[i]}(\vec{s})$ is a $1$ if $s \in v[i]$ and $0$ otherwise. We create such a variable for all $i \in [0,g-1]$ and all $s \in \{0,1\}^b$.
 Let $S_f$ be the subset of $k$ tuples of vectors in  $\{0,1\}^b$ such that $f(s_1,\ldots,s_k)=1$.

 $$f_{ckfunc}(\vec{X}) = \sum_{v_1 \in V_1, \ldots, v_k \in V_k} \left( \prod_{i \in [0,g-1]} \left( \sum_{(s_1,\ldots, s_k)\in S_f}  x_{v_1[i]}(\vec{s_1}) \cdots x_{v_k[i]}(\vec{s_k}) \right) \right).$$

 \begin{lemma}
 $f_{ckfunc}(\vec{X})$ is a \gPol{\#\ckfunc[]}
 (see Definition \ref{def:goodPoly}
 \label{lem:funcIsGoodPol}
 \end{lemma}
 \begin{proof}
 We will show that each property of a good polynomial is met by $f_{ckfunc}$.
 \begin{itemize}

    \item \textit{If $\vec{I} = b_1,\ldots, b_n$, then
    $f_{ckfunc}(b_1,\ldots, b_n) = f_{ckfunc}(\vec{I})=P(\vec{I})$ where $b_i$ maps to either a zero or a one in the prime finite field}: $f_{ckfunc}$ and \#\ckfunc[]~count the same thing. Note that the inner summation is computing $\circ_f$, the product is computing $\circledcirc_f$. Thus the overall sum is computing \#\ckfunc[].
    \item \textit{The function $f_{ckfunc}$ has degree $d = o\left( \lg(n)/\lg\lg(n) \right)$:} $f_{ckfunc}$ has degree $kg$ which, when $k$ is constant is $o(\lg(n)/\lg\lg(n))$ by the definition of $g$.
    \item \textit{The function $f_{ckfunc}$ is strongly $d$-partite:} Every monomial is formed by exactly one copy of a $x_{v_j[i]}(\vec{s})$ variable for every $j \in [0,g-1]$ and $i\in[1,k]$. These form our partitions and make the function strongly $kg$ partite.
\end{itemize}
\end{proof}

 Now we can say that the average case version of \#\ckfunc[]~is as hard as the worst case version.

\begin{reminder}{Theorem \ref{thm:worstToAvgckf}}
Let $\mu$ be a constant such that $0 < \mu <1$.
If average-case \#\ckfunc[]$^{\mu}$~(see Definition \ref{def:muavgCasefactored}) can be solved in time $T(n)$ with probability $1-1/(lg(n)^{kg}\lg\lg(n)^{kg})$  then worst-case \#\ckfunc[]~can be solved in time $\tilde{O}(T(n))$ \footnote{Note that given that $g= o(\lg(n)/\lg\lg(n)) $ then a probability of $1-1/n^{\epsilon}$ will be high enough for any $\epsilon>0$.}.

When $\mu =1/2$ average-case \#\ckfunc[]$^{\mu}$ is average-case \#\ckfunc[].
\end{reminder}
\begin{proof}
This follows from Theorem \ref{thm:framework} and Lemma \ref{lem:funcIsGoodPol}. The dimension of the \gPol{\#\ckfunc[]} is $kg$. By our construction of $f_{ckfunc}$ every set has every possible string as a variable. By the construction of the framework from theorem \ref{thm:framework}, every bit will be selected as a $1$ uniformly at random with probability $\mu$. So, given the construction of $f_{ckfunc}$ every set will have every possible string included with probability $\mu$. So the distribution induced by our framework matches our defined average-case distribution.

Finally by definition \ref{def:avgCaseFactored} when $\mu =1/2$ average-case \#\ckfunc[]$^{\mu}$ is average-case \#\ckfunc[].
\end{proof}

\begin{reminder}{Corollary \ref{cor:worstToAvg}}
By Theorem \ref{thm:worstToAvgckf}, we have the following result:

If average-case \#\ckov[]~can be solved in time $T(n)$ with probability $1-1/(lg(n)^{gk}\lg\lg(n)^{gk})$  then worst-case \#\ckov[]~ can be solved in time $\tilde{O}(T(n))$ \footnotemark[\value{footnote}].

If average-case \# \cksum[]~can be solved in time $T(n)$ with probability $1-1/(lg(n)^{gk}\lg\lg(n)^{gk})$  then worst-case \# \cksum[]~can be solved in time $\tilde{O}(T(n))$ \footnotemark[\value{footnote}].

If average-case \# \ckxor[]~can be solved in time $T(n)$ with probability $1-1/(lg(n)^{gk}\lg\lg(n)^{gk})$  then worst-case \# \ckxor[]~can be solved in time $\tilde{O}(T(n))$ \footnotemark[\value{footnote}].

\end{reminder}

  \paragraph{\#\cfkc[]}

Now we will give the \#\cfkc[]~polynomial. Once again we will represent every factored vector $v$ with $g2^b$ variables. The variable $x_{v[i]}(\vec{s})$ is a $1$ if $s \in v[i]$ and $0$ otherwise. We create such a variable for all $i \in [0,g-1]$ and all $s \in \{0,1\}^b$.
Once again, let $S_f$ be the subset of $\binom{k}{2}$ tuples of vectors in  $\{0,1\}^b$ such that $f(s_1,\ldots,s_{\binom{k}{2}})=1$.
Finally for convenience let $E_1,\ldots, E_{\binom{k}{2}}$ be the $\binom{k}{2}$ partitions of edges in the input of \cfkc[]~and let $\ell = \binom{k}{2}$ to make notation easier to read. Let $S_{E}$ be the set of all $\ell$ tuples of edges $e_1,\ldots, e_\ell$ that form a clique. In an abuse of notation we will also use $e_i$ to represent the factored vector associated with the edge $e_i$.

 $$f_{ffkc}(\vec{X}) = \sum_{e_1, \ldots, e_\ell \in S_E} \left( \prod_{i \in [0,g-1]} \left( \sum_{(s_1,\ldots, s_\ell)\in S_f}  x_{e_1[i]}(\vec{s_1}) \cdots x_{e_\ell[i]}(\vec{s_\ell}) \right) \right).$$

\begin{lemma}
 $f_{ffkc}(\vec{X})$ is a \gPol{\#\cfkc[]} (see Definition \ref{def:goodPoly}).
 \label{lem:funcIsGoodPolclique}
 \end{lemma}
 \begin{proof}
 We will show that each property of a good polynomial is met by $f_{ffkc}$.
 \begin{itemize}

    \item \textit{If $\vec{I} = b_1,\ldots, b_n$, then
    $f_{ffk}(b_1,\ldots, b_n) = f_{ffkc}(\vec{I})=P(\vec{I})$ where $b_i$ maps to either a zero or a one in the prime finite field}: $f_{ffkc}$ and \#\ckfunc[]~count the same thing. Note that the inner summation is computing $\circ_f$, the product is computing $\circledcirc'_f$. Thus the overall sum is computing \#\ckfunc[].
    \item \textit{The function $f_{ffkc}$ has degree $d = o\left( \lg(n)/\lg\lg(n) \right)$:} $f_{ffkc}$ has degree $\ell g< k^2g$ which, when $k$ is constant is $o(\lg(n)/\lg\lg(n))$ by the definition of $g$.
    \item \textit{The function $f_{ffkc}$ is strongly $d$-partite:} Every monomial is formed by exactly one copy of a $x_{e_j[i]}(\vec{s})$ variable for every $j \in [0,g-1]$ and $i\in[1,\ell]$. These form our partitions and make the function strongly $\ell g$ partite.
\end{itemize}

\end{proof}

\begin{reminder}{Theorem \ref{thm:worstToAvgclique}}
Let $\mu$ be a constant and $0<\mu<1$.
If average-case \#\cfkc[]$^{\mu}$~(see Definition \ref{def:muavgCasefactored}) can be solved in time $T(n)$ with probability $1-1/(lg(n)^{k^2g}\lg\lg(n)^{k^2g})$  then worst-case \#\cfkc[]~can be solved in time $\tilde{O}(T(n))$ \footnotemark[\value{footnote}].

When $\mu=1/2$ average-case \#\cfkc[]$^{\mu}$ is average-case \#\cfkc[].
\end{reminder}
\begin{proof}
This follows from Theorem \ref{thm:framework} and Lemma \ref{lem:funcIsGoodPolclique}. The dimension of the \gPol{\#\cfkc[]} is $\binom{k}{2}g<k^2g$. By our construction of $f_{ffkc}$ every set has every possible string as a variable. By the construction of the framework from theorem \ref{thm:framework}, every bit will be selected as a $1$ uniformly at random with probability $\mu$. So, given the construction of $f_{ffkc}$ every set will have every possible string included with probability $\mu$. So the distribution induced by our framework matches our defined average-case distribution.

Finally by definition \ref{def:avgCaseFactored} when $\mu =1/2$ average-case \#\cfkc[]$^{mu}$ is average-case \#\cfkc[].
\end{proof}

\begin{reminder}{Corollary \ref{cor:worstToAvgClique}}
By Theorem \ref{thm:worstToAvgclique}, we have the following result:

If average-case \# \czkc[]~can be solved in time $T(n)$ with probability $1-1/(lg(n)^{k^2g}\lg\lg(n)^{k^2g})$ then worst-case \#\czkc[]~can be solved in time $\tilde{O}(T(n))$ \footnotemark[\value{footnote}] .
\end{reminder}

\paragraph{Reductions to Counting Factored Problems Imply Average Case Hardness Over Some Distribution}

Assume a problem $\# P$ exists such that an algorithm for it running in $T(n)^{1-\epsilon}$ implies a violation of \#\ckfunch[]~or \#\cfkch[]. We will evince examples of such problems in Section \ref{sec:harderProblem}. Further imagine that there is an explicit reduction that turns instances of \#\ckfunc[]~or \#\cfkc[]~into instances of $\# P$. In that case we can describe a distribution $D$ over which problem $\# P$ is $T(n)^{1-o(1)}$ hard on average from \#\ckfunch[]~or \#\cfkch[]. We can generate this distribution $D$ by taking the uniform distribution (the average-case distribution) over \#\ckfunc[]~or \#\cfkc[]~and running this distribution through our reduction.

Thus, reductions from problems $\# P$ to \#\ckfunc[]~or \#\cfkc[]~give explicit hard average-case distributions for problems $\# P$.

\subsection{Factoring is Expressive: Worst-Case Reductions}
\label{subsec:WCReductionsCompressed}

Our factored versions of these problems are very expressive. This allows us to show hardness from these factored problems.

\subsubsection{Completeness}

We will now show that \ckov[], \ckxor[], and \cksum[]~are all complete for \ckfunc[]~for all functions $\mathfrak{f}$. We do this by showing \ckxor[]~solves \ckfunc[]. Then, the equivalence between \ckov[], \ckxor[], and \cksum[]~implies they are all complete for \ckfunc[].
We will also show, using similar techniques, that \czkc[]~is complete for \cfkc[]~for all functions $\mathfrak{f}$.

This is a reminder of Theorem \ref{thm:ckxorIscomplete}, however, we add an additional statement to the theorem. We give an explicit function that we use to build this reduction.

\begin{reminder}{Theorem \ref{thm:ckxorIscomplete}}
If we can solve  \#\ckxor[]~with $g$ sets of $k^3b$ length vectors in time $T(n)$ then we can solve \#\ckfunc[]~instance with $g$ sets of $b$ length vectors in time $T(n)+\tilde{O}(n)$.

Additionally,
Let $v_1, \ldots, v_k$ be $k$ factored vectors each with $g$ subsets of $\{0,1\}^b$. Let $f_{XOR}$ be the function that returns $1$ if the $k$ input vectors xor to zero and otherwise returns $0$.
There is a function $\gamma_{\mathfrak{f} \rightarrow XOR,k}(\cdot, \cdot)$ that takes as input a factored vector with $g$ subsets of $\{0,1\}^b$ and an index and returns a new factored vector  with $g$ subsets of $\{0,1\}^{O(b)}$. This function $\gamma_{\mathfrak{f} \rightarrow XOR,k}$
runs in $\tilde{O}(2^b \cdot g)$ time for each vector and:
$$\circledcirc_{f_{XOR}}(\gamma_{\mathfrak{f} \rightarrow XOR,k}(v_1, 1), \ldots, \gamma_{\mathfrak{f} \rightarrow XOR,k}(v_k,k)) = \circledcirc_{\mathfrak{f}}(v_1, \ldots, v_k).$$
\end{reminder}
\begin{proof}
Consider a \ckfunc[]~instance and let $v_i$ be a factored vector from the $i^{th}$ list of it.
Given the factored vector $v_i$ from \ckfunc[]~we will describe how to make the factored vector $v_i'$ for our \ckxor[]~instance.
This transformation will be $\gamma_{\mathfrak{f} \rightarrow XOR,k}(\cdot, \cdot)$. We will describe the transformation for $\gamma_{\mathfrak{f} \rightarrow XOR,k}(v_i, i)$.
We do this by doing the same transformation on each set $v_i[j]$ where $j\in[1,g]$. We transform each set by performing the same transformation on every vector $u_i \in v_i[j]$. We describe this transformation in the next paragraph.

Given a vector $u_i$ of length $b$ we produce at most $2^{b (k-1)}$ new vectors of length $k^3b$. These vectors represent all possible $k$ tuples which include $u_i$ as as the $i^{th}$ vector. We want to include a $k$ tuple vector only if $f$ of that $k$ tuple evaluates to $1$. And we want our new long vectors to to return true if we are comparing vectors in \ckfunc[]~instance that do indeed have exactly that $k$ tuple of vectors.

More formally, let one possible $k$ tuple that includes $u_i$ as the $i^{th}$ vector be $(w_1, \ldots, w_{i-1},u_i,w_{i+1} \ldots , w_k)$.
If
$f(w_1, \ldots, w_{i-1},u_i,w_{i+1} \ldots , w_k)=1,$
then we create a $k^3b$-length vector for $u_i$ with this $kb$ length vector by considering every possible tuple $(x,y,z)$ where $x,y,z\in[1,k]$: We set aside $b$ bits for every possible tuple (in sorted order by the tuple). We want to use these to check if the $x^{th}$ vector and $y^{th}$ vector agree about what tuple they are considering as follows:
\begin{itemize}
\item If the tuple is $(x,x,z)$ we write the all zeros string, for the rest of the cases assume the first two indices are non-equal.
\item If the tuple is $(x,i,z)$ we write $w_z$ (or $u_i$ if $z=i$) in the $b$ bits.
\item If the tuple is $(i,y,z)$ we write $w_z$ (or $u_i$ if $z=i$) in the $b$ bits.
\item If the tuple is $(x,y,z)$ and $x,y \ne i$ then we write the all zeros vector of length $b$.
\end{itemize}

If we are comparing $k$ of these new vectors each of which representing the same tuple $(w_1, \ldots , w_k)$ then the new vector xors to zero. Consider a given group of $b$ bits that corresponds to $(x,y,z)$. Only two of our vectors have non-zero entries here, the $x^{th}$ and $y^{th}$ vectors. Both wrote down $w_z$ if they were representing the same $k$-tuple. A vector xored to itself produces the zero vector, so we get the zero vector.

If we are comparing $k$ of these new vectors and not all of the vectors agree about what tuples they are comparing then we will not xor to the zero vector. Say the $x^{th}$ and $y^{th}$ vectors disagree about what the $z^{th}$ element of the tuple is. Then the $b$ bits corresponding to $(x,y,z)$ will still have only two vectors with non-zero contributions. We will be xoring two vectors which are not equal, this will xor to some non-zero string.

Thus there is a one-to-one correspondence between $k$-tuples of vectors that evaluate to one in the \ckfunc[]~version and $k$-tuples of vectors that xor to the zero vector in the new \ckxor[]~version. Thus, the counts both give as output are equal.

As a result, we can transform an instance of \ckfunc[]~with $g$ groups of $b$ length vectors into an instance of \ckxor[]~with $g$ groups of $k^3 b$ length vectors in time $O(n\cdot g \cdot 2^b \cdot 2^{(k-1)b} \cdot k^3b )$. We restrict $k$ to be constant and $b= o(\lg(n))$, thus the time for the conversion is $\tilde{O}(n)$.
In the new version the count of the number of \ckxor[]~vectors that xor to zero is the same as the count of the number of \ckfunc[]~vectors that evaluate to $1$ on the function. So, a $T(n)$ algorithm for \ckxor[]~with $g$ groups and $k^3b$ bits implies a $T(n) +\tilde{O}(n)$ algorithm for \ckfunc[].
\end{proof}

\subsubsection{\texorpdfstring{f$k$-OV}{Lg}, \texorpdfstring{f$k$-SUM}{Lg}, and \texorpdfstring{\ckxor[]}{Lg} are Equivalent and Complete}
Intuitively, we can use our subsets of $\{0,1\}^b$ to do guesses that reduce from one problem to another.

\begin{lemma}
If  (\#)\ckov[]~can be solved in time $T(n)$ then  (\#)\ckxor[]~can be solved in $\tilde{O}(T(n))$ time.
\label{lem:ckov>cksum}
\end{lemma}
\begin{proof}
Say we are given an \ckxor[]~instance, with $k$ lists of factored vectors, each with $g$ subsets of $b$-bit vectors. We will follow the structure of Theorem \ref{thm:ckxorIscomplete}. Say we are given a factored vector from list $i$, $v_i$. Consider the $j^{th}$ subset $v_i[j]$ of it. Consider a particular vector $u_i \in v_i[j]$.
We will produce a new vector for every possible $k$ tuple of vectors $(w_1, \ldots, u_i, \ldots, w_k)$ such that $w_1 \oplus \ldots \oplus u_i\oplus \ldots \oplus w_k = \vec{0}$. This vector will have $k^3$ sections each of length $2b$, for a total length of vector $2k^3b$. These $k^3$ sections will correspond to every possible tuple $(x,y,z)$ where $x,y,z \in [1,k]$. The $2b$ bits will be used to check if the vector from list $x$ and the vector from list $y$ agree about the vector $w_z$. We want to only accept if there are $k$ vectors, one from each list that xor to the zero vector. Let $\bar{s}$ be the bitwise bit flip of every bit in $s$. We will use the fact that if both $s_1$ and $\bar{s_2}$ are orthogonal and $\bar{s_1}$ and $s_2$ are orthogonal then $s_1 = s_2$. This allows us to check equality.  Let $\mathbin\Vert$ be the concatenation operator (e.g $00\mathbin\Vert01 = 0001$). The $2b$ bits that correspond to $(x,y,z)$ are determined as follows:
\begin{itemize}
    \item If the tuple is $(x,x,z)$ we write the $2b$ bit all zeros string. For the rest of these assume the first two indices are not equal.
\item If the tuple is $(i,x,z)$ then write $w_z\mathbin\Vert\bar{w_z}$ (for convenience let $w_i = u_i$).
\item If the tuple is $(x,i,z)$ then write $\bar{w_z}\mathbin\Vert w_z$ (for convenience let $w_i = u_i$).
\item If the tuple is $(x,y,z)$ and $x \ne i$ and $y \ne i$ then we put the all ones string.
\end{itemize}

Now $k$ of these constructed vectors will be orthogonal only if $w_1 \oplus \ldots \oplus w_k = \vec{0}$, all the vectors $w_i$ existed in the original lists, and the constructed vectors all agree on the tuple $(w_1, \ldots, w_k)$.

So, with our constructed vectors the count of the number of vectors that are orthogonal will remain the same. The new instance will have the same number of factored vectors, $n$, but the vectors will have $g$ subsets of $\{0,1\}^{2k^3b}$. An algorithm which runs in $T(n)$ on this \ckov~instance will run in $T(n)$ on the \ckxor~instance.
\end{proof}

Next we reduce (\#)\ckxor~to (\#)\cksum. In \ckxor~we want to know if $k$ vectors xor to zero, which is very similar to asking if $k$ numbers sum to zero. The difference is entirely carries. So, we can pad the instance, and then guess carries.

We will use the \cksum[]~variant where we ask if $k-1$ numbers sum to equal exactly the last number.

\begin{lemma}
If (\#)\cksum[]~can be solved in time $T(n)$ then (\#)\ckxor[]~can be solved in $\tilde{O}(T(n))$ time.

Additionally,
Let $v_1, \ldots, v_k$ be $k$ factored vectors each with $g$ subsets of $\{0,1\}^b$. Let $f_{XOR}$ be the function that returns $1$ if the $k$ input vectors xor to zero and otherwise returns $0$. Let $f_{SUM}$ be the function that returns $1$ if the $k$ input vectors sum to zero and otherwise returns $0$.
There is a function $\gamma_{XOR \rightarrow SUM,k}(\cdot, \cdot)$ that takes as input a factored vector with $g$ subsets of $\{0,1\}^b$ and an index and returns a new factored vector  with $g$ subsets of $\{0,1\}^{O(b)}$. This function $\gamma_{XOR \rightarrow SUM,k}$
runs in $\tilde{O}(2^b \cdot g)$ time for each vector and:
$$\circledcirc_{f_{SUM}}(\gamma_{XOR \rightarrow SUM,k}(v_1, 1), \ldots, \gamma_{XOR \rightarrow SUM,k}(v_k,k)) =
\circledcirc_{\mathfrak{f}}(v_1, \ldots, v_k).$$
\label{lem:cksum>ckxor}
\end{lemma}
\begin{proof}
We will describe the transformation $\gamma_{XOR \rightarrow SUM,k}$ below.
Let $v_1,\ldots, v_k$ be $k$ factored vectors from a \ckxor[]~instance. Let $v_1[j], \ldots, v_k[j]$ be the $j^{th}$ subset of $b$-bit vectors from each of the factored vectors. Let $v_i[j][h][\ell]$ be the $\ell^{th}$ bit of the $h^{th}$ vector in the set $v_i[j]$.

We will turn every bit from $v_i[j][h][\ell]$ into $\lceil \lg(k) \rceil +1$ bits in a new number. If $i<k$ then this new longer string is  $\lceil \lg(k) \rceil$ zeros followed by the bit $v_i[j][h][\ell]$. If $i=k$, then every vector $v_k[j][h]$ turns into many vectors in the $k^{th}$ set of the \cksum instance: If $v_k[j][h][\ell]=0$ then we use our $\lceil \lg(k) \rceil +1$ bits to represent all of the \textbf{even} numbers in $[0,k-1]$. If $v_k[j][h][\ell]=1$ then we use our $\lceil \lg(k) \rceil +1$ bits to represent all of the \textbf{odd} numbers in $[0,k-1]$. So we produce $O(k^b)$ vectors for $v_k[j][h]$.

If a k-tuple of vectors forms a zero vector in k-xor then we get exactly one k-sum. The number of sets stays the same but the length of vectors in those sets grows from $b$ to $(\lceil \lg(k) \rceil +1)b$ length vectors. This is a constant and so if \cksum[]~can be solved in time $T(n)$ then \ckxor[]~can be solved in $\tilde{O}(T(n))$ time.
\end{proof}

\begin{reminder}
{Theorem \ref{thm:compressedKVarEquiv}}
If any of \#\ckov[], \#\cksum[], or \#\ckxor[]~can be solved in $T(n)$ time then all of \#\ckov[], \#\cksum[], and \#\ckxor[]~can be solved in $\tilde{O}(T(n))$ time.
\end{reminder}
\begin{proof}
This follows from Lemmas \ref{lem:ckov>cksum}, \ref{lem:cksum>ckxor}, and Theorem \ref{thm:ckxorIscomplete}.
\end{proof}

\begin{reminder}{Theorem \ref{thm:allCompressedAreComplete}}
If any of \#\ckov[], \#\cksum[], or \#\ckxor[]~can be solved in $T(n)$ time then \#\ckfunc[]~can be solved in $\tilde{O}(T(n))$ time.
\end{reminder}
\begin{proof}
Use Theorem \ref{thm:ckxorIscomplete} and Theorem \ref{thm:compressedKVarEquiv}.
\end{proof}

By Theorem \ref{thm:compressedKVarEquiv} and Theorem
\ref{thm:allCompressedAreComplete} we get the following corollary.

\begin{corollary}
\#\ckovh[], \#\cksumh[], and \#\ckxorh[]~are all equivalent. Moreover, \#\ckov[]~is implied by \#\ckfunc[]~for any function $\mathfrak{f}$.
\label{cor:equivAndComplete}
\end{corollary}

\subsubsection{Factored \texorpdfstring{zero-$k$-clique}{Lg} is hard from \texorpdfstring{f$k$-OV}{Lg}, \texorpdfstring{f$k$-SUM}{Lg}, \texorpdfstring{f$k$-XOR}{Lg}, and \texorpdfstring{\cfkc[]}{Lg}}

\begin{lemma}
If (\#)\czkc~is solved in time $T(n)$ then (\#)\cksum~is solved in time $\tilde{O}(T(n))$.
\label{lem:czt>cksum}
\end{lemma}
\begin{proof}
Consider a \cksum instance with lists $L_1,\ldots,L_k$. We will build the $k$-partite graph of our \czkc~instance to have vertex sets $V_1,\ldots,V_k$.
For every factored number $x_i \in L_i$ from the \cksum instance we create a node $v_i \in V_i$ where all edges going from $v_i$ to any vertex in $V_{i+1}$ have the value $x_i$ on them. All edges going from $v_i$ to nodes in $V_j$ where $j \ne i-1$ and $j\ne i+1$ are given the special factored vector where every set contains only the all zeros string.

Now, when three nodes are selected $v_1, v_2, \ldots, v_k$ the corresponding edges have a zero sum iff the corresponding $x_1,x_2,\ldots, x_k$ are a zero sum.

\end{proof}

\begin{theorem}
If (\#)\czkc~can be solved in $T(n)$ time then all of (\#)\ckov, (\#)\cksum, and (\#)\ckxor~can be solved in $\tilde{O}(T(n))$ time.
\label{thm:cztIsAUnit}
\end{theorem}
\begin{proof}
This follows from Lemma \ref{lem:czt>cksum} and Theorem \ref{thm:compressedKVarEquiv}.
\end{proof}

Now we will show that \czkc[]~is complete for the set of all problems \cfkc[]~for all functions $\mathfrak{f}$.

\begin{reminder}{Theorem \ref{thm:fzkcIsComplete}}
If (\#)\czkc~can be solved in $T(n)$ time then  (\#)\cfkc[]~for any $f$, can be solved in $\tilde{O}(T(n)+n^2)$ time.
\end{reminder}
\begin{proof}
We will use the transforms $\gamma_{\mathfrak{f} \rightarrow XOR,\binom{k}{2}}(\cdot, \cdot)$ and $\gamma_{XOR \rightarrow SUM,\binom{k}{2}}(\cdot, \cdot)$ from Theorem \ref{thm:ckxorIscomplete} and Lemma \ref{lem:cksum>ckxor} respectively.

Let $G$ be the $k$-partite graph we take as input from (\#)\cfkc[], now label the $\ell = \binom{k}{2}$ edge sets as $E_1,\ldots, E_\ell$. Now, for every factored vector $e_i \in E_i$ run the following transform:
$\hat{\gamma}_{\ell}(e_i,i) = \gamma_{XOR \rightarrow SUM,\binom{k}{2}}(\gamma_{\mathfrak{f} \rightarrow XOR,\ell}(e_i, i), i).$ This causes the output factored vector to have $g$ subsets of $\{0,1\}^{O(b)}$. The transformation takes $\tilde{O}(2^{O(b)}g)$ time per vector, which is $\tilde{O}(1)$ time per vector. The output vectors have the property that $$\circledcirc_{f_{SUM}}(\hat{\gamma}_{\ell}(e_1,1),\ldots, \hat{\gamma}_{\ell}(e_\ell,\ell)) = \circledcirc_{\mathfrak{f}}(e_1,\ldots, e_\ell).$$

Because $\circledcirc'_{f}$ (the function used in our factored clique problem definition) is equal to $\circledcirc_{f} \cdot isClique(e_1,\ldots,e_{\ell})$, by running this transformation we will have that:
$$\circledcirc'_{f_{SUM}}(\hat{\gamma}_{\ell}(e_1,1),\ldots, \hat{\gamma}_{\ell}(e_\ell,\ell)) = \circledcirc'_{\mathfrak{f}}(e_1,\ldots, e_\ell).$$

Thus, we can run the transformation $\hat{\gamma}_{\ell}$ in time $\tilde{O}(n^2)$ (because $n^2$ is the input size). Additionally, the output of the counting or detection variants of the \czkc[]~on the transformed input will be exactly equal to the output of \cfkc[]~on the original input. Thus, if we can solve (\#)\czkc[]~in time $T(n)$ we can solve (\#) \cfkc[]~in time $\tilde{O}(T(n) +n^2)$.
\end{proof}

\subsubsection{Factored Zero Triangle is hard from SETH, 3-SUM and APSP}

\begin{lemma}
The \czkch[3]~is implied by any one of SETH, the $3$-SUM hypothesis, or the APSP hypothesis.
\label{lem:czkch3Imp}
\end{lemma}
\begin{proof}
A violation of \czkch[3]~implies a violation of \ckovh[3]~by Lemma \ref{thm:cztIsAUnit}. A violation of \ckovh[3]~implies a violation of SETH \cite{ryanThesis}.

A violation of \czkch[3]~implies that a $O(n^{1-\epsilon})$ time algorithm exists for the zero triangle problem for some $\epsilon>0$. A  $O(n^{1-\epsilon})$ time algorithm for zero triangle implies a violation of the $3$-SUM hypothesis and the APSP hypothesis \cite{williams2010subcubic}.

So if any one of the three core hypotheses of fine-grained complexity (SETH, $3$-SUM, and APSP) are true then \czkch[3]~is true.
\end{proof}

\begin{reminder}{Theorem \ref{thm:fzkcIsHardFromAll}}
If \czkc[3]~(even for $b=o(\log n)$ and $g=o(\log(n)/\log\log(n))$) can be solved in $O(n^{3-\epsilon})$ time for some constant $\epsilon>0$, then SETH is false, and there exists a constant $\epsilon'>0$ such that $3$-SUM can be solved in $O(n^{2-\epsilon'})$ time and APSP can be solved in $O(n^{3-\epsilon'})$ time.
\end{reminder}
\begin{proof}
This follows from Lemma \ref{lem:czkch3Imp}. A $O(n^{3-\epsilon})$ time algorithm implies a violation of \czkch[3]. If \czkch[3]~is false then all of SETH, the APSP hypothesis, the $3$-SUM hypothesis are false.
\end{proof}

\subsection{Preliminaries}
\subsubsection{Notation}
\begin{definition}
We use $x \sim \mathbb{F}^n_{p}$ to mean that $x$
is drawn uniformly at random from all $p^n$ values in the support of $\mathbb{F}^n_{p}$.
\end{definition}

\subsubsection{Getting Nearly Uniform Bit Strings from Finite Field Elements}
Adser{\`{a}} et. al show that counting cliques is hard on average over the uniform distribution where every edge exists iid \cite{UniformCliqueABB}.

\begin{theorem}
Let $Z_i = Ber[\mu]$ where $\mu\in (0,1)$. Then let $Y \equiv  \sum_{i = 0}^{t} Z_i \cdot 2^i  \pmod{p}$. Let the total variation distance between $Y$ and $\textsc{Unif}[0,p-1]$ be $\Delta$. Then there exists a constant $C$ such that if $t \geq C\cdot \mu^{-1} \cdot (1-\mu)^{-1} \cdot \lg(p/\epsilon^2) \cdot \lg(p)$, then $\Delta \leq \epsilon$ \cite{UniformCliqueABB}.
\end{theorem}

\begin{theorem}
If you are given an input with $n$ numbers $x_1, \ldots,x_n$ each chosen from $\textsc{Unif}[1,p-1]$ there exists a sampling procedure which runs in time $O(n\lg^3(n)t(1/p-\epsilon)^{-1})$ that, with probability at least $1-2^{-\lg^2(n)}$, produces a new set of numbers $I = x'_1,\ldots,x'_n$ such that:
\begin{enumerate}
    \item $x'_i \equiv x_i \mod p$ for all $i$.
    \item Each $x'_i$ is $t$ bits long where $t \geq C\cdot \mu^{-1} \cdot (1-\mu)^{-1} \cdot \lg(p/\epsilon^2) \cdot \lg(p)$.
    \item $I$ is total variation distance $n\epsilon$ from the distribution where every bit of $x'_i$ is iid sampled from $Ber[\mu]$.
\end{enumerate}
(inspired by \cite{UniformCliqueABB})
\label{thm:SampleProcudure}
\end{theorem}
\begin{proof}
Let $Z_i = Ber[\mu]$ where $\mu\in (0,1)$. Then let $Y$ be the distribution formed by $\sum_{i = 0}^{t} Z_i \cdot 2^i \pmod{p}$.

Consider the procedure to generate $x'_i$ where we sample a number $y$ from $Y$, if $y \equiv x_i \pmod{p}$ then $x'_i =y$, else repeat. We take $O(t)$ time to produce a sample. We succeed with the probability that  $y \equiv x_i \pmod{p}$. This probability is at least $\frac{1}{p}-\epsilon$, because $\epsilon$ is the total variation distance of $Y$ and $\textsc{Unif}[1,p-1]$. Thus, the time to produce a single sample in expectation is $O(t (1/p-\epsilon)^{-1})$. To fail $\Theta(t (1/p-\epsilon)^{-1} \lg^3(n))$ times in a row will happen with probability at most $1-2^{-2\lg^{2}(n)}$. If we fail $\Theta(t (1/p-\epsilon)^{-1} \lg^3(n))$ times in a row simply halt the program and throw an error.

We run this procedure for all $n$ numbers, thus taking at most $O(n t (1/p-\epsilon)^{-1} \lg^3(n))$ time to succeed with probability at least $1-n2^{-2\lg^{2}(n)} \geq 1-2^{-\lg^{2}(n)}$.

The total variation distance from each individual $x'_i$ to the uniform distribution is $\epsilon$ and there are $n$ inputs in total. Thus, the total variation distance is at most $n\epsilon$ by the union bound.
\end{proof}

\begin{corollary}
If you are given an input with $n$ numbers $x_1, \ldots,x_n$ each chosen from $\textsc{Unif}[1,p-1]$ there exists a sampling procedure which runs in time $O(n\lg^3(n)t(1/p-1/n^3)^{-1})$ that, with probability at least $1-2^{-\lg^2(n)}$, produces a new set of numbers $I = x'_1,\ldots,x'_n$ such that:
\begin{enumerate}
    \item $x'_i \equiv x_i \pmod{p}$ for all $i$.
    \item Each $x'_i$ is $t$ bits long where $t \geq C\cdot \mu^{-1} \cdot (1-\mu)^{-1} \cdot (\lg(p) + 6\lg(n)) \cdot \lg(p)$.
    \item $I$ is total variation distance $1/n^{2}$ from the distribution where every bit of $x'_i$ is iid sampled from $Ber[\mu]$.
\end{enumerate}
\label{cor:SampleButNoEps}
\end{corollary}
\begin{proof}
Simply plug in $\epsilon = 1/n^3$ to Theorem \ref{thm:SampleProcudure}.
\end{proof}

\subsection{The framework}
In this section we are going to show that any problem $P$ with a  $\gPol{\cdot}$ is hard over the uniform average case.
We define $\gPol{\cdot}$ in Definition \ref{def:goodPoly}.

First, we want to convert our problem over a polynomial large finite field to a problem over many $O(\lg(n))$ sized finite fields. We will use the Chinese Remainder Theorem (CRT) to do this.

\begin{lemma}
\label{lem:CRT}
Let $P$ be some problem with output in range $[1,n^c]$. Let $P_p$ be the same problem as $P$, but where $P_p(\vec{I}) \equiv P(\vec{I}) \pmod{p}$.

Let $f$ be a \gPol{$P$}. Let $f_1, \ldots, f_{s}$ be a set of $s$ polynomials where  $s =O(\lg(n)/\lg\lg(n))$. We define $f_i$ as the same polynomial as $f$, but over finite field $F_{p_i}$ where $p_i = \Theta(\lg(n))$ and all $p_i$ are distinct.

Then, for all $i$,  $f_i$ is a \gPol{$P_{p_i}$}.

Finally, given $f_i(\vec{I})$ for all $i \in [1,s]$ we can return $P(\vec{I})$.
\end{lemma}
\begin{proof}

If $f(\vec{I}) =  P(\vec{I})$ then trivially $f(\vec{I}) \equiv P(\vec{I})\pmod{p}$. As a result $f_i(\vec{I}) \equiv P_{p_i}(\vec{I}) \equiv P(\vec{I}) \pmod{p_i}$.\\
If $f$ has degree $d$ then $f_i$ also has degree $d$ (it certainly has at most $d$, because $f$ is strongly $d$-partite they will in fact be equal). \\
If $f$ is $d$-partite then so is $f_i$. \\
Thus, $f_i$ is a \gPol{$P_{p_i}$}.

Given $f_i(\vec{I})$ for all $i \in [1,s]$ we know $P_{p_i}(\vec{I})$ for all $i \in [1,s]$. We can use the Chinese Remainder Theorem to find the value of $P$ as long as $\Pi_{i=1}^s p_i \geq n^c$. By the prime number theorem there is a sufficiently large constant $c'$ such that there are more than $2c \lg(n)/\lg\lg(n)$ primes between  $\lg(n)$ and $c'\lg(n)$. If we choose these primes to be $p_1,\ldots, p_{s=2c \lg(n)/\lg\lg(n)}$ then $\Pi_{i=1}^s p_i \geq n^{2c} \geq n^c$.
\end{proof}

Now we want to apply a worst-case to average case reduction for each $f_i$ separately. We can use Lemma 1 from \cite{BallWorstToAvg} to achieve this.

\begin{lemma}
Consider positive integers $n$, $d$, and $p$, and an $\epsilon \in (0, 1/3)$ such that $d > 9$, $p$ is
prime and $p > 12d$. Suppose that for some polynomial $f : \mathbb{F}^n_p \rightarrow \mathbb{F}_p$ of degree at most\footnote{Ball et al. simply say a polynomial of degree $d$, however, unsurprisingly, their proof does not require the polynomial be of degree at least $9$ to work.} $d$, there is an
algorithm $A$ running in time $T(n)$ such that when $x$ is drawn uniformly at random from all inputs $\mathbb{F}^n_p $:
$$Pr[A(x) = f(x)] \geq 1-\epsilon.$$

Then there is a randomized algorithm $B$ that runs in time $O(nd^2log^2(p) + d^3 + T(n)d)$ such that
for \emph{any} $x \in \mathbb{F}^n_p$:
$$Pr[B(x) = f(x)] \geq 2/3.$$
\cite{BallWorstToAvg}
\label{lem:ballWCtoAC}
\end{lemma}

Notably, we demand that $d= o(\lg(n)/\lg\lg(n))$ and we use $p = \Theta(\lg(n))$, so  $p > 12d$. The running time, given these choices, is $\tilde{O}(n + T(n))$ time.

\begin{corollary}
Assume an $f$ exists that is \gPol{$P$}. Then, let $f_1, \ldots , f_s$ be the polynomials described in \ref{lem:CRT}.
Let $A$ be an algorithm  that runs in time $T(n)$ such that when $x \sim \mathbb{F}^n_{p_i}$:
$$Pr[A(x) = f_i(x)] \geq 3/4,$$
for all $i$.
Then there is a randomized algorithm $B$ that runs in time $\tilde{O}(n + T(n))$ such that
for \emph{any} $\vec{I} \in \{0,1\}^n$:
$$Pr[B(\vec{I}) = P(\vec{I})] \geq 1-O\left(2^{-\lg^2(n)}\right).$$
\label{cor:RandomFsolvesP}
\end{corollary}
\begin{proof}
We use Lemma \ref{lem:ballWCtoAC} for each polynomial $f_i$. It follows that having an algorithm $A$ for computing $f_i$ over the uniform input $\mathbb{F}^n_{p_i}$ that succeeds with probability $3/4$ implies that a randomized algorithm $B'_i$ exists that succeeds with probability $2/3$.

We can now create an algorithm $B_i$ by running $B'_i$ for $\Theta(\lg^3(n))$ times and pick the most common output, this will return the correct answer with probability at least $1-2^{-\lg^{2.5}(n)}$.

Now if all of $B_1,\ldots, B_s$ return the correct answer then we can use the CRT trick of Lemma \ref{lem:CRT} to compute the value of $P(\vec{I})$. All of $B_1,\ldots, B_s$  return the correct answer with probability at least $1-s2^{-\lg^{2.5}(n)} = 1-O(\lg(n)/\lg\lg(n))2^{-\lg^{2.5}(n)} < 1-O\left(2^{-\lg^{2}(n)}\right)$
\end{proof}

So, we now want to show that solving random instances of $P$ can solve random instances $f_i(x)$ where $x \sim \mathbb{F}^n_{p}$. To do this we will use the sampling procedure described in Corollary \ref{cor:SampleButNoEps}. We will also use the fact that $P_{p_i}(x)=f_i(x)$ when $x$ is a zero and one input.

\begin{lemma}
Assume a $d$ degree polynomial $f$ exists that is \gPol{$P$}. Then, let $f_1, \ldots , f_s$ and $p_1, \ldots , p_s$ be the polynomials and primes described in Lemma \ref{lem:CRT}.

Let $A$ be an algorithm  that runs in time $T(n)$ such that when $\vec{I}$ is formed by $n$ bits each chosen iid from $Ber[\mu]$ where $\mu\in (0,1)$ is a constant, then:
$$Pr[A(\vec{I}) = P(\vec{I})] \geq 1-1/\omega\left( \lg^d(n)\lg\lg^d(n) \right).$$

Then there is a  $B$ that runs in time $\tilde{O}(n + T(n))$ such that when $x \sim \mathbb{F}^n_{p_i}$:
$$Pr[B(x) = f_i(x)] > 3/4,$$
for all $f_i$.
\label{lem:UnifPtoACf}
\end{lemma}
\begin{proof}
Let $D_{\mu}$ be the distribution over inputs where each of the $n$ bits is chosen iid from $Ber[\mu]$, that is one is chosen with probability $\mu$ and zero is chosen with probability $1-\mu$.
Recall that when we say $\vec{Z} \sim D_{\mu}$ we mean that $\vec{Z} $ is drawn from the distribution $D_{\mu}$. We will use an abuse of notation where we run $f_i(\vec{Z})$, when we do this we mean that one should interpret the $n$ length bit vector as $n$ values from $F_{p_i}$ where $0$ maps to $0 \in F_{p_i}$ and $1$ maps to $1 \in F_{p_i}$. Additionally when we have a vector $v$ we will use $v[j]$ to represent the $j^{th}$ number in $v$.

In this proof we will show how to use $P(\vec{Z})$ to solve instances of $f_i(\vec{Z})$ for all $i$. Note that we can simply take the output of $P(\vec{Z})$ modulo $p_i$.
So we want to use $f_i(\vec{Z})$ where $\vec{Z}  \sim D_{\mu}$ to solve $f_i(z)$ where $z \sim \mathbb{F}_{p_i}^n$.

Let $f'$ be the function $f_i$ but taken over the integers instead of $F_{p_i}$. Note that this is the same $f'$ regardless of $f_i$. We have that if $x \in \mathbb{F}_{p_i}^n$ then $f'(x) \equiv f_i(x) \pmod{p_i}$.
Furthermore, if we make a new input $x'$ where $x'[j] \equiv x[j] \pmod{p_i}$ for all $j\in [1,n]$ then  $f'(x) \equiv f_i(x) \pmod{ p_i}$.
So, given an input $x \sim \mathbb{F}_{p_i}^n $ we will take the sampling procedure of Corollary \ref{cor:SampleButNoEps} and make a new input $x'$, where $x'[j]$ is a $t =O(\mu^{-1} \cdot (1-\mu)^{-1} \cdot (\lg(p_i) + 6\lg(n)) \cdot \lg(p_i))$ bit number. Note that because $\mu$ is constant and neither zero nor one and $p_i =\Theta(\lg(n))$ then $t =O(\lg(n)\lg\lg(n))$.
Furthermore, any given number $x'[j]$ has the property that the distribution over its binary representation has total variation distance $\leq 1/n^3$ from the distribution where all $t$ bits are chosen iid from $Ber[\mu]$.
Thus, all $tn$ bits in our new input $x'$ have total variation distance at most $1/n^2$ from the distribution where all $tn$ bits are chosen iid from $Ber[\mu]$.

Now, we can compute the value of $f'(x')$ with $t^d$ calls to $f'$ where every call has a zero one input. Every monomial is formed by one variable from each of the $d$ partitions. Let $m$ be the number of monomials. So we can write our polynomial $f'$ as follows :
$$f'(x') = \sum_{j=1}^m y_{k_{j,1}}\cdot y_{k_{j,2}}\cdots y_{k_{j,d}},$$
where $y_{k_{j,\ell}}$ is a variable from the $\ell^{th}$ partition $S_{\ell}$. The input $x'$ is formed with $n$ of these input variables $y_{k_{j,\ell}}$.

We can break down this multiplication for every bit. Let $y_{k_{j,\ell}}[r]$ be the $r^{th}$ bit of $y_{k_{j,\ell}}$. Now we can rewrite our sum. Recall that $g_{f'}(v_1,\ldots,v_d)$ is the function such that $f'$ can be written as a sum of calls to $g_{f'}$, where $v_\ell$ is a variable from partition $S_\ell$:
$$f'(x') =\sum_{j=1}^m \left( \sum_{r_1,\ldots,r_d \in[0,t-1]} 2^{r_1 +\ldots + r_d} \cdot y_{k_{j,1}}[r_1]\cdot y_{k_{j,2}}[r_2]\cdots y_{k_{j,d}}[r_d] \right).$$
Put in words, we can multiply $d$ numbers each of $t$ bits by making a weighted sum over the $t^d$ multiplications of the bits of the $d$ numbers.

Now, we want to create $t^d$ inputs $\hat{x}_1,\ldots, \hat{x}_{t^d}$. They are formed by taking all possible choices of $r_1,\ldots,r_d$ where each $r_{\ell}$ is an integer in $[0,t-1]$. Given a choice of $r_1,\ldots,r_d$ we create a new input $\hat{x}_j$ by taking all variables in $S_{\ell}$ and making their value in $\hat{x}_j$ be the  $r_{\ell}^{th}$ bit of that variable in $x'$.

Now, call $A(\hat{x}_j)$ for all $j\in[1,t^d]$. Note that  $P(\hat{x}_j) \equiv f_i'(\hat{x}_j)  \equiv f_i(\hat{x}_j) \pmod{p_i}$. So, if $A(\hat{x}_j) = P(\hat{x}_j)$ for all $j\in [1,t^d]$ then we can return the value of $f'(x') \equiv f_i(x) \pmod{p}$.

By the definition of $A$ in this Lemma, $A$ must succeed on any individual random input $x\sim D_{\mu}$ with probability $1-1/\omega(\lg^d(n)\lg\lg^d(n))$. The total variation distance of any $\hat{x}_j$ from $D_{\mu}$ is at most $1/n^2$. So $A$ must succeed on any one given random input $\hat{x}_j$ with probability $1-1/\omega(\lg^d(n)\lg\lg^d(n))-1/n^2$ which is $1-1/\omega(\lg^d(n)\lg\lg^d(n))$.

Our inputs $\hat{x}_j$ are not iid from each other, however, if $A$ is correct with probability $1-q$ on a given input from $\hat{x}_j$ then $A$ must be correct with probability at least $1-qt^d$ on $t^d$ inputs $\hat{x}_j$ at once.

So, $A$ will return correct answers for all $t^d$  inputs $\hat{x}_j$ at once with probability at least $1-1/\omega(1)$. Given these correct answers we can compute $f_i(x)$, for all $f_i$. So, an algorithm $B$ exists that makes $t^d$ calls to $A$ and takes $n \lg^4(n)t$ time to produce our new sampled input $x'$ from $x$. \\
$B$ returns $f_i$ correctly with probability at least $1-1/\omega(1) > 3/4$.\\
$B$ takes a total time of $O(t^d T(n) + n)$. We have that $t=O(\lg(n)\lg\lg(n))$ and $d= o(\lg(n)/\lg\lg(n))$ (by our definition of \gPol{P}). Thus, $t^d = n^{o(1)}$. So we have that $B$ runs in time $\tilde{O}( T(n) + n)$.
\end{proof}

This next theorem gives a worst case to average case reduction for $P$.

\begin{reminder}{Theorem \ref{thm:framework}}
Let $\mu$ be a constant such that $0 < \mu <1$.
Let $P$ be a problem such that a function $f$ exists that is a \gPol{$P$}, and let $d$ be the degree of $f$.
Let $A$ be an algorithm  that runs in time $T(n)$ such that when $\vec{I}$ is formed by $n$ bits each chosen iid from $Ber[\mu]$:
$$Pr[A(\vec{I}) = P(\vec{I})] \geq 1-1/\omega\left( \lg^d(n)\lg\lg^d(n) \right).$$
Then there is a randomized algorithm $B$ that runs in time $\tilde{O}(n + T(n))$ such that
for \emph{any} for $\vec{I} \in \{0,1\}^n$:
$$Pr[B(\vec{I}) = P(\vec{I})] \geq 1-O\left(2^{-\lg^2(n)}\right).$$
\end{reminder}
\begin{proof}
We will use Lemma \ref{lem:UnifPtoACf} and Corollary \ref{cor:RandomFsolvesP} to get this result.

Note that the algorithm $A$ here can be used as the algorithm $A$ in Lemma \ref{lem:UnifPtoACf}.

Furthermore, note that the algorithm $B$ of Lemma \ref{lem:UnifPtoACf} has the same requirements as the algorithm $A$ of Corollary \ref{cor:RandomFsolvesP}.

So, given the algorithm $A$ of this theorem we can produce the algorithm $B$ from Corollary \ref{cor:RandomFsolvesP}.

The algorithm $B$ of Corollary \ref{cor:RandomFsolvesP} has the same properties of the algorithm $B$ described in this theorem.

Thus, algorithm $A$ implies that an algorithm $B$ exists.
\end{proof}

\subsection{So You Want to Prove Uniform Average-Case Hardness:\\
How to Use Good Low-Degree Polynomials}

Let $P$ be a problem that takes an $n$ bit input $I$. The uniform average case with probability $\mu$ draws each of the $n$ bits identically and independently where we draw $1$ with probability $\mu$ and $0$ with probability $1-\mu$.

Now, recall the definition of $\gPol{P}$.

\begin{definition}[good low-degree polynomial~Definition \ref{def:goodPoly}]
Let $n$ be the input size of the problem $P$, let $P$ return an integer in the range $[0,p-1]$ where $p$ is a prime and $p < n^c$ for some constant $c$.
A \emph{good low-degree polynomial} for problem $P$  (\gPol{P})  is a polynomial $f$ over a prime finite field $F_{p}$ where:
\begin{itemize}
    \item There are at most polynomial monomials in $f$.
    \item If $\vec{I} = b_1,\ldots, b_n$, then
    $f(b_1,\ldots, b_n) = f(\vec{I})=P(\vec{I})$ were $b_i$ will map to either a zero or a one in the prime finite field.
    \item The function $f$ has degree $d = o\left( \lg(n)/\lg\lg(n) \right)$.
    \item the function $f$ is strongly $d$-partite.
\end{itemize}
\end{definition}

To show that $P$ is hard in the average case find a polynomial $f$ that is a $\gPol{P}$. The most likely hurdle will be the degree (a degree of $o(\lg(n)/\lg\lg(n))$ is quite small). The second mostly likely hurdle will be making your function strongly $d$-partite.  You need to separate the input into $d$ partitions such that every monomial involves exactly one variable from each partition.

If you manage to construct a $\gPol{P}$, then you can apply Theorem \ref{thm:framework}. This gives the result that a $T(n)$ time algorithm for $P$ in the average-case that succeeds with high enough probability (probability at least $1-1/\omega(\lg^d(n)\lg\lg^d(n))$) implies a $\tilde{O}(T(n))$ time algorithm for $P$ in the worst case that succeeds with high probability.

So, just constructing a $\gPol{P}$ implies a worst-case to average-case self-reduction for the problem $P$.

We will give some tips for constructing $d$-partite $\gPol(\cdot)$ functions.\\
It is easiest to get the strong $k$-partite structure if you start with a worst-case problem that has the $k$-partite structure. We suggest considering versions of the problem (ideally worst-case equivalent versions) that are $k$-partite. For example, we could consider a version of \fkov[]~that takes a single list as input. This version would allow all $k$ tuples of vectors to be compared. However, this version does not lend itself to a $gk$ partite representation. \\
Another issue is

\subsection{So You Want to Reduce from a Factored Problem}
\subsection{The factored problems}
We call the problems we introduce ``factored problems'' (a full formal definition is in Section~\ref{sec:Prelims}).
To define them, let us first define a {\em factored vector}. Let $b$ and $g$ be positive integers. A $(g,b)$-factored vector, $v$, is made up of $g$ sets $v[1], \ldots, v[g]$. Each set is a subset $v[i] \subseteq \{0,1\}^b$. Roughly speaking, a factored vector $v$ represents many $b\cdot g$ binary vectors, namely a concatenation $x_1,x_2,\ldots,x_g$ for each choice of a $g$-tuple of vectors $x_i\in v[i]$ for all $i$.  For example, for $g=2$ and $b=3$, let $v$ be a factored vector where
$v[0] = \{001,010\}$ and $v[1] = \{010,110\}$. A natural interpretation of $v$ is that it is a set of the following $4$ binary vectors, by concatenating each member of $v[0]$ with each member of $v[1]$, that is $\{001010, 001110,010010,010110\}$.

Now, consider a function $f$ that takes a $2b$-bit input $x_1,\ldots,x_b,y_1,\ldots, y_b$ and returns a value in $\{0,1\}$; we can consider $f$ as a Boolean function. Then, for two factored vectors $v$ and $v'$ and a coordinate $i\in [g]$, we can consider the number of pairs of $b$-bit vectors $x\in v[i], y\in v'[i]$ that $f$ accepts. This is $accept_f(v,v',i):=\sum_{x\in v[i],y\in v'[i]} f(x_1,\ldots,x_b,y_1,\ldots,y_b)$, where $x=x_1\ldots x_b$ and $y=y_1\ldots y_b$. If we take the product $\prod_{i=1}^g accept_f(v,v',i)$, we would obtain the number of pairs of $b\cdot g$-length vectors represented by $v$ and $v'$ that are accepted by $f$, where $f$ is said to accept a pair of $b\cdot g$-length vectors if it accepts each of the $g$ pairs of chunks of $b$-length subvectors between positions $(i-1)b+1$ to $ib$ for $i\in [g]$.

Then we can define the factored problem for $f$, \ckfunc[2]~that given two sets $S$ and $T$ of $n$ $(g,b)$-factored vectors, computes the sum $\sum_{v\in S,v'\in T} \prod_{i=1}^g accept_f(v,v',i)$, i.e. the total number of pairs of vectors represented by vectors in $S$ and $T$ that are accepted by $f$. For technical reasons, we restrict the
 values $g=o(\lg(n)/\lg\lg(n))$ and $b = o(\lg(n))$, so that each factored vector can be represented with at most $gb2^b$ bits ($g$ sets of at most $2^b$ vectors of length $b$).

Depending on the function $f$, we get different versions of a factored problem. If $f$ on $b$-length vectors $x$ and $y$, returns $1$ iff $x\cdot y=0$, then we get the factored OV problem \ckov[2]. If $f$ returns $1$ if the XOR of $x$ and $y$ is $0$, we get the \ckxor[2]~problem, and if $f$ returns $1$ iff $x+y=0$ when viewed as integers, we get the \cksum[2]~problem.

More generally, $f$ can be defined over $k\cdot b$-length vectors, for integer $k\geq 2$, taking $k$-tuples of $b$-length binary vectors to $\{0,1\}$. Then analogously we can define \ckfunc~to compute the number of $k$-tuples of vectors represented by some $k$-tuple of factored vectors, one from each $n$-sized input set $S_i$, $i\in [k]$, so that $f$ accepts the $k$-tuple. This way we can define \ckov, \ckxor, \cksum etc, the factored versions of \kOV, \kXOR~and \ksum.

Similarly to these problems defined on $k$-tuples of sets of factored vectors, we define problems reminiscent to $k$-clique. Here $f$ is a function that takes $\binom{k}{2}$-tuples of $b$-length vectors to $\{0,1\}$, one is given a graph whose edges are labeled by factored vectors and the factored $f$ $k$-clique problem, \cfkc[], asks to compute the number of $\binom{k}{2}$-tuples of vectors that are accepted by $f$ and are represented by the factored vectors labeling the edges of a
$k$-clique in the graph. We focus in particular on the factored zero-$k$-clique problem, \czkc[], in which $f$ corresponds to returning whether the sum of $\binom{k}{2}$ $b$-bit numbers is $0$.

\subsection{Results for factored problems}

We will summarize the results around our factored problems below.
They appear in sections \ref{sec:compressedVariants} and \ref{sec:harderProblem}. We give a visual summary of our results in Figure \ref{fig:results}. We use the shortened names for many of the problems in the figure.
The results will concern both counting and decision versions of our factored problems. The decision versions ask whether the count is nonzero, whereas the counting versions ask for the exact count. When we want the counting version, we will place $\#$ in front of the name of the problem. See the Preliminaries (Section \ref{sec:Prelims}) for more details.

\begin{figure}[ht]
    \centering

    \includegraphics[width=0.9\textwidth]{ResultSummarywXOR.pdf}
    \caption{A summary of the reductions to and from factored problems in the paper. The problems in diamonds are the core problems of FGC. The full lines are reductions from this paper, while doted lines are pre-existing reductions.
    The problems in gray boxes are our factored problems. The  problems in thick lined boxes are the problems we reduce from factored problems. For the problems surrounded by a thick-lined double box we have generated an explicit average case distributions on which they are hard (but it is not the uniform distribution).
    These results appear in Sections \ref{sec:compressedVariants} and \ref{sec:harderProblem}.}
    \label{fig:results}
\end{figure}

\paragraph{Summary.}
We first provide an overview summary of our results.

First we show that the factored versions of $k$-OV, $k$-SUM and $k$-XOR are all $n^{k-o(1)}$-fine-grained hard under SETH. We also show that the factored version of zero-$3$-clique (\fzkc[3]) is $n^{3-o(1)}$-fine-grained hard based on any of the three core hypotheses of FGC (SETH, or the APSP or $3$-SUM hypothesis).  Additionally, we show that the counting versions of these factored problems are as hard in their natural uniform average-case as they are in the worst case. Moreover, we show that many natural problems, like counting regular expression matchings, reduce from our factored problems. This even implies fine-grained average-case hardness for these problems over some explicit distributions.

Thus our factored problems do three things simultaneously:

\begin{itemize}
\item Instead of trying to use the uniform average-case of the core problems of FGC as central problems in a network of average-case reductions, we can use the factored versions of the core problems in FGC. For example, the counting variant of factored OV (\#\ckov[2]) is hard in its uniform average case from the worst-case OV hypothesis.
 Generically, our factored problems serve as an alternative central problem for average-case hardness. To demonstrate this, in Section \ref{sec:harderProblem}, we give reductions from counting factored problems to four problems in graph algorithms and sequence alignment (including counting regular expression matchings).

  \item The factored versions of the core problems are sufficiently expressive that they are complete for the large class of factored problems. In particular, \ckov[], \ckxor[], and \cksum~are complete for the class of problems of the form \ckfunc[]~over all $f$, while \fzkc[]~is complete for the class of problems \cfkc[]~over all $f$.
  Despite this expressiveness we are still able to reduce our factored problems to many natural problems. In section \ref{sec:harderProblem} we give fine-grained reductions from our factored problems to  $k$-LCS, Edit Distance and a labeled version of Max Flow.

\item Abboud et al. \cite{matchingTriangles} gave two problems, Triangle Collection and Matching Triangles that are hard from all three core assumptions in FGC. They also showed that one can reduce  Triangle Collection \footnote{Actually a version of the problem that is still hard under all three assumptions.} to several natural problems in graph algorithms. Unfortunately, however, neither Triangle Collection, nor Matching Triangles are known to be hard on average.
One of our factored problems, \fzkc[3]~is also hard from all three core assumptions. Moreover, the counting version of \fzkc[3]~is additionally $n^{3-o(1)}$ hard in the average-case from all three core assumptions of FGC. Thus, problems that reduce from counting \fzkc[3]~get average-case hardness for some explicit average-case distribution. We give two examples of problems that reduce from counting \fzkc[3]~in Section \ref{sec:harderProblem}. Hence if you are interested in average-case hardness then counting \fzkc[3]~might be a better source for reductions than, say Matching Triangles or Triangle Collection.

\end{itemize}

\paragraph{Fine-grained hardness for factored problems.}
Here we show that our factored problems are fine-grained hard under standard FGC hypotheses.

We first show that a single call to a factored problem solves its non-factored counterpoint.
\begin{theorem} \label{thm:unfactoredToFactored}
In $O(n)$ time, one can reduce an instance of size $n$ of $k$-OV, $k$-XOR, $k$-SUM and Z$k$C to a single call to an instance of size $\tilde{O}(n)$  of \ckov[], \ckxor[], \cksum[]~and \czkc, respectively.
\end{theorem}

The above theorem holds both in the decision and counting context. It gives fine-grained hardness for the factored variants of all our problems, under the hypothesis that the original variants are hard.  Note that  $k$-XOR, $k$-SUM have $\tilde{O}(n^{ \lceil k/2 \rceil})$ time algorithms. However, we have $n^{k-o(1)}$ conditional lower bounds for all of \ckov[], \ckxor[], \cksum[]~and \czkc. So, while we do get fine-grained hardness from the $k$-XOR and $k$-SUM hypotheses, this hardness is not tight. The hardness is tight from the $k$-OV and Z$k$C hypotheses however.

Now we give fine-grained hardness for \czkc[3]~under all three core hypotheses from FGC.
\begin{theorem}
If \czkc[3]~(even for $b=o(\log n)$ and $g=o(\log(n)/\log\log(n))$) can be solved in $O(n^{3-\epsilon})$ time for some constant $\epsilon>0$, then SETH is false, and there exists a constant $\epsilon'>0$ such that $3$-SUM can be solved in $O(n^{2-\epsilon'})$ time and APSP can be solved in $O(n^{3-\epsilon'})$ time.
\label{thm:fzkcIsHardFromAll}
\end{theorem}

\paragraph{Worst-case to average-case reductions for factored problems.}
We show that our factored problems admit fine-grained worst-case to average-case reductions. Our first theorem about this is a worst-case to average-case fine-grained reduction for the counting version of \ckfunc~for a natural distribution (defined in Definition \ref{def:muavgCasefactored}). The proof appears in Section \ref{sec:compressedVariants}.

\begin{theorem}
\label{thm:worstToAvgckf}
Let $\mu$ be a constant such that $0 < \mu <1$.
Suppose that average-case \#\ckfunc[]$^{\mu}$~(see definition \ref{def:muavgCasefactored}, this is an iid distribution which has ones with probability $\mu$) can be solved in time $T(n)$ with probability at least $1-1/(lg(n)^{kg}\lg\lg(n)^{kg})$. Then worst-case \#\ckfunc[]~can be solved in time $\tilde{O}(T(n))$ \footnote{Note that given that $g= o(\lg(n)/\lg\lg(n)) $ then a probability of $1-1/n^{\epsilon}$ will be high enough for any $\epsilon>0$.}.

When $\mu =1/2$ average-case \#\ckfunc[]$^{\mu}$ is average-case \#\ckfunc[].
\end{theorem}

 Thus, if we have worst-case fine-grained hardness for \#\ckfunc~for some $f$, then we get average-case hardness for the same problem over a natural distribution. In particular, in the corollary below we obtain average-case hardness for \#\ckov[], \#\cksum[], \#\ckxor[], based on the standard FGC hardness of \kOV, \ksum, \kXOR~(as implied by Theorem~\ref{thm:unfactoredToFactored}).

\begin{corollary}
\label{cor:worstToAvg}
If average-case \#\ckov[]~can be solved in time $T(n)$ with probability $1-1/(lg(n)^{gk}\lg\lg(n)^{gk})$  then worst-case \#\ckov[]~ can be solved in time $\tilde{O}(T(n))$ \footnotemark[\value{footnote}].

If average-case \#\cksum[] can be solved in time $T(n)$ with probability $1-1/(lg(n)^{gk}\lg\lg(n)^{gk})$  then worst-case \#\cksum[]~can be solved in time $\tilde{O}(T(n))$ \footnotemark[\value{footnote}].

If average-case \#\ckxor[]~can be solved in time $T(n)$ with probability $1-1/(lg(n)^{gk}\lg\lg(n)^{gk})$  then worst-case \#\ckxor[]~can be solved in time $\tilde{O}(T(n))$ \footnotemark[\value{footnote}].

\end{corollary}

Similarly, we obtain fine-grained average-case hardness for \#\cfkc, based on the fine-grained worst-case hardness of \#\cfkc.

\begin{theorem}
\label{thm:worstToAvgclique}
Let $\mu$ be a constant and $0<\mu<1$.
If average-case \#\cfkc[]$^{\mu}$~(see Definition \ref{def:muavgCasefactored}, this is an iid distribution which has ones with probability $\mu$) can be solved in time $T(n)$ with probability $1-1/(lg(n)^{k^2g}\lg\lg(n)^{k^2g})$  then worst-case \#\cfkc[]~can be solved in time $\tilde{O}(T(n))$ \footnotemark[\value{footnote}].

When $\mu=1/2$ average-case \#\cfkc[]$^{\mu}$ is average-case \#\cfkc[].
\end{theorem}

By Theorem \ref{thm:worstToAvgclique}, we have the following result for \#\czkc[]~in particular.

\begin{corollary}
\label{cor:worstToAvgClique}
If average-case \#\czkc[]~can be solved in time $T(n)$ with probability $1-1/(lg(n)^{k^2g}\lg\lg(n)^{k^2g})$ then worst-case \#\czkc[]~can be solved in time $\tilde{O}(T(n))$ \footnotemark[\value{footnote}].
\end{corollary}

Thus in particular we obtain fine-grained average-case hardness for counting factored zero-$3$-cliques, based on the hardness of zero-$3$-clique, and thus based on the APSP and $3$-SUM hypotheses.

\paragraph{Completeness for \ckov[],\cksum[], \ckxor[]~and \czkc[].}

Let $k\geq 2$ be a fixed integer. Consider the class of problems \ckfunc[]~defined over all boolean functions $f$ on $kb$-length inputs. Our first sequence of results show that \ckov[],\cksum[]~and  \ckxor[]~are complete for the class, so that a $T(n)$ time algorithm for any of these problems would imply an $\tilde{O}(T(n))$ time algorithm for \ckfunc[]~for any $f$.

To prove this, we first show that \ckxor[]~is complete for the class:
\begin{theorem}
\label{thm:ckxorIscomplete}
If we can solve \#\ckxor[]~with $g$ sets of $k^3b$ length vectors in time $T(n)$ then, for any $f$, we can solve a \#\ckfunc[]~instance with $g$ sets of $b$ length vectors in time $T(n)+\tilde{O}(n)$ time.
\end{theorem}

We then show that \ckov[], \cksum[]~and \ckxor[]~are equivalent.
\begin{theorem}
\label{thm:compressedKVarEquiv}
If any of \#\ckov[], \#\cksum[], or \#\ckxor[]~can be solved in $T(n)$ time then all of \#\ckov, \#\cksum[], and \#\ckxor[]~can be solved in $\tilde{O}(T(n))$ time.
\end{theorem}

The above two theorems imply the final completeness theorem:
\begin{theorem}
\label{thm:allCompressedAreComplete}
If any of \#\ckov[], \#\cksum[], or \#\ckxor[]~can be solved in $T(n)$ time then \#\ckfunc[]~can be solved in $\tilde{O}(T(n))$ time.
\end{theorem}

We also consider the class of problems (\#)\cfkc[]~defined by Boolean functions $f$ on $\binom{k}{2}b$-length inputs. We show that (\#)\czkc~is complete for this class.

\begin{theorem}
If (\#)\czkc~can be solved in $T(n)$ time then (\#)\cfkc[]~for any $f$, can be solved in $\tilde{O}(T(n)+n^2)$ time.
\label{thm:fzkcIsComplete}
\end{theorem}

Thus our factored problems corresponding to core problems in FGC, are the hard problems for natural classes of factored problems.

\paragraph{Fine-grained hardness for well-studied problems, based on the hardness of factored problems.}
The results we mention here appear in Section \ref{sec:harderProblem}. The main upshot is that the factored problems are both hard and also simple enough to imply hardness for basic problems in graph and string algorithms.
Some of the results are based on the hardness of \fzkc[3]~which implies hardness from all of SETH, 3-SUM and APSP. Some come from \ckfunc[]~which implies hardness from SETH.

\noindent \textbf{\emph{Partitioned Matching Triangles.}}
First we define the {\em Partitioned Matching Triangles} problem (PMT) as follows: Given $g$ disjoint $n$-node graphs with node colors, is there a triple of colors $a,b,c$ so that every one of the $g$ graphs contains a triangle whose nodes are colored by $a,b,c$? The counting variant of PMT~is to count the total number of such $g$-tuples of colored triangles.

Abboud et al. \cite{matchingTriangles} consider the related Matching Triangles problem mentioned earlier in the introduction, and show that it is hard from all three core FGC hypotheses. In the Matching Triangles problem one is given an integer $T$ and a node-colored graph $G$ and one wants to know if there is a triple of colors $a,b,c$ so that there are at least $T$ triangles in $G$ colored by $a,b,c$.

We observe first that for the particular parameters for which Matching Triangles is shown to be hard in \cite{matchingTriangles}, one can actually reduce Matching Triangles in a fine-grained way to Partitioned Matching Triangles (PMT), so that the latter problem is also hard from all three hypothesis. Furthermore, we give a powerful reduction to PMT~from \czkc[3]. Moreover, our reduction also holds between the counting versions of the problems, so that we get fine-grained {\em average-case} hardness for counting PMT~under all three hypotheses as well.

\begin{theorem}
\label{thm:czkc-to-ndmt}
If (\#)Partitioned Matching Triangles can be solved in $T(n)$ time, then we can solve (\#)\czkc[3]~in time $\tilde{O}(T(n)+n^2)$.
\end{theorem}

\noindent\textbf{\emph{$\bm{k}$-color Node Labeled $st$ Connectivity.}}
In the $k$-color Node Labeled $st$ Connectivity Problem (\kNLstC) one is given an acyclic graph $G=(V,E)$ with two designated nodes $s,t\in V$, and colors on all nodes in $V\setminus \{s,t\}$ from a set of colors $C$. One is then asked whether there is a path from $s$ to $t$ in $G$ using at most $k$ node colors.

We give a fine-grained reduction from \czkc[]~to \kNLstC~that also holds between the counting versions. Here in the counting version of \kNLstC~we want to output the number of $s$-$t$ paths through at most $k$ colors, mod $\lceil2^{2k\lg^2(n)}\rceil$.

\begin{theorem} \label{thm:knlstc-hardness}
If a $O(|C|^{k-2}|E|^{1-\epsilon/2})$ or $O(|C|^{k-2-\epsilon}|E|)$ time algorithm exists for (counting mod $2^{2k\lg^2(n)}$) \kNLstC~then a $O(n^{k-\epsilon})$ algorithm exists for (\#)\czkc.
\end{theorem}

The conditional lower bound of $(|C|^{k-2}|E|)^{1-o(1)}$ resulting from the above theorem is tight. In Appendix \ref{app:algorithms}~we give the corresponding algorithm.

\noindent\textbf{\emph{$\bm{k}$-color Edge Labeled $st$ Connectivity.}}
The $k$-color Edge Labeled $st$ Connectivity problem (\kELstC[]) asks for a given acyclic graph with colored edges and given source $s$ and target $t$, if there is a path from $s$ to $t$ that uses only $k$ colors of edges.

We give conditional hardness for both the decision and counting version of the problem (where the counts are mod a small $R$). This also implies average-case hardness for the counting mod $R$ problem under all three hardness hypotheses of FGC.

\begin{theorem}
\label{kelstcCKFUNC}
If a $\tilde{O}(|E||C|^{k-1-\epsilon})$ or $\tilde{O}(|E|^{1-\epsilon}|C|^{k-1})$ time algorithm exists for (counting mod $ 2^{2k\lg^2(n)}$) \kELstC[], then a $\tilde{O}(n^{k-\epsilon})$ algorithm exists for (\#)\ckfunc[].
\end{theorem}

This is tight.  Note this algorithm is slower (by a factor of $|C|$) than the node-labeled version, however it is optimal. The corresponding algorithm is in a theorem from Appendix \ref{app:algorithms}.

\noindent\textbf{\emph{$\bm{(k+1)}$ Labeled Max Flow.}}
The $(k+1)$ Labeled Max Flow problem studied in \cite{mfml}
 asks, given a capacitated graph $G=(V,E)$ where the edges have colors, and $s,t\in V$, if there is a maximum flow from the source $s$ to the sink $t$ where number of distinct colors of the edges with non-zero flow is at most $k+1$.

\begin{theorem}
\label{klmf}
If $(k+1)$L-MF can be solved in $T(n)$ time, then we can solve \czkc~in time $\tilde{O}(T(n)+n^2)$.
\end{theorem}

This implies an $n^{k-1-o(1)}$ lower bound for $k$L-MF under all three FGC hypotheses.
We also show that for the particular structured version of the problem given in our reduction, this lower bound is tight.

\noindent\textbf{\emph{Regular Expression Matching.}}
The Regular Expression Matching problem (studied e.g. in \cite{regularexpression}) takes as input a regular expression (pattern) $p$ of size $m$ and a sequence of symbols (text) $t$ of length $n$, and asks if there is a substring of $t$ that can be derived from $p$.
The counting version of the problem, \#Regular Expression Matching asks for the number of subset alignments of the pattern in the text mod an integer $R$, where $R=n^{o(1)}$. A classic algorithm constructs and simulates a non-deterministic finite automaton corresponding to the expression, resulting in the rectangular $O(mn)$ running time for the detection version of the problem.

We give hardness from \#\ckov[2]~(mod $R$) which in turn implies average-case fine-grained hardness for counting regular expression matchings mod $R$, from SETH.

\begin{theorem}
Let $R$ be an integer where $\lg{(R)}$ is subpolynomial. If you can solve (\# mod ${R}$) regular expression matching in $T(n)$ time, then you can solve (\# mod $R$) \ckov[2]~in $\tilde{O}(T(n)+n)$ time
\label{thm:regex}
\end{theorem}
Again, we show in Appendix \ref{app:algorithms} that for the particular ``type'' of pattern used in our reduction, this lower bound is tight.

\noindent\textbf{\emph{LCS and Edit Distance.}}
The $k$-LCS problem is a basic problem in sequence alignment. Given $k$ sequences $s_1,\ldots,s_k$ of length $n$, one is asked to find the longest sequence that appears in every $s_i$ as a subsequence.
\klcs~can be solved in $O(n^k)$ time with dynamic programming and requires $n^{k-o(1)}$ time under SETH, via a reduction from \kOV~\cite{LCSisHard}. Here we show that $k$-LCS is also fine-grained hard via a reduction from \ckov[].

\begin{theorem}
\label{thm:kLCSisWorstCaseHard}
A $T(n)$ time algorithm for \klcs~with alphabet size $O(k)$ implies a $\tilde{O}(T(n))$ algorithm for \ckov[].
\end{theorem}

The Edit Distance problem is another famous sequence alignment problem. Here one is given two $n$ length sequences $a$ and $b$ and one needs to compute the minimum number of symbol insertions, deletions and substitutions needed to transform $a$ into $b$.
Edit Distance can be solved in $O(n^2)$ time via dynamic programming, and requires $n^{2-o(1)}$ time under SETH, via a reduction from OV \cite{BackursI15,BackursI18}.

In section \ref{sec:harderProblem} we show that edit distance is also fine-grained hard from \ckov[2].

\begin{theorem}
\label{thm:editDistisWorstCaseHard}
A $T(n)$ time algorithm for Edit Distance implies a $\tilde{O}(T(n))$ algorithm for \ckov[2].
\end{theorem}

\subsubsection{Counting OV is Easy on Average}
As mentioned earlier in the introduction we show that counting orthogonal vectors over the uniform distribution is easy in the average-case. Let $\#$OV$^{\mu,d}$~be the problem of solving orthogonal vectors on instances generated by sampling $n$ vectors iid from the distribution over $d$ bit vectors where every bit in the vector is sampled iid from the distribution that returns $1$ with probability $\mu$ and returns $0$ with probability $1-\mu$.

\begin{theorem}
\label{thm:avgCaseCountOVisEasy}
For all constant values of $\mu$ and all values of $d$ there exists constants $\epsilon>0$ and $\delta>0$ such that there is an algorithm for $\#$OV$^{\mu,d}$~that runs in time $\tilde{O}(n^{2-\delta})$ with probability at least $1-n^{-\epsilon}$.
\end{theorem}

\subsubsection{Counting to Detection for \texorpdfstring{Z$k$C}{Lg}}
Our worst-case to average-case reductions show hardness for counting problems. We mentioned earlier in the introduction that stronger cryptographic primitives have been built from detection problems than from counting problems.
In this paper we show that in the sufficiently low error regime there is a counting to detection reduction for the zero-$k$-clique problem. Unfortunately, this does \emph{not} give a fine-grained one-way function from worst-case assumptions. However, it makes progress towards bridging the gap between the problems we can show hard from the worst-case and those we can build powerful cryptographic primitives from.

\begin{definition}
An average case instance of Z$k$C~(ACZ$k$C) with range $R$ takes as input a complete $k$-partite graph with $n$ nodes in each partition. Every edge has a weight chosen iid from $[0,R-1]$. A clique is considered a zero $k$ clique if the sum of the edges is zero mod $R$.
\end{definition}

\begin{theorem}
\label{thm:countToDecision}
Given a decision algorithm for ACZ$k$C~that runs in time $O(n^{k-\epsilon})$ for some $\epsilon>0$ and succeeds with probability at least $1-n^{-\omega(1)}$, there is a counting algorithm that runs in $O(n^{k-\epsilon'})$ time for some $\epsilon'>0$ and succeeds with probability at least $1-n^{-\omega(1)}$, where $\omega(1)$ here means any function that is asymptotically larger than constant.
\end{theorem}

\subsubsection{Worst-Case to Average-Case Reductions}
We define the notion of a good low-degree polynomial~for the problem $P$ (a \gPol{$P$}). We define the properties of a good low-degree polynomial~in Definition \ref{def:goodPoly}. Intuitively these properties are that the function must be low degree, count the output of the problem, and have well structured monomials.
We show that any problem $P$ that has a \gPol{$P$} is hard in its uniform average case in appendix \ref{sec:Framework}. We do this using techniques from Boix{-}Adser{\`{a}} et al \cite{UniformCliqueABB}. We use the \gPol{$\cdot$} framework to show uniform average-case hardness for our counting factored problems (in section \ref{sec:compressedVariants}). We give the framework theorem statement below.

\begin{theorem}
\label{thm:framework}
Let $\mu$ be a constant such that $0 < \mu <1$.
Let $P$ be a problem such that a function $f$ exists that is a \gPol{$P$}, and let $d$ be the degree of $f$.
Let $A$ be an algorithm  that runs in time $T(n)$ such that when $\vec{I}$ is formed by $n$ bits each chosen iid from $Ber[\mu]$:
$$Pr[A(\vec{I}) = P(\vec{I})] \geq 1-1/\omega\left( \lg^d(n)\lg\lg^d(n) \right).$$
Then there is a randomized algorithm $B$ that runs in time $\tilde{O}(n + T(n))$ such that
for \emph{any} for $\vec{I} \in \{0,1\}^n$:
$$Pr[B(\vec{I}) = P(\vec{I})] \geq 1-O\left(2^{-\lg^2(n)}\right).$$
\end{theorem}

Boix{-}Adser{\`{a}} et al show that counting $k$ cliques is as hard in Erd{\H{o}}s-R{\'{e}}nyi graphs as it is in the worst case. We use the \gPol{$\cdot$}~framework a second time to slightly generalize their result to show that counting any subgraph $H$ in an Erd{\H{o}}s-R{\'{e}}nyi graph is at least as hard as counting subgraphs $H$ in worst case $k$-partite graphs (in section \ref{sec:SubgraphsWithKNodes}).

\begin{theorem}
\label{thm:ACSubgraphCountToWCSubgraphCount}
Let $H$ have $e$ edges and $k$ vertices where $k =o(\sqrt{\lg(n)})$.
Let $A$ be an average-case algorithm for counting subgraphs $H$ in Erd{\H{o}}s-R{\'{e}}nyi graphs with edge probability $1/b$ which takes $T(n)$ time with probability $1-2^{-2k} \cdot b^{-k^2} \cdot (\lg(e)\lg\lg(e))^{-\omega(1)}$.

Then an algorithm exists to count subgraphs $H$ in $k$-partite graphs in time $\tilde{O}(T(n))$ with probability at least $1-\tilde{O}(2^{-\lg^2(n)})$.
\end{theorem}

\subsection{Organization of the Paper}
In the preliminaries section \ref{sec:Prelims} we give a formal definition of our factored problems. We also define the problems that we use throughout the paper, and we give an introduction of the average-case framework which is defined formally in Appendix \ref{sec:Framework}.
We show that the factored problems are hard, and give the worst-case to average-case reductions for the factored problems in section \ref{sec:compressedVariants}.
In section \ref{sec:harderProblem}, we show that our factored problems can show hardness for many natural non-factored problems.
We use the same framework that gives average-case hardness for the factored problems to show that counting arbitrary subgraphs in random graphs is hard in section \ref{sec:SubgraphsWithKNodes}. We give a fast algorithm for counting OV over the uniform average-case in section \ref{sec:OV}. We give counting to detection reduction for average-case zero-$k$-clique with high probability in section  \ref{sec:countToDetect}. Finally, we list problems that seem like promising future work in section \ref{sec:FutureWork}.

We give the efficient algorithms for our factored problems and the problems that reduce from our factored problems in appendix \ref{app:algorithms}. We give the framework that generalizes the techniques of Boix{-}Adser{\`{a}} et al. in appendix \ref{sec:Framework}.

\section{Introduction}
\label{sec:Intro}
\input{Intro.tex}

\section{Preliminaries}
\label{sec:Prelims}
\input{Prelims.tex}

\section{Factored Problems are Hard}
\label{sec:compressedVariants}
\input{compressed.tex}

\section{Implications from Factored Variants}
\label{sec:harderProblem}
\input{AHarderProblem}

\section{Average Case Hardness for Subgraph Counting}
\label{sec:SubgraphsWithKNodes}
\input{SmallSubGraphs.tex}

\subsection{Inclusion-Edgesculsion}
\label{sec:edgesclusion}
\input{edgesclusion.tex}

\section{Counting OV is Easy on Average}
\label{sec:OV}
\input{OrthogonalVectors.tex}

\section{Counting to Detection Reduction for Average-Case \texorpdfstring{Z$k$C}{Lg}}
\label{sec:countToDetect}
\input{countToDetect}

\section{Future Work}
\label{sec:FutureWork}
\input{futureWork}

\section*{Acknowledgements}
We would like to acknowledge Marshall Ball for interesting and helpful early discussions.

We would like to acknowledge all our reviewers for helpful comments. We thank all the reviewers for advice about improving the readability of the paper. We would like to extend special thanks to reviewer 1 who noted that we could improve the definition of good low-degree polynomial~by removing a restriction!

\let\realbibitem=\par \vspace{-0.5ex}\realbibitem
\def\par \vspace{-0.5ex}\realbibitem{\par \vspace{-0.5ex}\realbibitem}

\bibliographystyle{alpha}

\subsection{Hypotheses about Core Problems of Fine-Grained Complexity}

\begin{definition} [The $3$-SUM Hypothesis \cite{C3sum}]
	In the \emph{\ksum[]~problem}, we are given an unsorted list $L$ of $n$ values (over $\mathbb Z$ or $\mathbb R$) and want to determine if there are $a_1, \ldots, a_k \in L$ such that $\sum_{i=1}^k a_i = 0$. The counting version of \ksum[]~asks how many sets of $k$ numbers $a_1, \ldots, a_k \in L$ sum to zero.

The \ksum[]~hypothesis states that that the \ksum[]~problem requires $n^{\lceil k/2 \rceil -o(1)}$ time \cite{C3sum}.

This is equivalent to saying no $n^{\lceil k/2 \rceil-\epsilon}$ time algorithm exists for \ksum[]~for constant $\epsilon>0$.

	\label{def:ksum}
\end{definition}

\begin{definition}[APSP Hypothesis \cite{CAPSP}]
APSP takes as input a graph $G$ with $n$ nodes (vertices), $V$ and $m$ edges, $E$. These edges are given weights in $[-R,R]$ where $R = O(n^c)$ for some constant $c$. We must return the shortest path length for every pair of vertices $u,v \in V$. The length of a path is the sum of the edge weights for all edges on that path.

The APSP Hypothesis states that the APSP problem requires $n^{3-o(1)}$ time when $m=\Omega(n^2)$.

\label{def:apsp}
\end{definition}

\begin{definition}[Strong Exponential Time Hypothesis (SETH) \cite{cseth}]
Let $c_k$ be the smallest constant such that there is an algorithm for $k$-CNF SAT that runs in $O(2^{c_k n +o(n)})$ time.

SETH states that there is no constant $\epsilon>0$ such that $c_k \leq 1-\epsilon$ for all constant $k$.
\end{definition}

Intuitively SETH states that there is no constant $\epsilon>0$ such that there is a $O(2^{n(1-\epsilon)})$ time algorithm for $k$-CNF SAT for all constant values of $k$.

\begin{definition} [The $k$-OV Hypothesis \cite{ryanThesis}]
In the \emph{$k$-OV~problem}, we are given $k$ unsorted lists $L_1,\ldots, L_k$ of $n$ zero-one vectors of length $d$ as input. If there are $k$ vectors $v_1 \in L_1,\ldots,v_k \in L_k$ such that for $\forall i\in[1,d]~\exists j\in[1,k]$ such that $v_i[j]=0$ we call these $k$ vectors an orthogonal $k$-tuple. One should return true if there is an orthogonal $k$-tuple in the input. The counting version of $k$-OV~(\#$k$-OV) asks for the number of orthogonal $k$-tuples.

The $k$-OV~hypothesis states that that the $k$-OV~problem requires $n^{k-o(1)}$ time \cite{ryanThesis}.

This is equivalent to saying no $O(n^{k-\epsilon})$ time algorithm exists for $k$-OV for constant $\epsilon>0$.

	\label{def:kOV}
\end{definition}
\subsection{Graphs}

\begin{definition}
Let $H=(V_H,E_H)$ be a $k$-node graph with $V_H=\{x_1,\ldots,x_k\}$.

An $H$-partite graph is a graph with $k$ partitions $V_1,\ldots,V_k$. This graph must only have edges between nodes $v_i \in V_i$ and $v_j \in V_j$ if e $(x_i,x_j)\in E_H$. (See Figure \ref{fig:Hpartite})
\end{definition}

\begin{figure}[ht]
\centering
\includegraphics[width=0.8\textwidth]{HPartiteImage.pdf}
\caption{An example of the corresponding $H$-partite graphs. }
\label{fig:Hpartite}
\end{figure}

\subsection{Good Low-Degree Polynomials}
We define the good low-degree polynomial~for a problem $P$ ($\gPol{P}$). In Appendix \ref{sec:Framework} we provide a framework which shows that if a problem $P$ has a  $\gPol{P}$ then $P$ is hard over the uniform average case. The proof of this framework is a generalization of the proof in Boix et al. \cite{UniformCliqueABB}. We use this to show average-case hardness for counting versions of factored problems and counting subgraphs in sections \ref{sec:compressedVariants} and \ref{sec:SubgraphsWithKNodes} respectively.

\begin{definition}
Let the polynomial  $f$ have $n$ inputs $x_1,\ldots, x_n$.
We say $f$ is \textit{strongly $d$-partite} if one can partition the inputs into $d$ sets $S_1,\ldots, S_d$ such that $f$ can be written as a sum of monomials $\sum_i x_{1,i}\cdots x_{d,i}$, where every variable $x_{j,i}$ is from the partition $S_j$.
That is, if there is a monomial $x_{i_1}^{c_1} \cdots x_{i_k}^{c_k}$ in $f$ then it must be that $c_j =1 $ and for all $j \ne \ell$ if $x_{i_j} \in S_m$ then $x_{i_\ell} \notin S_m$.
\end{definition}

\begin{definition}
Let $P(\vec{I})$ be the correct output for problem $P$ given input $\vec{I}$.
\end{definition}

\begin{definition}
Let $n$ be the input size of the problem $P$, let $P$ return an integer in the range $[0,p-1]$ where $p$ is a prime and $p < n^c$ for some constant $c$.
A \emph{good low-degree polynomial} for problem $P$  (\gPol{P})  is a polynomial $f$ over a prime finite field $F_{p}$ where:
\begin{itemize}

    \item If $\vec{I} = b_1,\ldots, b_n$, then
    $f(b_1,\ldots, b_n) = f(\vec{I})=P(\vec{I})$ where $b_i$ maps to either a zero or a one in the prime finite field.
    \item The function $f$ has degree $d = o\left( \lg(n)/\lg\lg(n) \right)$.
    \item The function $f$ is strongly $d$-partite.
\end{itemize}
\label{def:goodPoly}
\end{definition}

\subsection{Factored Problems}
\label{subsec:prelimsCompressed}

We introduce a more expressive extension of $k$-SUM, $k$-OV, $k$-XOR, and Z$k$C.
At a high level this extension takes every number or vector from the original problems and splits them up into $g =o(\lg(n)/\lg\lg(n))$ groups of numbers or vectors with bit representations of size $b =o(\lg(n))$. If the original numbers had length $\ell$, then $\ell \approx b\cdot g$. Then, we allow each group to contain multiple numbers or vectors.

We start by giving a definition of \ckov[], then we give a small example of \ckov[2]. Next, we follow up with the analogously defined \cksum[],\ckxor[], and FZT. Finally, we give algorithms for these problems in the Appendix \ref{app:algorithms}.

\subsubsection{\texorpdfstring{F$k$-OV}{Lg}, Intuition and Examples}

\begin{definition}
A $(g,b)$-{\em factored vector} $v$ is defined by $g$ sets $(v[1],\ldots,v[g])$ where each $v[i]\subseteq \{0,1\}^b$ is a set of $b$-dimensional binary vectors.

For a set of vectors $\vec{w_1},\ldots,\vec{w_k}$ of the same dimension $d$,
let $isOrthogonalTuple(\vec{w_1},\ldots,\vec{w_k})$ return $1$ iff $\vec{w_1},\ldots,\vec{w_k}$ are orthogonal, i.e. iff $\sum_{a=1}^d \prod_{j=1}^k w_j[a]~= 0$, where $w_j[a]$ is the $a^{th}$ bit of the vector $w_j$.

Now we define a useful operator, $\circ$ for a set $\{Z_1,\ldots, Z_k\}$ where each $Z_i$ is a set of $d$-dimensional binary vectors as follows.
$$\circ(Z_1,\ldots,Z_k) :=  \sum_{\vec{w_1}\in Z_1, \ldots, \vec{w_k} \in Z_k} isOrthogonalTuple(\vec{w_1},\ldots,\vec{w_k}).$$

Now, given $k$ $(g,b)$-factored vectors $v_1,\ldots,v_k$ the number of orthogonal vectors within those factored vectors is $\circledcirc(v_1,\ldots,v_k) := \Pi_{i=0}^{g-1}\circ(v_1[i],\ldots,v_k[i]).$

The input to \ckov[]~is $V_1,\ldots, V_k$, where each $V_j$ is a set of $n$ $(g,b)$-factored vectors, where $g = o(\lg(n)/\lg\lg(n))$ and $b= o(\lg(n))$.
The total number of orthogonal vectors in a given \ckov[]~instance is
$$\sum_{v_1,\ldots,v_k \in V_1,\ldots, V_k}\circledcirc(v_1,\ldots,v_k).$$

The \ckov[]~problem
asks to determine whether $\sum_{v_1,\ldots,v_k \in V_1,\ldots, V_k}\circledcirc(v_1,\ldots,v_k)>0$.
\end{definition}

\paragraph{An Example: }
We give a small example bellow. Consider \ckov[2]~where $g=2$ and $b={3}$. We give an example of factored vectors $u$, $v$ and $w$:
\begin{align*}
   &u[0] = \{001,010\} \text{~~} & u[1] = \{001,010\}\\
   &v[0] = \{000,010,110\} \text{~~} & v[1] = \{110,101\}\\
   &w[0] = \{\} \text{~~} & w[1] = \{000,011,100,111\}
\end{align*}

First, note that $\circledcirc(w,u) = \circledcirc(w,v) = 0$ trivially because $w[0]$ is the empty set. Empty sets are valid in this factored representation, but, rather degenerate.
Next, note that $\circledcirc(v,u)$ is $4 \cdot 2 = 8$. For $\circ(u[0],v[0])$ all of $(001,000), (001,010), (001, 110),$ and $ (010,000)$ are orthogonal.  For $\circ(u[1],v[1])$ both $(001,110),$ and $(010,101)$ are orthogonal.

\paragraph{A Natural Interpretation:} We can generate a $$k$-OV$ instance by interpreting a factored vector as representing $|v_1|\cdot \ldots \cdot |v_k|$ vectors. For example $u$ in the above example would represent the following list of vectors:
$$ 001001, 001010, 010001, 010010.$$
As another example $v$ would represent the following list of vectors:
$$ 000110, 000101, 010110, 010101, 110110, 110101.$$
Finally, $W$ represents no vectors, because $w[0]$ is the empty set.

However, the number of vectors that can be represented by a single factored vector that has a $g2^b$ sized representation is $2^{bg}$. While $g2^b$ is sub-polynomial, $2^{bg}$ can be super polynomial (e.g. if $b=g=\lg(n)^{3/2}$)!

\subsubsection{Definitions for \texorpdfstring{F$k$-$\mathfrak{f}$}{Lg}, \texorpdfstring{F$k$-SUM}{Lg}, \texorpdfstring{F$k$-XOR}{Lg}, and FZT}

\begin{definition}
Let $f:(\{0,1\}^b)^{\times k} \rightarrow \{0,1\}$ be a function taking $k$ $b$-dimensional binary vectors to $\{0,1\}$. We can view $f$ as a Boolean function.

Let us define an operator for $f$, $\circ_f$, that takes $k$ factored vectors $a_1,\ldots,a_k$ and computes the number of $k$-tuples of vectors, one in each $a_i$, that $f$ accepts:
$$\circ_f(a_1,\ldots,a_k) =  \sum_{\vec{w_1}\in a_1 \ldots \vec{w_k} \in a_k} f(\vec{w_1},\ldots,\vec{w_k}).$$

If $v$ is a $(g,b)$-factored vector let, for $i\in [g]$, $v[i]$ be the $i^{th}$ set of vectors in $v$.

Given $(g,b)$-factored vectors $v_1,\ldots,v_k$ the number of $k$-tuples of vectors accepted by $f$ within those factored vectors is $\circledcirc_f(v_1,\ldots,v_k) = \Pi_{i=0}^{g-1}\circ_f(v_1[i],\ldots,v_k[i]).$

For each $f$, we define a problem \ckfunc[].
The input to \ckfunc[]~is $k$ sets, $V_1,\ldots, V_k$, of $n$ $(g,b)$-factored vectors each, where $g = o(\lg(n)/\lg\lg(n))$ and $b= o(\lg(n))$.

The total number $k$-tuples of vectors accepted by $f$ in a given \ckfunc[]~instance is
$$\textrm{F}k\textrm{-}f(V_1,\ldots,V_k):=\sum_{v_1,\ldots,v_k \in V_1,\ldots, V_k}\circledcirc_f(v_1,\ldots,v_k).$$

The \ckfunc[]~problem returns true iff $\textrm{F}k\textrm{-}f(V_1,\ldots,V_k)>0$.
More generally, the counting version $\#$\ckfunc[]~of \ckfunc[]~asks to compute the quantity $\textrm{F}k\textrm{-}f(V_1,\ldots,V_k)$.

\end{definition}

\begin{definition}
\ckxor[]~is the problem \ckfunc[]~where $f$ is $1$ if the componentwise XOR of the $k$ given vectors is the $0$ vector:
$$f(v_1, \ldots, v_k) =
\begin{cases}
1, & \text{if } v_1 \oplus \ldots \oplus v_k = \vec{0} \\
0, & \text{else}
\end{cases}.$$
\end{definition}

\begin{definition}
\cksum[]~is the problem \ckfunc[]~where $f$ that checks if the sum of the $k$ vectors is the $0$ vector:
$$f(v_1, \ldots, v_k) =
\begin{cases}
1, & \text{if } v_1 + \ldots + v_k = 0\\
0, & \text{else}
\end{cases}.$$
\end{definition}

\begin{definition} For an integer $k$, $\ell=\binom{k}{2}$ and a given function $f:\{0,1\}^{b\ell}\rightarrow \{0,1\}$, construed as taking $\ell$-tuples of $b$-length binary vectors to $\{0,1\}$,
let $\#$\cfkc~be the problem of counting cliques in a graph whose edges are labeled with factored vectors, where a clique is counted with multiplicity the number of $\ell$-tuples of vectors that $f$ accepts and that appear in the $\ell$ factored vectors labeling the edges.

More formally, we change the definition of the operation $\circledcirc_f(\cdot)$ to take as input $k$ vertices $v_1,\ldots,v_k$ of a given graph $G=(V,E)$ whose edges $(x,y)\in E$ are labeled by $(g,b)$-factored vectors $e_{x,y}$:
$$
\circledcirc'_{f}(v_1,\ldots,v_k) = isClique(v_1,\ldots,v_k)\cdot\Pi_{i=0}^{g-1}\circ_f(e_{v_1,v_2}[i],e_{v_1,v_3}[i], \ldots,e_{v_{k-1},v_k}[i]).
$$

Above $isClique(v_1,\ldots,v_k)$ outputs $1$ if $v_1,\ldots,v_k$ form a $k$-clique in $G$, and otherwise outputs $0$.

We keep the definition of $\circ_f(\cdot)$ the same as before, but now its input is a list of $\ell$ sets of vectors that are the $i$th group of vectors of the factored vectors labeling the clique edges: $$\circ_f(e_1[i],\ldots,e_{\ell}[i]) =  \sum_{\vec{w_1}\in e_1[i]~\ldots \vec{w_\ell} \in e_{\ell}[i]} f(\vec{w_1},\ldots,\vec{w_\ell}).$$

Finally, we let $\#$\cfkc be the problem of computing
$$\textrm{F}fk\textrm{C}(G):=\sum_{v_1,\ldots,v_k\in V} \circledcirc'_f(v_1,\ldots,v_k).$$

Here, unlike for $\#$F$\ell$-f, we are only counting the sums of factored vectors when those factored vectors are on a set of $\ell=\binom{k}{2}$ edges that form a $k$ clique. Let \cfkc be the detection version of the problem that returns $1$ if $\textrm{F}fk\textrm{C}(G)>0$ and $0$ otherwise.
\end{definition}

\begin{definition}
Factored Zero $k$-Clique, \czkc~is the \cfkc~problem~where $f$ is the sum function for $\binom{k}{2}$ variables defined in the definition of \cksum[]~.
\end{definition}

\begin{definition}
Factored Zero Triangle, FZT~is \czkc[3].
\end{definition}

\subsubsection{Hypotheses for Factored Problems}

First we will define the hypotheses for our factored list problems.

In many lemma, theorem and definition statements we will use a structure where we put $(\#)$ before several problem or hypothesis names. This structure means that the statement is true for all non counting versions, or for all counting versions.  For example, in the first line below the two implies statements are:\\
``The  \ckov[]~hypothesis (i.e.\ckovh[]) states that \ckov[]~requires $n^{k-o(1)}$ time.''
 \\
 and ``The  \#\ckov[]~hypothesis (i.e.\#\ckovh[]) states that  \#\ckov[]~requires $n^{k-o(1)}$ time.''.

\begin{definition}
The  (\#)\ckov[]~hypothesis (i.e.(\#)\ckovh[]) states that  (\#) \ckov[]~requires $n^{k-o(1)}$ time.

The  (\#)\cksum[]~hypothesis (i.e.(\#)\cksumh[]) states that  (\#) \cksum[]~requires $n^{k-o(1)}$ time.

The  (\#)\ckxor[]~hypothesis (i.e.(\#)\ckxorh[]) states that  (\#)\ckxor[]~requires $n^{k-o(1)}$ time.

The  (\#)\ckfunc[]~hypothesis (i.e.(\#)\ckfunch[]) states that  (\#)\ckfunc[]~requires $n^{k-o(1)}$ time.
\end{definition}

Now we will define the hypotheses for our factored clique problems.

\begin{definition}
The  (\#)\czkc~hypothesis (i.e.(\#)\czkch) states that (\#) \czkc~requires $n^{k-o(1)}$ time.

The  (\#)\cfkc~hypothesis (i.e.(\#)\cfkch) states that  (\#) \cfkc~requires $n^{k-o(1)}$ time.
\end{definition}

\subsubsection{Average-Case for Factored Problems}

We will separate the average-case distribution of factored problems into the normal case and a more-general parameterized case.

\begin{definition}[More General Average-Case]
Let $S_{b,\mu}$ be a distribution over sets of vectors from $\{0,1\}^b$. A set drawn from $S_{b,\mu}$ includes every vector $w \in \{0,1\}^b$ with probability $\mu$.

Let $D_{g,b,\mu}$ be a distribution over factored vectors $v$ where all $g$ sets of $v[i]$ are sampled iid from $S_{b,\mu}$.

The average-case distribution for \#\ckfunc[]$^{\mu}$ samples every factored vector in its input iid from $D_{g,b,\mu}$.

The average-case distribution for \#\cfkc[]$^{\mu}$ samples every factored vector in its input iid from $D_{g,b,\mu}$.
\label{def:muavgCasefactored}
\end{definition}

For the average-case we use in this paper we use $\mu=1/2$. We feel this is the most natural distribution for our problem. We will occasionally call this the ``uniform average-case'' to emphasize that every set $v[i]$ in every factored vector is chosen uniformly at random from all possible subsets of $\{0,1\}^b$.

\begin{definition}
The average-case distribution for \#\ckfunc[]~samples every factored vector in its input iid from $D_{g,b,1/2}$.

The average-case distribution for \#\cfkc[]~samples every factored vector in its input iid from $D_{g,b,1/2}$.
\label{def:avgCaseFactored}
\end{definition}

\subsection{Problems harder than factored problems}
Here we define problems that later are shown to be hard via reductions from the factored problems. We state the known results for each, and a simple algorithm for each is given in Appendix \ref{app:algorithms} that matches the lower bound we prove later.

\begin{definition}
The \textbf{Partitioned Matching Triangles (PMT)} problem takes as input $g=O(\log{n}/\log\log{n})$ disjoint $n$-node graphs with node colors, and asks if there is a triple of colors with a triangle of that color triple in each of the $g$ graphs. The counting version of the problem, \textit{$\#$PMT}, asks for the number of such $g$-tuples of colored triangle.
\end{definition}

This problem is very similar to the \textit{$\Delta$ Matching Triangles} problem defined in \cite{matchingTriangles}, where given an $n$-node graph $G$ with node colors, the problems asks if there is a triple color with $\Delta$ triangles of that color triple in $G$.

In \cite{matchingTriangles}, $3$SUM, APSP and SETH are reduced to $\Delta$ Matching Triangles where the instances produced can be represented as instances of Partitioned Matching Triangles instance for $g=\Delta$. So Partitioned Matching Triangles is hard from $3$SUM, APSP and SETH. A related problem to PMT is the \textit{node disjoint triangle packing} problem which asks to find a maximum size node-disjoint triangle packing in a given graph (see for example \cite{caprara2002packing}). PMT is a natural mix of the $\Delta$-matching-triangle and the node disjoint triangle packing problems.

\begin{definition}
\textbf{Node Labeled $k$-Color $st$ Connectivity (\kNLstC)} takes as input a directed graph $G$ with edge set $E$ and vertex set $V$, two special nodes $s$ and $t$, and a proper coloring of the vertices $c:~V\setminus \{s,t\}\rightarrow C$, where $C$ is a set of colors, so that the endpoints of every edge have different colors and $s$ and $t$ have all their neighbors colored distinctly.
The input graph $G$ is a layered graph, the vertex set $V$ is partitioned into $V_0, V_1,\ldots,V_\ell$, such that every directed edge goes from a node in set $V_i$ to a node in set $V_{i+1}$ for some $i\in \{0,\ldots,\ell-1\}$.
The \kNLstC~problem asks if there is a path from $s$ to $t$ that uses only $k$ colors of nodes (where $s$ and $t$ are not counted for colors)
\end{definition}

We also consider the problem of Counting \kNLstC~mod $R$, in which we ask for the total number of paths from $s$ to $t$ that use at most $k$ colors of nodes. We will generally use values of $R$ such that $\lg(R)$ is subpolynomial, as this allows us to represent the count with a subpolynomial number of bits.

\begin{definition}
The \textbf{$k$ Edge Labeled (directed/undirected) $st$ Connectivity (\kELstC[])} problem takes as input a directed acyclic graph $G=(V,E)$, two special vertices $s$ and $t$ and a coloring of the edges $c:E\rightarrow C$, where $C$ is a set of colors.

\kELstC[]~asks, given this input can you pick $k$ colors such that there is a path from $s$ to $t$ using only edges that are colored by one of those $k$ colors? The counting version of \kELstC[], $\#$\kELstC[]~asks for the number of paths from $s$ to $t$ mod $R$ that use only $k$ colors, where $\lg(R) = n^{o(1)}$.
\end{definition}

\begin{definition}
The \textbf{Bounded Labeled Maximum Flow (BL-MF)} problem \cite{mfml} takes as input a directed, capacitated, and edge-labeled graph $G=(V,E)$ with a source node $s\in V$, a sink node $t\in V$, and a positive integer $k$, and asks if there is a maximum flow $x$ from $s$ to $t$ in $G$ such that the
total number of different labels corresponding to arcs $(i,j)\in E$ with non-zero flow is less than or equal to $k$. For fixed constant $k$, we refer to the problem as $k$L-MF.
\end{definition}

BL-MF is the decision version of the maximum flow with the \textit{minimum number of labels (MF-ML)} problem where we seek a maximum flow from $s$ to $t$ that uses the minimum number of labels. \cite{mfml} uses this problem to model the purification of water during the distribution process. They show that BL-MF is NP-complete. Let \textit{BL-MF*} be a slightly more restricted version of BL-MF where the number of edges of each label is $o(n)$ and the edges attached to the sink and source have a special label $l^*$.
We show a lower bound of $O(n^{k-1})$ for $k$L-MF* (and thus $k$L-MF) for fixed $k$, and show that it has a matching algorithm as well

\begin{definition}
The \textbf{Regular Expression Matching} problem \cite{regularexpression} takes as input a regular expression (pattern) $p$ of size $m$ and a sequence of symbols (text) $t$ of length $n$, and asks if there is a substring of $t$ that can be derived from $p$.
The counting version of the problem, \#Regular Expression Matching asks for the number of subset alignments of the pattern of the pattern in the text mod an integer $R$, where $R=n^{o(1)}$.
\end{definition}

A classic algorithm constructs and simulates a non-deterministic finite automaton corresponding to the expression, resulting in the rectangular $O(mn)$ running time.

\begin{definition}
The (counting) \textbf{$k$-Longest Common Subsequence ((\#)\klcs)} problem (see for example \cite{LCSdef}) takes as input $k$  sequences $P_1, \ldots, P_k$ of
length $n$ over an alphabet $\Sigma$. Let $\ell$ be the length of the longest sequence $X$ such that $X$ appears in all of $P_1, \ldots, P_k$ (in the same order).

\klcs~ asks for the value of $\ell$, while \#\klcs~asks to compute $\ell$ and also the total {\em number} of common subsequences of length $\ell$.

More formally, define $C_{\#}(X_i)$ to be the total number $k$-tuples of $\ell$ sequence locations in each of our $k$ strings such that those locations map onto the sequence $X_i$ for all $k$ strings when $X_i$ is of length $\ell$. Let $X_1, X_2, \ldots X_j$ be all possible sequences of length $\ell$ that appear in all of $P_1, \ldots, P_k$. For the \#\klcs~problem we ask for the value of $\ell$ and the value of $\Pi_{i=1}^j C_{\#}(X_i)$.
\end{definition}

\begin{definition}
The \textbf{Edit Distance} problem (see for example \cite{BackursI15}) takes as input two sequences $x$ and $y$ over an alphabet $\Sigma$, and asks to output the edit distance $EDIT(x, y)$ which is equal to the minimum number of symbol insertions, symbol deletions or symbol substitutions needed to transform $x$ into $y$.
\end{definition}
\subsection{Reducing counting \texorpdfstring{$H$}{Lg} subgraphs in \texorpdfstring{$H$-partite}{Lg} fashion to uniform counting}

We start by reducing CHGHP~to UCHGHP. Our ultimate goal is to reduce CHGHP~to counting $H$ subgraphs in an Erd{\H{o}}s-R{\'{e}}nyi graph.

\begin{lemma}
Let $H$ be a $k$-node graph with vertices $V_H=\{x_1,\ldots,x_k\}$ and $G$ a $H$-partite $n$-node graph with vertex set partition $V_1,\ldots,V_k$.
Let $\vec{E}$ be the set of variables $\{e(v_i,v_j)| i\neq j, v_i\in V_i, v_j\ \in V_j \}$ when an edge variable is a $1$ if that edge exists and $0$ if the edge is absent in $G$.
Let $h(v_1, \ldots ,v_k)$ be a function that multiples $e(v_i,v_j)$ if $x_ix_j$ is an edge in $H$ for all $i,j \in [1,k]$ where $i \ne j$.
If $p$ is a prime in $[2n^k, n^{2k}]$,
the following function returns the output of CHGHP~on $G$:
$$f(\vec{E}) = \sum_{v_1 \in V_1,\ldots,v_k \in V_k} h(v_1, \ldots ,v_k) \pmod{p}.$$
\label{lem:smallKSugraphPoly}
\end{lemma}
\begin{proof}

Consider the function $h$: If $v_1, \ldots ,v_k$ in that particular order contain the graph $H$ it returns $1$, otherwise it returns $0$. Specifically, we are checking if our particular permutation of these variables completely covers the (arbitrary) permutation of variables associated with the input sub-graph $H$.

Now $f$ sums over all choices of $k$ nodes from each partition and counts how many instances of the sub graph appear in each. There is no double counting because every set of $k$ nodes differs by at least one node.
\end{proof}

\begin{lemma}
The function $f$ defined in Lemma \ref{lem:smallKSugraphPoly} is a good low-degree polynomial~for CHGHP~if the number of edges in $H$ is $o(\lg(n)/\lg\lg(n))$.
\label{lem:gpolForSmallK}
\end{lemma}
\begin{proof}
To prove the lemma, first note that $f$ is a polynomial over a prime finite field $F_{p}$ for some prime $p \in [2n^k, n^{2k}]$,
and the number of monomials in $f$ is $O(n^k \cdot k!)$, which is polynomial. By Lemma \ref{lem:smallKSugraphPoly} the function $f$ returns the same value as CHGHP~ when it is given zero-one inputs.

Let $|E_H|$ be the number of edges in $H$. The function $f$ has degree $|E_H| = o\left( \lg(n)/\lg\lg(n) \right)$. In fact given constant $k$, $f$ has constant degree. This is because $f$ is formed with a sum over monomials $h(v_1,\ldots,v_k)$, which have degree $|E_H|\le \binom{k}{2}$

Finally, the function $f$ is strongly $|E_H|$-partite.
There are $|E_H|$ partitions of edges. The function $f$ is a sum over calls to $h$ where $h$ takes as input one variable from each of those edge partitions and multiplies all of them.
\end{proof}

\begin{corollary}
Let $d=\binom{k}{2}$ and $k=o(\sqrt{\lg(n)/\lg\lg(n)})$.
 If an algorithm exists to solve UCHGHP~in time $T(n)$ with probability $1-1/\omega\left( \lg^{d}(n)\lg\lg^d(n) \right)$, then an algorithm exists to solve CHGHP~in time $\tilde{O}(T(n) +n^2)$ with probability at least $1-O\left(2^{-\lg^2(n)} \right)$.
\end{corollary}
\begin{proof}
If $k=o(\sqrt{\lg(n)/\lg\lg(n)})$ then the size of the edge set in $H$, $E_H$ is at most $\binom{k}{2}=d = o(\lg(n)/\lg\lg(n))$.
Using Theorem \ref{thm:framework} we simply need that a good low-degree polynomial~for CHGHP~exists.
By Lemma \ref{lem:gpolForSmallK}, the function $f$ from Lemma \ref{lem:smallKSugraphPoly} is a \gPol{CHGHP}.
\end{proof}

\begin{corollary}
Let $H$ be a sub-graph with an edge set $E_H$ where $|E_H| = o(\lg(n)/\lg\lg(n))$. Let $d=|E_H|$.
 If an algorithm exists to solve UCHGHP~in time $T(n)$ with probability $1-1/\omega\left( \lg^{d}(n)\lg\lg^d(n) \right)$, then an algorithm exists to solve CHGHP~in time $\tilde{O}(T(n) +n^2)$ with probability at least $1-O\left(2^{-\lg^2(n)} \right)$.
 \label{cor:uchpghImpliescpgh}
\end{corollary}
\begin{proof}
We have that $E_H$ is at most $ \binom{k}{2}=d = o(\lg(n)/\lg\lg(n))$.
Using Theorem \ref{thm:framework} we simply need that a good low-degree polynomial~for CHGHP~exists.
By Lemma \ref{lem:gpolForSmallK}, the function $f$ from Lemma \ref{lem:smallKSugraphPoly} is a \gPol{CHGHP}.
\end{proof}

redpajama_set_name: RedPajamaArXiv