9 votes

Question about two matrices: Hadamard v. "the magical one" in the proof of the sensitivity conjecture

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 ...
user avatar
9 votes

Question about two matrices: Hadamard v. "the magical one" in the proof of the sensitivity conjecture

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\}^...
user avatar
8 votes

Non-Orthogonal Vectors Problem

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 ...
user avatar
6 votes

Non-Orthogonal Vectors Problem

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 ...
user avatar
5 votes
Accepted

Canonisation of boolean matrices under row and column permutations

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, ...
user avatar
3 votes

Minimum number of columns making each row different

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 ...
user avatar
  • 5,722
1 vote

Canonisation of boolean matrices under row and column permutations

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 ...
user avatar
  • 550
1 vote

Sparsity of a Boolean function and its Fourier depth

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$, ...
user avatar
  • 10.1k
1 vote

reference request- property of subset of rows in a matrix

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 ...
user avatar
  • 10.5k

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