Questions tagged [boolean-matrix]
The boolean-matrix tag has no usage guidance.
21
questions
18
votes
0answers
379 views
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 ...
3
votes
0answers
136 views
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 ...
23
votes
2answers
665 views
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{...
5
votes
0answers
55 views
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 ...
2
votes
0answers
39 views
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 ...
8
votes
3answers
544 views
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$ ...
1
vote
1answer
94 views
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 ...
0
votes
1answer
85 views
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 ...
4
votes
0answers
80 views
About Boolean functions with a high sign-rank
Recently in this beautiful paper, https://arxiv.org/pdf/1705.02397.pdf it has been shown that there is an explicit $Th \circ Th$ function with sign-rank scaling exponentially in dimension. I wanted to ...
26
votes
0answers
538 views
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 ...
-1
votes
1answer
156 views
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 ...
1
vote
1answer
95 views
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 ...
1
vote
0answers
104 views
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 ...
3
votes
0answers
90 views
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 ...
3
votes
3answers
198 views
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\...
8
votes
0answers
342 views
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 ...
4
votes
0answers
126 views
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?
7
votes
2answers
472 views
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 ...
10
votes
1answer
565 views
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 ...
10
votes
1answer
356 views
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 ...
12
votes
2answers
2k views
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 ...
