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 ...
- 36.7k
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\}^...
- 800
9
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 ...
- 176
7
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 ...
- 962
7
votes
Accepted
Most Matrices are Rigid
For simplicity, let us first consider the case $\mathbb{F}=\mathbb{F}_2$. Every non-rigid matrix can be specified by a rank-$r$ matrix $L$ and a matrix $S$ of total sparsity $s$. Since every low-rank ...
- 2,247
6
votes
Accepted
Complexity of Maximizing Hamming Distances Below a Threshold
Lemma 1. The problem is NP-hard, by reduction from Max-2-SAT.
Proof sketch. The reduction is in two steps. Consider the variant of the problem in which $d$ is even and the coverage requirement is ...
- 9,595
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, ...
- 36.7k
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 ...
- 5,772
1
vote
Accepted
Non-Orthogonal Vectors Problem
Equivalences:
The non-orthogonal vectors problem (as defined above) for a set $S$ of $n$ Boolean
vectors each of length $d$ and a positive integer $k$ is equivalent
the following:
...
- 5,065
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 ...
- 560
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$, ...
- 10.2k
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 ...
- 11.6k
Only top scored, non community-wiki answers of a minimum length are eligible