Skip to main content
Share Your Experience: Take the 2024 Developer Survey
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 ...
Joshua Grochow's 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\}^...
Jason Gaitonde's user avatar
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 ...
Lijie Chen's user avatar
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 ...
Rasmus Pagh's user avatar
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 ...
Alex Golovnev's user avatar
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 ...
Neal Young's user avatar
  • 10.8k
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, ...
Joshua Grochow's 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 ...
Gamow's user avatar
  • 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: ...
Michael Wehar's user avatar
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 ...
Boson's user avatar
  • 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$, ...
Aryeh's user avatar
  • 10.6k
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 ...
D.W.'s user avatar
  • 12.1k

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