# Questions tagged [boolean-matrix]

The tag has no usage guidance.

22 questions
Filter by
Sorted by
Tagged with
91 views

40 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 ...
743 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
97 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 ...
117 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 ...
84 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 ...
608 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 ...
234 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
98 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
107 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 ...
91 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 ...
213 views