<p><strong>Passing to the dual hypergraphs to look for products.</strong></p>

<p>As you mention in the comments, we may interpret the bitstrings contained in $A$, $B$, and $C$ as edges in hypergraphs.</p>

<ul>
<li>Vertices are the elements of $[n]$; </li>
<li>An edge $x \in \{0,1\}^n$ contains a vertex $v \in [n]$ if $x_v = 1$.</li>
</ul>

<p>(Because these are multi-sets, they're actually multi-hyper-graphs. We may consider the edges to have some generic labels to distinguish them.) We may consider the dual hypergraph $H$ in which the vertices and the edges are interchanged; that is, where</p>

<ul>
<li>The (labelled) bitstrings $x \in \{0,1\}^n$ now distinct vertices, and</li>
<li>A bitstring $x \in \{0,1\}^n$ belongs to an edge represented (that is, labelled) by $e \in [n]$ if and only if $x_e =1$;</li>
</ul>

<p>&mdash; that is, a bitstring $x \in \{0,1\}^n$ describes all of the edges which are incident to it; of which there are always $n$ in this graphical model, albeit some of them may be the "empty edge".
This puts us in a much better position to describe the hypergraph as a product in some conventional manner. The hypergraph $H_C$ obtained from a multiset $C$ now has a composite number of vertices $m$:  we would like hypergraphs $H_A$ and $H_B$ such that $V(H_C)$ has some particular bijective correspondance with $V(H_A) \times V(H_B)$.</p>

<p><strong>A diagonally restricted tensor product of hypergraphs.</strong></p>

<p>Consider the alternative formulation of the problem, replacing bit-wise OR with bit-wise AND, alluded to in the recent revision of the problem. (To do this, we take the bitwise complement of all of the bitstrings.)  The Cartesian bit-wise <strong><em>meet</em></strong> condition (rather than "join", as we're using "$\wedge$" now in place of "$\vee$") corresponds to the existence of a particular bijection $$\varphi: V(H_A) \times V(H_B) \to V(H_C)$$ such that the edge labelled $e \in [n]$ in $H_C$ contains only the vertices $\varphi(a,b) \in V(H_C)$ such that both $a \in V(H_A)$ and $b \in V(H_B)$ are contained in the respective edges labelled by $e$ in $H_A$ and $H_B$. This seems somewhat different from most graph products, in that we do not take combinations of arbitrary edges, but only those with consistent labels.</p>

<ul>
<li><p>If we suspended this label consistency condition, the join construction would correspond to a hypergraph tensor product (generalizing the <a href="http://en.wikipedia.org/wiki/Tensor_product_of_graphs" rel="nofollow">tensor product of graphs</a>, also commonly known as the direct product in the literature), in which we define edge-pairs $(e,f) \in E(H_A) \times E(H_B)$ which contain all vertices $(a,b) \in V(H_A) \times V(H_B)$ such that $a \in e$ and $b \in f$. This glosses over some issues to do with edges which contain $(a,b)$ and $(a,b')$ for a fixed co-ordinate $a$; but the construction we consider is appropriate to hypergraphs, taking the tensor product of the incidence matrices (characteristic functions of the edges, ranging over the vertices) to form the incidence matrix of $H_A \otimes H_B$.</p></li>
<li><p>To re-obtain the Cartesian bit-wise join of $H_A$ and $H_B$, we must 
restrict to the diagonal edges $(e,e) \in E(H_A) \times E(H_B) =
   [n] \times [n]$, which we re-label by $(e,e) \mapsto e$. Note that $H_A$ and $H_B$ are edge-labelled hypergraphs, as their edges are non-negotiably labelled by the elements of $[n]$ from the formulation of the vertices as bitstrings with a fixed order. (Of course, when we are <em>searching</em> for hypergraphs $H_A$ and $H_B$, re-labelling the edges simply corresponds to considering a different hypergraph.) Selecting the diagonal is a plausible restriction, if somewhat unnatural in the context of graph products.</p></li>
</ul>

<p><strong>The resulting reformualtion.</strong></p>

<p>From this, asking "does $C$ arise from the Cartesian bitwise join of $A$ and $B$?" is equivalent to asking:</p>

<blockquote>
  <p>Is an edge-labelled hypergraph $H_C$ with $m$ vertices and at msot $n$ edges, with distinct edge-labels selected from $[n]$ isomorphic to the diagonal subgraph (<em>i.e.</em> taking only the diagonally labelled edges) of the tensor product $H_A \otimes H_B$ of two labelled hypergraphs $H_A$ and $H_B$, which also have at most $n$ edges each and also have edges labels over $[n]$?</p>
</blockquote>

<p>I'm not sure if you're going to come closer to a natural graph product formulation of than this. I rather suspect that if this does play a deep role in computational complexity that someone has studied something like this; but without knowing what areas of complexity theory it is pertinent to, I would not be able to tell you where to look, beyond perhaps investigating tensor products of hypergraphs.</p>

CC BY-SA 3.0
2012-10-17T18:53:44.543Z
+1 for considering the dual hypergraph which was just musing minutes ago might work & looks promising, am suspecting might make the hypergraph product theory (some good refs on that) relevant. found suresh's ref to the dual hypergraph based on reading your Q/A list & your question on hypergraph coloring. hope to have more comments after further review....
vzn
CC BY-SA 3.0
2012-10-17T20:58:27.317Z
still have to dig into this but this is a ref turned up on hypergraph products earlier (before posting question) which has a somewhat new yet somewhat fleshed out theory incl a prime factorization thm! what do you think, does any of this fit? [hypergraph products by gringmann](http://www.bioinf.uni-leipzig.de/conference-registration/09herbst/talks/402_Gringmann.pdf) .. note in all cases (there are a bunch) it uses a cartesian product of vertex sets.
vzn
CC BY-SA 3.0
2012-10-17T21:35:17.007Z
@vzn: I think that in just about any (hyper)graph product of note, the vertex set will be the cartesian product of the vertex sets of the factors; that was my motivation for considering the dual hypergraph originally. As to unique "prime" factorization, I think you must look for products which *lack* that property, as the Cartesian bitwise meet/join certainly lack it. (Consider $A_1 = \{110,001\}$ and $B_1 = \{011,101\}$ versus $A_2 = \{111,000\}$ and $B_2 = \{011,101\}$; both yield a join of $$C = \begin{bmatrix} 111 & 111 \\ 011 & 101 \end{bmatrix}$$ expressed as an outer product.)
Niel de Beaudrap
CC BY-SA 3.0
2012-10-17T22:47:46.250Z
as written on your now-deleted answer, am actually interested in the question/case of $C$ that are provably "prime" wrt factorization. conjecture that "important" $C$ exist that are "prime" wrt "cartesian bitwise join" factoring
vzn
CC BY-SA 3.0
2012-10-18T00:34:17.363Z
My post didn't provide any sort of uniqueness guarantees. To "factor" the matrix $C$ in my previous comment, one would take as factors the bit-wise AND across the rows and columns, obtaining $A = \{111,001\}$ and $B = \{011, 101\}$, which you might notice is yet a third factorization. (I expect that it is an accident of the example that I've chosen that the row-vector factor is the same in each one.) And this is just with a single mapping of elements to coefficients; for larger $C$ there may be feasible factorizations for different mappings. It's not clear that you can prevent this in any way.
Niel de Beaudrap
CC BY-SA 3.0
2012-10-18T15:49:20.913Z
@vzn: I don't think it's a "product" in its own right; my aim was to relate it as closely to some product (e.g. the tensor product) as I could. In order to be a product, it should do things such as commute over disjoint, disconnected unions of hypergraphs; but because the product is only defined for pairs of hypergraphs with the same number of edges, it is not clear how such a property could hold. Not to mention, come to think of it, that one cannot take the join of  an arbitrary pair of hypergraphs.
Niel de Beaudrap
CC BY-SA 3.0
2012-10-18T15:57:04.410Z
am looking into converting problem to some std hypergraph product in the gringmann ref but cant figure it out right now. the dual idea seems very important but alone is not enough. it does lead to a problem with the right dimensions (in vertices) as you note, but maybe not edge dim ever (because of all the products given, they seem to have $|e| \geq |e_A| + |e_B|$....) maybe it is basically a new hypergraph product? or something else? it takes two hypergraphs $H_A, H_B$ with $r,s$ vertices and $|e_A|=|e_B|=n$ edges each, gives a new hypergraph with $r \cdot s$ vertices but still $n$ edges?
vzn
CC BY-SA 3.0
2012-10-18T17:56:34.037Z
new wild idea. could it have something to do with a bipartite or n-partite hypergraph? ...
vzn
CC BY-SA 3.0
2012-10-20T17:12:00.817Z
A small comment.  Although for some reason Wikipedia has ended up with an article called "Tensor product of graphs", the actual term in common usage is "direct product" or "categorical product".
András Salamon
CC BY-SA 3.0
2012-10-20T18:04:03.990Z
@AndrásSalamon: that seems to vary by the sub-community. Chris Godsil for instance, and many researchers dealing with such topics in the penumbra of the quantum information or quantum chemistry community, refer to it as a tensor product of graphs.
Niel de Beaudrap
CC BY-SA 3.0
2012-10-20T21:59:06.230Z
@Niel de Beaudrap: that may be so, but the standard references on graph products (the books by Imrich/Klavžar) use direct product.  Tensor product seems to be some kind of historical usage that has been adopted again by accident.
András Salamon
CC BY-SA 3.0
2012-10-20T22:05:55.950Z
@Andras: it is certainly good to note synonyms which are likely to be common, in any case; I'll edit to remark on it.
Niel de Beaudrap
CC BY-SA 3.0
2012-10-17T18:16:08.530Z
2012-10-20T23:42:04.250Z
2012-10-20T23:42:04.250Z
Niel de Beaudrap
<p>This problem is very similar to dominating set in bipartite graphs. Indeed, whenever $a_i \lor b_j = 0$, we know that $a_i = b_j = 0$. Remove all these inputs and constraints. Now we are left with sets $A',B'$ and edges containing vertices in $A'$ to vertices in $B'$. Any solution to this system of equations corresponds to a dominating set in this bipartite graph.</p>

<p>Finding a solution of minimal Hamming weight is the same as solving minimum dominating set, which is known to be NP-hard even for planar bipartite graphs of maximum degree 3, as shown by Jukka Suomela <a href="https://cstheory.stackexchange.com/a/2508/40">in this very site</a>.</p>

CC BY-SA 3.0
2012-10-15T22:59:24.310Z
thx but dont follow & think it might not fit; your comment above is not correct, didnt mean $|\cdot|$ as length of the bitvector but as size of the bitvector set (number of bitvectors in the set). $C$ is given but not $A,B$. if you think this is right can you sketch out how this applies for a given $C$? am not saying my problem statement is free of ambiguity, there might be a clearer way to state it....
vzn
CC BY-SA 3.0
2012-10-15T22:44:31.837Z
2012-10-15T22:44:31.837Z
2017-04-13T12:32:28.053Z
Yuval Filmus
<p>(This question has been substantially revised in an attempt to word it clearly.)</p>

<p>I am wondering if anyone has seen this problem. Let $[n] = \{1,\ldots,n\}$ for an integer $n$. Consider two finite multisets of bitstrings, $$ A=\{a_i\}_{i\in[r]} \quad\text{and} \quad B=\{b_j\}_{j\in[s]} \;,$$ where each $a_i \in \{0, 1\}^n$ and each $b_j \in \{0, 1\}^n$. We may compute from this a "Cartesian bitwise join" $C$, which is also a multiset of bitstrings $C= \{c_{i,j}\}_{(i,j) \in [r] \times [s]}$ for size $|C| = |A| \cdot |B| = rs$, where
$$ c_{i,j} = a_i \vee b_j$$ where "$\vee$" is bitwise-OR.</p>

<p><strong>Question.</strong> If you are given such a multi-set $C$, without any particular indexing, can you find multi-sets $A$ and $B$ of which $C$ is the Cartesian bit-wise join? Equivalently: given a sequence $C = (c_k)_{k\in[m]}$ consisting of bitstrings in $\{0,1\}^n$, can you find sequences $A = (a_i)_{i\in[r]}$ and $B = (b_j)_{j\in[s]}$ such that $m = rs$, and a bijection $\varphi: [r] \times [s] \to [m]$, such that $$c_{\varphi(i,j)} = a_i \vee b_j$$ for all $(i,j) \in [r] \times [s]$?</p>

<hr>

<p>This problem is equivalent to the following problem. Consider the ring $R$ whose elements are strings in $\{0,1\}^n$, where addition is done bit-wise by the operation $x + y = x \oplus y \oplus 1$ (where $\oplus$ is parity) with $1^n$ being the identity, and multiplication is the bit-wise OR with $0^n$ being the identity. For some particular ordering of the elements of $A$, we may present $A$ as an element of $R^r$, and similarly present $B$ as an element of $R^s$. 
The Cartesian bitwise join corresponds to the outer product of $A$ and $B$,
$$ C \;=\; A B^\top \;=\; \begin{bmatrix} a_1 \vee b_1 &amp; a_1 \vee b_2 &amp;\cdots&amp; a_1 \vee b_s \\
a_2 \vee b_1 &amp; a_2 \vee b_2 &amp; \cdots &amp; a_2 \vee b_s \\
\vdots &amp; \vdots &amp; &amp; \vdots \\
a_r \vee b_1 &amp; a_r \vee b_2 &amp; \cdots &amp; a_r \vee b_s 
\end{bmatrix}\;,$$
except interpreted as a multiset rather than a matrix (that is, the elements of $C$ are not assigned to particular coefficients of an $r \times s$ matrix). Given a multiset $C$ with composite cardinality $m \in \mathbb N$, can its elements be mapped to coefficients of an $r \times s$ array (such that $m = rs$) which is an outer product of the above form?</p>

<p>(By interchanging 0s and 1s in all of the bitstrings, we may replace the bit-wise OR "$\vee$" with the bit-wise AND "$\wedge$", in which case we may take $R$ to be the ring whose elements are strings in $\{0,1\}^n$, where addition is as vectors over $\mathbb Z_2$, and multiplication is the bit-wise AND. )</p>

<hr>

<p>One may consider additional constraints on this problem, such as minimum Hamming weight of the bitstrings in $A$ and $B$ (in the Cartesian join formulation). We certainly require that $A,B \ne \{0^n\}$ to prevent a trivial solution.</p>

<ul>
<li>This problem arises in an EE &amp; complexity theory context. I am looking for other cases or analysis of it.</li>
<li>The problem is somewhat analogous to factoring but does not seem to have a unique factorization.</li>
<li>Note that bitvectors can be naturally modelled as hypergraphs so maybe something from that theory is applicable. I did research hypergraph products but that theory does not seem to apply directly. The problem translates to finding two hypergraphs $H'$ and $H''$ given a hypergraph $H$, such that the $H$ can be formed by taking all pairwise unions of edges in $H'$ and $H''$.</li>
</ul>

CC BY-SA 3.0
2012-12-10T17:05:29.273Z
@niel as promised [more details](http://vzn1.wordpress.com/2012/12/08/outline-for-a-np-vsppoly-proof-based-on-monotone-circuits-hypergraphs-and-factoring/) re the connection to monotone circuits. basically it is intrinsic to determining _exact error_ due to approximations in lower bounds monotone circuit approximation proofs although this is not yet widely recognized. feel free to rip it into tiny little pieces =)
vzn
CC BY-SA 3.0
2012-12-10T17:09:41.383Z
@András this operation is "hidden" also in eg the Rossman paper on monotone circuit lower bounds which youve [helpfully cited](http://cstheory.stackexchange.com/a/1506/7884) in various places eg tcs.se & your blog (have been focusing some on that paper while developing this)
vzn
CC BY-SA 3.0
2012-12-12T20:01:00.060Z
@sasho fyi actually note 1st rev was simplification (of the real problem) that assumed that the grid is rectangular and $|A|,|B|$ could be found by factoring the size of the multiset $|C|$. in real problem as suresh pointed out, the multisets and repeated "joins" mean that $|A|,|B|$ will only be "near" factors of $|C|$. last rev above by NdB still doesnt quite reflect that. original motivation is as a key operator in [monotone circuit decomposition](http://vzn1.wordpress.com/2012/12/08/outline-for-a-np-vsppoly-proof-based-on-monotone-circuits-hypergraphs-and-factoring/). wonder what you think
vzn
CC BY-SA 3.0
2012-10-15T22:31:58.547Z
Why is $|C| = |A| \cdot |B|$ ? I can see $\le$, but not $=$. In other words, are the sizes of the desired $A, B$ also given ?
Suresh Venkat
CC BY-SA 3.0
2012-10-15T22:41:45.587Z
that reminds me. in some cases the combinations $a_i \vee b_j$ can give the same bitvectors in $C$. am looking for any nontrivial analysis on the problem, pref from the literature, misc assumptions are ok, just looking for some general picture to start.... one immed observation is that the sets could/can be of size $x \cdot y$ where $x, y$ are factors of $|C|$
vzn
CC BY-SA 3.0
2012-10-15T22:45:39.917Z
@Suresh $|C| = |A| \cdot |B|$ by definition. The (formal) sets $A$,$B$ are known in advance. Here $|\cdot|$ is not Hamming weight, just length.
Yuval Filmus
CC BY-SA 3.0
2012-10-15T22:50:09.540Z
am considering both "directions" of this problem but mainly the 
"reverse" direction where $C$ is given but $A,B$ are not given & are to be determined. yes sorry for any ambiguity, $|A|$ above is just the number of bitvectors in the set.
vzn
CC BY-SA 3.0
2012-10-16T02:54:33.153Z
This is a very odd definition. So $C$ is a two-dimensional matrix which is serialized as a one-dimensional vector, and we don't know its dimensions, only the size of the vector. Is that correct? Where does this definition arise?
Yuval Filmus
CC BY-SA 3.0
2012-10-16T02:54:37.550Z
isn't the question equivalent to, for collections of sets $\mathcal{S} = \{S_1, \ldots, S_n\}$ and $\mathcal{T} = \{T_1, \ldots, T_m\}$, find $\mathcal{S}$ and $\mathcal{T}$ given $\mathcal{S} \cap \mathcal{T} = \{S_i \cap T_j\}$? almost always the solution is not unique, and also there is always a trivial solution where $\mathcal{T} = \{U\}$ where $U$ is the universe of possible elements. what are you looking for?
Sasho Nikolov
CC BY-SA 3.0
2012-10-16T02:56:16.567Z
if the analogy is with factoring, are you looking for any non-trivial solution to the above problem?
Sasho Nikolov
CC BY-SA 3.0
2012-10-16T03:24:47.990Z
$C$ is given! its full dimensions and contents are _known/given_. yes it can be seen as a 2d matrix with arbitrary row or column reordering allowed. the "horizontal dimension" (length) of all the bitvectors is given as the same as that of $C$.
vzn
CC BY-SA 3.0
2012-10-16T03:34:46.883Z
it may seem odd but its actually quite "central" in some key complexity theory proofs. yes exactly, collections of sets or equivalently, hypergraphs. each $a_i$ and $b_j$ is a bitvector. will accept any meaningful ref incl reduction to known problems etc... maybe more precisely/formally, $C = \{c: c= a_i \vee b_j, i < |A|, j < |B|\}$... if there is enough interest (say maybe 5 upvotes or more/meaningful answers) will post an example generated by ruby code & some random sets. dont want to reveal "punchline" early on to try to generate independent ideas. will reveal eventually.
vzn
CC BY-SA 3.0
2012-10-16T03:49:11.493Z
what about the fact that there is always a trivial solution or that the solution is not unique?
Sasho Nikolov
CC BY-SA 3.0
2012-10-16T14:57:48.137Z
would like some way to characterize the "nontrivial" solutions or formulate the problem such that trivial solutions are excluded.... nontrivial is not yet precisely defined... inexact solutions might be interesting but the exact case is the important case... have an interesting conjecture on the nontrivial factoring but it wont make sense until "trivial" is defined well... hint, it is not too hard to (P-time) reduce it all to a big SAT problem but that doesnt seem to directly help to reveal the inner structure....
vzn
CC BY-SA 3.0
2012-10-16T15:02:14.783Z
Vote to close, I still cannot understand the question. Please use more standard terminology, and phrase the question clearly.
Yuval Filmus
CC BY-SA 3.0
2012-10-16T15:23:17.097Z
@yuval there is more than one way to phrase it. sorry the notation is not clear & that it wasnt perfect on 1st shot. it is a well defined problem but maybe not written well however think that people are also not reading it carefully. open to suggestions on formulation. have clarified it in the comments.
vzn
CC BY-SA 3.0
2012-10-16T15:49:16.770Z
clarification, here is more on ["bitwise or" of two bitvectors](http://en.wikipedia.org/wiki/Bitwise_operation#OR)
vzn
CC BY-SA 3.0
2012-10-16T16:45:25.903Z
i ventured to clarify, hope i kept the original intention. i would not normally do such a thorough re-edit, but vzn is not usually one to respond to requests for edits.
Sasho Nikolov
CC BY-SA 3.0
2012-10-16T20:06:00.553Z
was on the verge of editing but had no specific suggestions so far. agreed your edit indeed improves clarity & preserves the intent. except the idea of defining a/the "trivial case". maybe closer but does not seem to work right. $1^n$ bitwise or'd with any vector is $1^n$. did you mean $0^n$? that works right?
vzn
CC BY-SA 3.0
2012-10-17T18:32:43.750Z
... Repeating a (now deleted because of meta-discussion) comment — what are these deep proofs in complexity theory where you find that this operation occurs? Assuming my understanding of your problem is correct, it doesn't surprise me that it may play a role in some proofs, as outer products are a natural operation; but it would be nice to know your motivations for this problem, unless it is essentially an exercise in pure algebraic logic.
Niel de Beaudrap
CC BY-SA 3.0
2012-10-17T20:56:37.147Z
note to audience— lots of prior meta comments deleted by mutual agreement although its against my style/pref to do that. unf, apparently got ~3 downvotes on question after the diagram was added & on subsequent edits, dont know the reason. may add my own analysis to the problem as answer at some pt if there are more upvotes but for now, seems like audience is not too enthusiastic for the topic right now & dont want to push against voting. but still think problem is very important & would like to continue discussion in chat or elsewhere if someone initiates it. planning on revisiting at some pt.
vzn
CC BY-SA 3.0
2012-10-18T01:04:23.977Z
@niel (1) dont really care about the distinction between multisets or sets for this problem & think it simplifies it to just have sets (2) not following why you defined addition in the ring & it doesnt seem to be used elsewhere...? (3) like the $A B^T$ idea a lot & makes me think/wonder there could be some connection to matrix SVD...?
vzn
CC BY-SA 3.0
2012-10-18T01:13:09.697Z
(1) Multisets are necessary if you want $|C| = |A|\cdot|B|$. If not, then as per Suresh's initial comment, you can get $|C| \leqslant |A|\cdot|B|$ (if all the elements of $A$ and $B$ are distinct but give rise to repeated elements in $C$, which we only count once each) or even $|C| \geqslant |A|\cdot|B|$ (in case $A$ and $B$ *do* have repeated elements, which we use in different combinations to create multiple possibly distinct elements of $C$). If you want any particular relation between the sizes of the collections at all, definiteness is essential.
Niel de Beaudrap
CC BY-SA 3.0
2012-10-18T01:17:13.983Z
(2) I defined it as a ring only in order for the linear algebra to be well-defined, and in particular to avoid complaints about whether or not my presentation of $A$ and $B$ are "vectors". You are correct that for an outer product it's irrelevant. (3) You should be warned that singular value decompositions are a property of real-valued matrices. If you want to play with those, you do have to care about the addition operation; not to mention the fact that the coefficients are bitstrings and not real numbers. If you substitute bitstrings with diagonal matrices, maybe you get somewhere.
Niel de Beaudrap
CC BY-SA 3.0
2012-10-18T01:19:41.877Z
... Whether you deal with multisets, or whether or not the formulation in terms of outer products is likely to be informative (SVD or no), will tend to depend on what this operation is used for analytically. Are you prepared yet to describe what role you have seen it play, or think that it must play, in complexity theory? Otherwise, this may be better suited for [Math.SE](http://math.stackexchange.com/questions) than here, as this is basically just playing around with structures without yet any idea even of whether the problem is easier or harder than factorization.
Niel de Beaudrap
CC BY-SA 3.0
2012-10-19T22:17:33.663Z
@niel its in monotone circuit proofs.. planning on writing up more details in a blog..
vzn
CC BY-SA 3.0
2012-10-20T17:27:05.417Z
The current formulation admits the trivial solution $r=m, s=1$.  Even this does not always lead to a unique factorisation: the singleton factor can be any bit vector that is dominated by each of the vectors in the other factor.  Should the question not require nontrivial factors?
András Salamon
CC BY-SA 3.0
2012-10-20T22:18:49.390Z
yes it is simple to "factor out" any $1$ bit from $C$ (ie every element of $C$ has its $n$'th bit as $1$, isnt that the case you are referring to? so yes maybe the problem should point out there are no $1$ bits common to $n$'th bits of all elements of $C$.
vzn
CC BY-SA 3.0
2012-10-21T23:40:53.233Z
@vzn: Your condition seems sensible, and would stop multiple trivial factorisations.  However, there is still the trivial solution $A=C$ and $B$ containing a single bit vector which is all zeroes.
András Salamon
<cc.complexity-theory><reference-request><graph-theory><graph-algorithms><boolean-functions>
Factoring Cartesian bitwise join of bit vectors
vzn
# Factoring Cartesian bitwise join of bit vectors

(Asked by: username_0 on 2012-10-15)

(This question has been substantially revised in an attempt to word it clearly.)

I am wondering if anyone has seen this problem. Let $[n] = \{1,\ldots,n\}$ for an integer $n$. Consider two finite multisets of bitstrings, $$ A=\{a\_i\}\_{i\in[r]} \quad\text{and} \quad B=\{b\_j\}\_{j\in[s]} \;,$$ where each $a\_i \in \{0, 1\}^n$ and each $b\_j \in \{0, 1\}^n$. We may compute from this a "Cartesian bitwise join" $C$, which is also a multiset of bitstrings $C= \{c\_{i,j}\}\_{(i,j) \in [r] \times [s]}$ for size $|C| = |A| \cdot |B| = rs$, where
$$ c\_{i,j} = a\_i \vee b\_j$$ where "$\vee$" is bitwise-OR.

**Question.** If you are given such a multi-set $C$, without any particular indexing, can you find multi-sets $A$ and $B$ of which $C$ is the Cartesian bit-wise join? Equivalently: given a sequence $C = (c\_k)\_{k\in[m]}$ consisting of bitstrings in $\{0,1\}^n$, can you find sequences $A = (a\_i)\_{i\in[r]}$ and $B = (b\_j)\_{j\in[s]}$ such that $m = rs$, and a bijection $\varphi: [r] \times [s] \to [m]$, such that $$c\_{\varphi(i,j)} = a\_i \vee b\_j$$ for all $(i,j) \in [r] \times [s]$?

---

This problem is equivalent to the following problem. Consider the ring $R$ whose elements are strings in $\{0,1\}^n$, where addition is done bit-wise by the operation $x + y = x \oplus y \oplus 1$ (where $\oplus$ is parity) with $1^n$ being the identity, and multiplication is the bit-wise OR with $0^n$ being the identity. For some particular ordering of the elements of $A$, we may present $A$ as an element of $R^r$, and similarly present $B$ as an element of $R^s$.
The Cartesian bitwise join corresponds to the outer product of $A$ and $B$,
$$ C \;=\; A B^\top \;=\; \begin{bmatrix} a\_1 \vee b\_1 & a\_1 \vee b\_2 &\cdots& a\_1 \vee b\_s \\
a\_2 \vee b\_1 & a\_2 \vee b\_2 & \cdots & a\_2 \vee b\_s \\
\vdots & \vdots & & \vdots \\
a\_r \vee b\_1 & a\_r \vee b\_2 & \cdots & a\_r \vee b\_s
\end{bmatrix}\;,$$
except interpreted as a multiset rather than a matrix (that is, the elements of $C$ are not assigned to particular coefficients of an $r \times s$ matrix). Given a multiset $C$ with composite cardinality $m \in \mathbb N$, can its elements be mapped to coefficients of an $r \times s$ array (such that $m = rs$) which is an outer product of the above form?

(By interchanging 0s and 1s in all of the bitstrings, we may replace the bit-wise OR "$\vee$" with the bit-wise AND "$\wedge$", in which case we may take $R$ to be the ring whose elements are strings in $\{0,1\}^n$, where addition is as vectors over $\mathbb Z\_2$, and multiplication is the bit-wise AND. )

---

One may consider additional constraints on this problem, such as minimum Hamming weight of the bitstrings in $A$ and $B$ (in the Cartesian join formulation). We certainly require that $A,B \ne \{0^n\}$ to prevent a trivial solution.

* This problem arises in an EE & complexity theory context. I am looking for other cases or analysis of it.
* The problem is somewhat analogous to factoring but does not seem to have a unique factorization.
* Note that bitvectors can be naturally modelled as hypergraphs so maybe something from that theory is applicable. I did research hypergraph products but that theory does not seem to apply directly. The problem translates to finding two hypergraphs $H'$ and $H''$ given a hypergraph $H$, such that the $H$ can be formed by taking all pairwise unions of edges in $H'$ and $H''$.

**Tags:** cc.complexity-theory, reference-request, graph-theory, graph-algorithms, boolean-functions

> **Comments:**
> **username_1**: Why is $|C| = |A| \cdot |B|$ ? I can see $\le$, but not $=$. In other words, are the sizes of the desired $A, B$ also given ?  
> **username_0**: that reminds me. in some cases the combinations $a_i \vee b_j$ can give the same bitvectors in $C$. am looking for any nontrivial analysis on the problem, pref from the literature, misc assumptions are ok, just looking for some general picture to start.... one immed observation is that the sets could/can be of size $x \cdot y$ where $x, y$ are factors of $|C|$  
> **username_2**: @Suresh $|C| = |A| \cdot |B|$ by definition. The (formal) sets $A$,$B$ are known in advance. Here $|\cdot|$ is not Hamming weight, just length.  
> **username_0**: am considering both "directions" of this problem but mainly the  "reverse" direction where $C$ is given but $A,B$ are not given & are to be determined. yes sorry for any ambiguity, $|A|$ above is just the number of bitvectors in the set.  
> **username_2**: This is a very odd definition. So $C$ is a two-dimensional matrix which is serialized as a one-dimensional vector, and we don't know its dimensions, only the size of the vector. Is that correct? Where does this definition arise?  
> **username_3**: isn't the question equivalent to, for collections of sets $\mathcal{S} = \{S_1, \ldots, S_n\}$ and $\mathcal{T} = \{T_1, \ldots, T_m\}$, find $\mathcal{S}$ and $\mathcal{T}$ given $\mathcal{S} \cap \mathcal{T} = \{S_i \cap T_j\}$? almost always the solution is not unique, and also there is always a trivial solution where $\mathcal{T} = \{U\}$ where $U$ is the universe of possible elements. what are you looking for?  
> **username_3**: if the analogy is with factoring, are you looking for any non-trivial solution to the above problem?  
> **username_0**: $C$ is given! its full dimensions and contents are _known/given_. yes it can be seen as a 2d matrix with arbitrary row or column reordering allowed. the "horizontal dimension" (length) of all the bitvectors is given as the same as that of $C$.  
> **username_0**: it may seem odd but its actually quite "central" in some key complexity theory proofs. yes exactly, collections of sets or equivalently, hypergraphs. each $a_i$ and $b_j$ is a bitvector. will accept any meaningful ref incl reduction to known problems etc... maybe more precisely/formally, $C = \{c: c= a_i \vee b_j, i < |A|, j < |B|\}$... if there is enough interest (say maybe 5 upvotes or more/meaningful answers) will post an example generated by ruby code & some random sets. dont want to reveal "punchline" early on to try to generate independent ideas. will reveal eventually.  
> **username_3**: what about the fact that there is always a trivial solution or that the solution is not unique?  
> **username_0**: would like some way to characterize the "nontrivial" solutions or formulate the problem such that trivial solutions are excluded.... nontrivial is not yet precisely defined... inexact solutions might be interesting but the exact case is the important case... have an interesting conjecture on the nontrivial factoring but it wont make sense until "trivial" is defined well... hint, it is not too hard to (P-time) reduce it all to a big SAT problem but that doesnt seem to directly help to reveal the inner structure....  
> **username_2**: Vote to close, I still cannot understand the question. Please use more standard terminology, and phrase the question clearly.  
> **username_0**: @yuval there is more than one way to phrase it. sorry the notation is not clear & that it wasnt perfect on 1st shot. it is a well defined problem but maybe not written well however think that people are also not reading it carefully. open to suggestions on formulation. have clarified it in the comments.  
> **username_0**: clarification, here is more on ["bitwise or" of two bitvectors](http://en.wikipedia.org/wiki/Bitwise_operation#OR)  
> **username_3**: i ventured to clarify, hope i kept the original intention. i would not normally do such a thorough re-edit, but username_0 is not usually one to respond to requests for edits.  
> **username_0**: was on the verge of editing but had no specific suggestions so far. agreed your edit indeed improves clarity & preserves the intent. except the idea of defining a/the "trivial case". maybe closer but does not seem to work right. $1^n$ bitwise or'd with any vector is $1^n$. did you mean $0^n$? that works right?  
> **username_4**: ... Repeating a (now deleted because of meta-discussion) comment — what are these deep proofs in complexity theory where you find that this operation occurs? Assuming my understanding of your problem is correct, it doesn't surprise me that it may play a role in some proofs, as outer products are a natural operation; but it would be nice to know your motivations for this problem, unless it is essentially an exercise in pure algebraic logic.  
> **username_0**: note to audience— lots of prior meta comments deleted by mutual agreement although its against my style/pref to do that. unf, apparently got ~3 downvotes on question after the diagram was added & on subsequent edits, dont know the reason. may add my own analysis to the problem as answer at some pt if there are more upvotes but for now, seems like audience is not too enthusiastic for the topic right now & dont want to push against voting. but still think problem is very important & would like to continue discussion in chat or elsewhere if someone initiates it. planning on revisiting at some pt.  
> **username_0**: @niel (1) dont really care about the distinction between multisets or sets for this problem & think it simplifies it to just have sets (2) not following why you defined addition in the ring & it doesnt seem to be used elsewhere...? (3) like the $A B^T$ idea a lot & makes me think/wonder there could be some connection to matrix SVD...?  
> **username_4**: (1) Multisets are necessary if you want $|C| = |A|\cdot|B|$. If not, then as per Suresh's initial comment, you can get $|C| \leqslant |A|\cdot|B|$ (if all the elements of $A$ and $B$ are distinct but give rise to repeated elements in $C$, which we only count once each) or even $|C| \geqslant |A|\cdot|B|$ (in case $A$ and $B$ *do* have repeated elements, which we use in different combinations to create multiple possibly distinct elements of $C$). If you want any particular relation between the sizes of the collections at all, definiteness is essential.  
> **username_4**: (2) I defined it as a ring only in order for the linear algebra to be well-defined, and in particular to avoid complaints about whether or not my presentation of $A$ and $B$ are "vectors". You are correct that for an outer product it's irrelevant. (3) You should be warned that singular value decompositions are a property of real-valued matrices. If you want to play with those, you do have to care about the addition operation; not to mention the fact that the coefficients are bitstrings and not real numbers. If you substitute bitstrings with diagonal matrices, maybe you get somewhere.  
> **username_4**: ... Whether you deal with multisets, or whether or not the formulation in terms of outer products is likely to be informative (SVD or no), will tend to depend on what this operation is used for analytically. Are you prepared yet to describe what role you have seen it play, or think that it must play, in complexity theory? Otherwise, this may be better suited for [Math.SE](http://math.stackexchange.com/questions) than here, as this is basically just playing around with structures without yet any idea even of whether the problem is easier or harder than factorization.  
> **username_0**: @niel its in monotone circuit proofs.. planning on writing up more details in a blog..  
> **username_5**: The current formulation admits the trivial solution $r=m, s=1$.  Even this does not always lead to a unique factorisation: the singleton factor can be any bit vector that is dominated by each of the vectors in the other factor.  Should the question not require nontrivial factors?  
> **username_0**: yes it is simple to "factor out" any $1$ bit from $C$ (ie every element of $C$ has its $n$'th bit as $1$, isnt that the case you are referring to? so yes maybe the problem should point out there are no $1$ bits common to $n$'th bits of all elements of $C$.  
> **username_5**: @username_0: Your condition seems sensible, and would stop multiple trivial factorisations.  However, there is still the trivial solution $A=C$ and $B$ containing a single bit vector which is all zeroes.  
> **username_0**: @niel as promised [more details](http://username_01.wordpress.com/2012/12/08/outline-for-a-np-vsppoly-proof-based-on-monotone-circuits-hypergraphs-and-factoring/) re the connection to monotone circuits. basically it is intrinsic to determining _exact error_ due to approximations in lower bounds monotone circuit approximation proofs although this is not yet widely recognized. feel free to rip it into tiny little pieces =)  
> **username_0**: @András this operation is "hidden" also in eg the Rossman paper on monotone circuit lower bounds which youve [helpfully cited](http://cstheory.stackexchange.com/a/1506/7884) in various places eg tcs.se & your blog (have been focusing some on that paper while developing this)  
> **username_0**: @sasho fyi actually note 1st rev was simplification (of the real problem) that assumed that the grid is rectangular and $|A|,|B|$ could be found by factoring the size of the multiset $|C|$. in real problem as suresh pointed out, the multisets and repeated "joins" mean that $|A|,|B|$ will only be "near" factors of $|C|$. last rev above by NdB still doesnt quite reflect that. original motivation is as a key operator in [monotone circuit decomposition](http://username_01.wordpress.com/2012/12/08/outline-for-a-np-vsppoly-proof-based-on-monotone-circuits-hypergraphs-and-factoring/). wonder what you think  

---

## 2 answers

### Answer by username_4 on 2012-10-17. Score: 5 | Accepted answer

**Passing to the dual hypergraphs to look for products.**

As you mention in the comments, we may interpret the bitstrings contained in $A$, $B$, and $C$ as edges in hypergraphs.

* Vertices are the elements of $[n]$;
* An edge $x \in \{0,1\}^n$ contains a vertex $v \in [n]$ if $x\_v = 1$.

(Because these are multi-sets, they're actually multi-hyper-graphs. We may consider the edges to have some generic labels to distinguish them.) We may consider the dual hypergraph $H$ in which the vertices and the edges are interchanged; that is, where

* The (labelled) bitstrings $x \in \{0,1\}^n$ now distinct vertices, and
* A bitstring $x \in \{0,1\}^n$ belongs to an edge represented (that is, labelled) by $e \in [n]$ if and only if $x\_e =1$;

— that is, a bitstring $x \in \{0,1\}^n$ describes all of the edges which are incident to it; of which there are always $n$ in this graphical model, albeit some of them may be the "empty edge".
This puts us in a much better position to describe the hypergraph as a product in some conventional manner. The hypergraph $H\_C$ obtained from a multiset $C$ now has a composite number of vertices $m$: we would like hypergraphs $H\_A$ and $H\_B$ such that $V(H\_C)$ has some particular bijective correspondance with $V(H\_A) \times V(H\_B)$.

**A diagonally restricted tensor product of hypergraphs.**

Consider the alternative formulation of the problem, replacing bit-wise OR with bit-wise AND, alluded to in the recent revision of the problem. (To do this, we take the bitwise complement of all of the bitstrings.) The Cartesian bit-wise ***meet*** condition (rather than "join", as we're using "$\wedge$" now in place of "$\vee$") corresponds to the existence of a particular bijection $$\varphi: V(H\_A) \times V(H\_B) \to V(H\_C)$$ such that the edge labelled $e \in [n]$ in $H\_C$ contains only the vertices $\varphi(a,b) \in V(H\_C)$ such that both $a \in V(H\_A)$ and $b \in V(H\_B)$ are contained in the respective edges labelled by $e$ in $H\_A$ and $H\_B$. This seems somewhat different from most graph products, in that we do not take combinations of arbitrary edges, but only those with consistent labels.

* If we suspended this label consistency condition, the join construction would correspond to a hypergraph tensor product (generalizing the [tensor product of graphs](http://en.wikipedia.org/wiki/Tensor_product_of_graphs), also commonly known as the direct product in the literature), in which we define edge-pairs $(e,f) \in E(H\_A) \times E(H\_B)$ which contain all vertices $(a,b) \in V(H\_A) \times V(H\_B)$ such that $a \in e$ and $b \in f$. This glosses over some issues to do with edges which contain $(a,b)$ and $(a,b')$ for a fixed co-ordinate $a$; but the construction we consider is appropriate to hypergraphs, taking the tensor product of the incidence matrices (characteristic functions of the edges, ranging over the vertices) to form the incidence matrix of $H\_A \otimes H\_B$.
* To re-obtain the Cartesian bit-wise join of $H\_A$ and $H\_B$, we must
  restrict to the diagonal edges $(e,e) \in E(H\_A) \times E(H\_B) =
  [n] \times [n]$, which we re-label by $(e,e) \mapsto e$. Note that $H\_A$ and $H\_B$ are edge-labelled hypergraphs, as their edges are non-negotiably labelled by the elements of $[n]$ from the formulation of the vertices as bitstrings with a fixed order. (Of course, when we are *searching* for hypergraphs $H\_A$ and $H\_B$, re-labelling the edges simply corresponds to considering a different hypergraph.) Selecting the diagonal is a plausible restriction, if somewhat unnatural in the context of graph products.

**The resulting reformualtion.**

From this, asking "does $C$ arise from the Cartesian bitwise join of $A$ and $B$?" is equivalent to asking:

> Is an edge-labelled hypergraph $H\_C$ with $m$ vertices and at msot $n$ edges, with distinct edge-labels selected from $[n]$ isomorphic to the diagonal subgraph (*i.e.* taking only the diagonally labelled edges) of the tensor product $H\_A \otimes H\_B$ of two labelled hypergraphs $H\_A$ and $H\_B$, which also have at most $n$ edges each and also have edges labels over $[n]$?

I'm not sure if you're going to come closer to a natural graph product formulation of than this. I rather suspect that if this does play a deep role in computational complexity that someone has studied something like this; but without knowing what areas of complexity theory it is pertinent to, I would not be able to tell you where to look, beyond perhaps investigating tensor products of hypergraphs.

> **Comments:**
> **username_0**: +1 for considering the dual hypergraph which was just musing minutes ago might work & looks promising, am suspecting might make the hypergraph product theory (some good refs on that) relevant. found suresh's ref to the dual hypergraph based on reading your Q/A list & your question on hypergraph coloring. hope to have more comments after further review....  
> **username_0**: still have to dig into this but this is a ref turned up on hypergraph products earlier (before posting question) which has a somewhat new yet somewhat fleshed out theory incl a prime factorization thm! what do you think, does any of this fit? [hypergraph products by gringmann](http://www.bioinf.uni-leipzig.de/conference-registration/09herbst/talks/402_Gringmann.pdf) .. note in all cases (there are a bunch) it uses a cartesian product of vertex sets.  
> **username_4**: @username_0: I think that in just about any (hyper)graph product of note, the vertex set will be the cartesian product of the vertex sets of the factors; that was my motivation for considering the dual hypergraph originally. As to unique "prime" factorization, I think you must look for products which *lack* that property, as the Cartesian bitwise meet/join certainly lack it. (Consider $A_1 = \{110,001\}$ and $B_1 = \{011,101\}$ versus $A_2 = \{111,000\}$ and $B_2 = \{011,101\}$; both yield a join of $$C = \begin{bmatrix} 111 & 111 \\ 011 & 101 \end{bmatrix}$$ expressed as an outer product.)  
> **username_0**: as written on your now-deleted answer, am actually interested in the question/case of $C$ that are provably "prime" wrt factorization. conjecture that "important" $C$ exist that are "prime" wrt "cartesian bitwise join" factoring  
> **username_4**: My post didn't provide any sort of uniqueness guarantees. To "factor" the matrix $C$ in my previous comment, one would take as factors the bit-wise AND across the rows and columns, obtaining $A = \{111,001\}$ and $B = \{011, 101\}$, which you might notice is yet a third factorization. (I expect that it is an accident of the example that I've chosen that the row-vector factor is the same in each one.) And this is just with a single mapping of elements to coefficients; for larger $C$ there may be feasible factorizations for different mappings. It's not clear that you can prevent this in any way.  
> **username_4**: @username_0: I don't think it's a "product" in its own right; my aim was to relate it as closely to some product (e.g. the tensor product) as I could. In order to be a product, it should do things such as commute over disjoint, disconnected unions of hypergraphs; but because the product is only defined for pairs of hypergraphs with the same number of edges, it is not clear how such a property could hold. Not to mention, come to think of it, that one cannot take the join of  an arbitrary pair of hypergraphs.  
> **username_0**: am looking into converting problem to some std hypergraph product in the gringmann ref but cant figure it out right now. the dual idea seems very important but alone is not enough. it does lead to a problem with the right dimensions (in vertices) as you note, but maybe not edge dim ever (because of all the products given, they seem to have $|e| \geq |e_A| + |e_B|$....) maybe it is basically a new hypergraph product? or something else? it takes two hypergraphs $H_A, H_B$ with $r,s$ vertices and $|e_A|=|e_B|=n$ edges each, gives a new hypergraph with $r \cdot s$ vertices but still $n$ edges?  
> **username_0**: new wild idea. could it have something to do with a bipartite or n-partite hypergraph? ...  
> **username_5**: A small comment.  Although for some reason Wikipedia has ended up with an article called "Tensor product of graphs", the actual term in common usage is "direct product" or "categorical product".  
> **username_4**: @AndrásSalamon: that seems to vary by the sub-community. Chris Godsil for instance, and many researchers dealing with such topics in the penumbra of the quantum information or quantum chemistry community, refer to it as a tensor product of graphs.  
> **username_5**: @username_4: that may be so, but the standard references on graph products (the books by Imrich/Klavžar) use direct product.  Tensor product seems to be some kind of historical usage that has been adopted again by accident.  
> **username_4**: @Andras: it is certainly good to note synonyms which are likely to be common, in any case; I'll edit to remark on it.  

---

### Answer by username_2 on 2012-10-15. Score: 4

This problem is very similar to dominating set in bipartite graphs. Indeed, whenever $a\_i \lor b\_j = 0$, we know that $a\_i = b\_j = 0$. Remove all these inputs and constraints. Now we are left with sets $A',B'$ and edges containing vertices in $A'$ to vertices in $B'$. Any solution to this system of equations corresponds to a dominating set in this bipartite graph.

Finding a solution of minimal Hamming weight is the same as solving minimum dominating set, which is known to be NP-hard even for planar bipartite graphs of maximum degree 3, as shown by Jukka Suomela [in this very site](https://cstheory.stackexchange.com/a/2508/40).

> **Comments:**
> **username_0**: thx but dont follow & think it might not fit; your comment above is not correct, didnt mean $|\cdot|$ as length of the bitvector but as size of the bitvector set (number of bitvectors in the set). $C$ is given but not $A,B$. if you think this is right can you sketch out how this applies for a given $C$? am not saying my problem statement is free of ambiguity, there might be a clearer way to state it....  

---

