Skip to main content

Questions tagged [boolean-matrix]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
26 votes
0 answers

Rank mod 6 vs rank over the reals

Let $A$ be a boolean matrix (eg with $0,1$ entries). Assume that $A$ has rank $\le r$ both over $\mathbb{F}_2$ and over $\mathbb{F}_3$. Does this imply that $A$ has low rank over the reals? This seems ...
Shachar Lovett's user avatar
23 votes
2 answers

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

The recent and incredibly slick proof of the sensitivity conjecture relies on the explicit* construction of a matrix $A_n\in\{-1,0,1\}^{2^n\times 2^n}$, defined recursively as follows: $$A_1 = \begin{...
Clement C.'s user avatar
  • 4,481
18 votes
0 answers

In an $m$ by $n$ Boolean matrix, can you find a square block whose four corners are ones in $O(m \cdot n)$ time?

Decision Problem Input: An $m$ by $n$ Boolean matrix $M$. Decision Question: Does there exist a square block within $M$ such that upper-left corner entry == upper-right corner entry == lower-left ...
Michael Wehar's user avatar
13 votes
2 answers

Fast sparse boolean matrix product with possible preprocessing

What are the most practically efficient algorithms for multiplying two very sparse boolean matrices (say, N=200 and there are just some 100-200 non-zero elements)? Actually, I have the advantage that ...
jkff's user avatar
  • 8,971
10 votes
1 answer

Can such a matrix exist?

During my work i came up with the following problem: I am trying to find an $n \times n$ $(0,1)$-matrix $M$, for any $n > 3$, with the following properties: The determinant of $M$ is even. For ...
Etsch's user avatar
  • 615
10 votes
1 answer

What is the largest gap between rank and approximate rank?

We know that the log of the rank of a 0-1 matrix is the lower bound of deterministic communication complexity, and the log of the approximate rank is the lower bound of randomized communication ...
pyao's user avatar
  • 425
9 votes
3 answers

Non-Orthogonal Vectors Problem

Consider the following problems: Orthogonal Vectors Problem Input: A set $S$ of $n$ Boolean vectors each of length $d$. Question: Do there exist distinct vectors $v_1$ and $v_2 \in S$ ...
Michael Wehar's user avatar
8 votes
0 answers

Upper Bound on Number of $n \times n$ Boolean matrices of Boolean rank at most $k$

An $n \times n$ Boolean matrix $B$ has Boolean rank $k$ if there exist matrices $L \in \{0,1\}^{n \times k}$ and $R \in \{0,1\}^{k \times n}$, s.t. $B = L \circ R$. Here $\circ$ denotes the Boolean ...
tranisstor's user avatar
7 votes
2 answers

Binary matrix column subset selection complexity

Given an $m \times n$ matrix ($m$ rows) containing only $0$'s and $1$'s, what is the complexity of finding an $m \times k$ submatrix (of $k$ columns) such that within the chosen submatrix there is no ...
antti.huima's user avatar
7 votes
1 answer

Complexity of Maximizing Hamming Distances Below a Threshold

Problem Statement Is the following problem NP-Complete? Input: A collection $S$ of binary strings, with each string of length $m$. Goal: Compute a binary string $s^*$ of length $m$ that mazimizes the ...
B A's user avatar
  • 98
5 votes
0 answers

Hardness result or reference for optimal Gaussian elimination process

I'm wondering if the following problem is NP-Complete or has any hardness result. References on related problem are also welcome. Input: integers $n\geq1,k\geq0$ and an invertible matrix $M\in\mathbb ...
Shlw Kevin's user avatar
4 votes
1 answer

Most Matrices are Rigid

The rigidity of a matrix $M\in \mathbb{F}^{n\times n}$ is the minimum number of entries that need to be changed in $M$ to reduce its rank to $r$. Formally, it is defined as: $$R_{M}^{\mathbb{F}}(r) = \...
atul ganju's user avatar
4 votes
0 answers

Dynamic matrix-matrix multiplication

Suppose A and B are initial Boolean matrices. Let C = A*B. Suppose one can perform the sequence of the next operations: "set A[i,j] = 1", "set B[i,j] = 1". The result of each ...
gsv's user avatar
  • 421
4 votes
0 answers

About Boolean functions with a high sign-rank

Recently in this beautiful paper, it has been shown that there is an explicit $Th \circ Th$ function with sign-rank scaling exponentially in dimension. I wanted to ...
gradstudent's user avatar
  • 1,453
4 votes
0 answers

Deciding transitivity of a directed acyclic graph [duplicate]

Is there any algorithm that decides whether a given directed acyclic graph is transitive or not, in time-complexity asymptotically better than boolean matrix multiplication?
ekayaaslan's user avatar
3 votes
3 answers

Canonisation of boolean matrices under row and column permutations

Consider the equivalence relation $\sim$ on boolean matrices $A,B\in\{0,1\}^{m\times n}$ which is defined as follows: $A\sim B$ :iff there are permutation matrices $P\in\{0,1\}^{n\times n}, Q\in\{0,1\...
0123456789's user avatar
3 votes
0 answers

Maximum weight triangles in dense graphs

There are multiple results (Vassilevska and Williams STOC09, for instance) on computing efficiently minimal-weight triangles (or more generally patterns) in node-weighted graphs. Several of these ...
Joseph Stack's user avatar
  • 1,095
2 votes
0 answers

Minimize The Number of Connected Components in Hit-map of A Boolean Matrix

Suppose there is a matrix with the value of 0 and 1. The hit-map of the matrix (0 is blue and 1 is red) create some connected component (see the following figure as an instance): Is there any ...
OmG's user avatar
  • 189
1 vote
1 answer

Minimum number of columns making each row different

I'm curious whether this problem is NP-hard: suppose you are given an arbitrary $m\times n$ 0-1 matrix (each element is either 0 or 1, for the simplicity of the problem), and any pair of rows (i.e. a ...
defg's user avatar
  • 41
1 vote
1 answer

reference request- property of subset of rows in a matrix

I am interested in the following quantity. Suppose we are given a matrix $M\in \mathbb{F}_2^{m\times n}$ and a string $z\in \{0,1\}^n$. I am interested in finding the largest subset $S$ of rows in M ...
researcher's user avatar
1 vote
0 answers

algorithms for a large submatrix / general factor / quasi-biclique problem?

Given a sparse 0/1 matrix $X$, too large to fit in memory, with $m$ rows and $n$ columns, I'm looking for an algorithm for finding a submatrix (when one exists) with maximum number of rows such that ...
DavidDLewis's user avatar
0 votes
0 answers

Is there a name/terminology for binary codes with evenly spaced number of ones?

I am generating a random binary matrix $A \in \{0, 1\}^{m \times n}$ with the number of ones in each row set to evenly spaced numbers from an interval. For example, if $n=50$, the number of ones for $...
randomprime's user avatar
0 votes
1 answer

Reduction from SAT to binary matrix subset problem

I'm trying to understand the answer by @Denis on this question, where he showed a way to reduce from SAT to the binary matrix column subset selection problem. The reason I'm having to post a new ...
CowNorris's user avatar
  • 115
-1 votes
1 answer

Sparsity of a Boolean function and its Fourier depth [closed]

For a function $f : \{-1,1\}^n \rightarrow \mathbb{R}$ one can ask for its $l_0$ norm in the indicator basis i.e the number of vertices on which the function is non-zero. Does this sparsity parameter ...
gradstudent's user avatar
  • 1,453