9

An observation too long for a comment (and which also fits well with Jason Gaitonde's observation-too-long-for-comment): As hinted at in the OQ, both of these can in fact be realized by a very simple kind of recursive construction. Namely, we specify $B_0 \in \{(0), (\pm 1)\}$ (a $1 \times 1$ matrix), and then a single recursive formula $$ B_n = \left(\...


9

Here's just a couple of observations I couldn't fit in a comment: 0) Added because the first answer was deleted: there is an interpretation of $H_n$, namely, indexing the rows and columns by $\{0,1\}^n$, the entry corresponding to $(x,y)$ is $1$ if the Hadamard product $x\odot y=(x_1y_1,\ldots,x_n y_n)$ has even parity, and $-1$ if it has odd parity. 1) In ...


8

Rephrasing as a set system, each row represents a subset $E_i$ of some set $X$, for $i=1,2,\dots,m$. You want a set $Y \subseteq X$ with at most $k$ elements, such that $E_i \cap Y \ne \emptyset$ for each $i$. In other words, you want a hitting set of size at most $k$; this problem is NP-complete.


8

When $k$ is given as part of the input, the second problem is equivalent to the monochromatic Max-IP problem (given $S \subseteq \{0,1\}^d$, find $\max_{(a,b) \in S, a\ne b} a \cdot b$). Recently I and Ryan Williams have an (unpublic yet) work showing that when $d = O(\log n)$, OVP and a bichromatic version of Max-IP (given $A,B$, find $\max_{(a,b) \in A \...


6

If $k=O(\log n)$ I believe the techniques of Alman, Chan, and Williams give the best known solution to the Non-Orthogonal Vectors Problem. (They phrase it differently, as a Hamming closest pair problem, but this is equivalent up to poly($d$) factors.) With no bound on $k$, a bichromatic version of the Non-Orthogonal Vectors Problem is at least as hard as ...


5

This problem is precisely the canonization problem for isomorphism of bipartite undirected graphs. While the lexicographically maximum form may be harder, any canonical form will be GI-hard (and so, in particular, it doesn't matter whether the $P$ and $Q$ are restricted to satisfy $P=Q^{-1}$ or not, as asked in a comment above). In particular, there is a ...


3

Your problem is known to be NP-hard. See for instance Vincent Froese, René van Bevern, Rolf Niedermeier, Manuel Sorge: "Exploiting hidden structure in selecting dimensions that distinguish vectors." Journal of Computer and System Sciences 82, pp 521-535 (2016).


2

It is NP-hard, here is a reduction from SAT: You have variables $x_1,\dots,x_m$, and clauses $C_1,\dots,C_n$ on these variables. You build the following $(m+n)\times 2m$ matrix: For $i\in[1,m]$, the $i^{th}$ row contains only $0$ except two $1$'s in column $i$ (representing variable $x_i$) and column $m+i$ (representing $\neg x_i$). Then, the following $...


1

The Fourier transform is a linear operation. In particular, for $f:\{-1,1\}\to\mathbb{R}$ and $S\subseteq[n]$, the Fourier coefficient $\hat f(S)$ is a linear functional of $f$. If $\hat f(S)\neq 0$, its magnitude can be made arbitrarily large or small by multiplying $f$ by an appropriate scalar -- without affecting $||f||_0$. So the answer to your question ...


1

Your problem can be solved in polynomial time, by reduction to bipartite matching. In other words, there is a polynomial-time algorithm to find the largest subset $S$ of rows with your desired property. Construct an undirected bipartite graph with $m$ left-vertices (one per row) and $n$ right-vertices (one per columN). Add an edge $(i,j)$ whenever $M_{i,j}...


1

This kind of problem has been studied, e.g. in the exploitation of symmetries in model-checking and in satisfaction constraint problems. The short answer is that it is $NP$-hard. I suggest this draft by Junttila as a starting point: A note on the computational complexity of a string orbit problem. It addresses the complexity question (in the subcase of ...


Only top voted, non community-wiki answers of a minimum length are eligible