# Tag Info

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