# 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 corner entry == lower-right corner entry == 1? That is, all four corners of the square block are 1's.

Cubic Time Solution

We know that this problem can be solved in $$O(m \cdot n \cdot min\{m,n\})$$ time. The approach involves scanning through the matrix row by row. For each row, for each pair of 1's in that row, we check whether those 1's form an edge of a square block whose four corners are 1's.

Our Question

What is the time complexity of this problem? Is there a quadratic time solution? In particular, can we solve this decision problem in $$O(m \cdot n)$$ time?

Extra Background

1. If you're just looking for a rectangular block whose four corners are ones, this can be solved in $$O(m \cdot n)$$ time. Many variations to this problem can be solved in $$O(m \cdot n)$$ time as well. I co-authored a paper on this subject.

2. The paper "Finding squares and rectangles in sets of points" investigates a related problem from computational geometry where you're given a set of points in a 2D plane and you want to know if there are four points that form an axis-parallel square.

Written together with Eevvoor.

• You can assume wlog that $m \leq n$ (otherwise transpose) and that $n \leq 2m$ since otherwise you can cover the matrix by $2n/m$ matrices of size $m \times 2m$ that cover all square blocks. So wlog the input matrix is square $n$ by $n$. Sep 19, 2020 at 3:41
• @daniello Yes! That's a good point. When the input matrix is rectangular, we can reduce it to the case where the input matrix is square. Thank you. :) Sep 19, 2020 at 8:08
• Seems a little similar to finding a triangle in a graph. If you get a subcubic reduction from that problem that'd be the end of the story for now. Sep 19, 2020 at 15:32
• @JoshuaGrochow Yes, when searching for a rectangular block, the problem is related to finding a four cycle in a graph which is solvable in quadratic time. However, when searching for a square block, I don't know what can be done. Maybe there is a way to reduce triangle finding to this problem. Sep 19, 2020 at 16:29
• This is more dead end than answer, but: there exist sets of $mn^{1-o(1)}$ nonzeros with no square, formed by filling diagonals according to a near-linear-size progression-free set (en.wikipedia.org/wiki/Salem%E2%80%93Spencer_set). So an algorithm that answers yes if dense enough to force a square and switches to the naive O(nonzeros times min(m,n)) otherwise can't be strongly subcubic. Sep 22, 2020 at 16:38