Spiky Rank and Its Applications to Rigidity and Circuits

Hambardzumyan, Lianna; Myasnikov, Konstantin; Riazanov, Artur; Shirley, Morgan; Shraibman, Adi

doi:10.4230/LIPIcs.ICALP.2026.106

Spiky Rank and Its Applications to Rigidity and Circuits

Lianna Hambardzumyan The University of Copenhagen, Denmark Konstantin Myasnikov EPFL, Lausanne, Switzerland Artur Riazanov

EPFL, Lausanne, Switzerland Morgan Shirley Lund University, Sweden Adi Shraibman The Academic College of Tel Aviv-Yaffo, Israel

Abstract

We introduce spiky rank, a new matrix parameter that enhances blocky rank by combining the combinatorial structure of the latter with linear-algebraic flexibility. A spiky matrix is block-structured with diagonal blocks that are arbitrary rank-one matrices, and the spiky rank of a matrix is the minimum number of such matrices required to express it as a sum. This measure extends blocky rank to real matrices and is more robust for problems with both combinatorial and algebraic character.

Our conceptual contribution is as follows: we propose spiky rank as a well-behaved candidate matrix complexity measure and demonstrate its potential through applications. We show that large spiky rank implies high matrix rigidity, and that spiky rank lower bounds yield lower bounds for depth-2 ReLU circuits, the basic building blocks of neural networks. On the technical side, we establish tight bounds for random matrices and develop a framework for explicit lower bounds, applying it to Hamming distance matrices and spectral expanders. Finally, we relate spiky rank to other matrix parameters, including blocky rank, sparsity, and the $\gamma_{2}$ -norm.

Keywords and phrases:

blocky rank, matrix rigidity, ReLU circuits, spiky rank

Category:

Track A: Algorithms, Complexity and Games

Funding:

Lianna Hambardzumyan: This work is funded by the European Research Council (ERC) under grant agreement no. 101125652 (ALBA). Most of the work was done while the author was a postdoctoral researcher at the University of Victoria, Canada, funded by NSERC and at Hebrew University of Jerusalem, Israel, funded by ISF grants 921/22 and 2635/19.

Konstantin Myasnikov: Supported by Swiss State Secretariat for Education, Research, and Innovation (SERI) under contract number MB22.00026.

Artur Riazanov: Supported by Swiss State Secretariat for Education, Research, and Innovation (SERI) under contract number MB22.00026.

Morgan Shirley: Supported by Knut and Alice Wallenberg grant KAW 2023.0116.

Copyright and License:

© Lianna Hambardzumyan, Konstantin Myasnikov, Artur Riazanov, Morgan Shirley,
and Adi Shraibman; licensed under Creative Commons License CC-BY 4.0

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Circuit complexity

Related Version:

Full Version: https://arxiv.org/abs/2602.23503 [19]

Acknowledgements:

We thank Nathan Harms for helpful feedback that improved the presentation of the paper. We are grateful to Dmitry Sokolov for bringing ultra-lossless expanders to our attention, and to Amir Yehudayoff for pointing us to Warren’s theorem for the proof of Theorem 24. Finally, we thank Nati Linial, Shachar Lovett, Ryan Williams, and Amir Yehudayoff for many insightful discussions on spiky rank.

DOI:

10.4230/LIPIcs.ICALP.2026.106

Event:

53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Editors:

Sayan Bhattacharya, Danupon Nanongkai, Michael Benedikt, and Gabriele Puppis

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Studying the structural parameters of matrices has proven to be a powerful way to capture the complexity of various computational models and to establish lower bounds. A recurring theme in complexity theory is identifying “well-behaved” matrix parameters: parameters strong enough to capture meaningful lower bounds, structured enough to admit combinatorial or algebraic analysis, and flexible enough to connect to multiple computational models. Rank, rigidity, $\gamma_{2}$ -norm, and blocky rank are all examples of such measures.

In this work we introduce and study spiky rank, a new matrix parameter that we argue meets the criteria for a well-behaved complexity measure. Spiky rank is a generalization of the blocky rank defined for communication complexity applications by Hambardzumyan, Hatami and Hatami [18] (Definitions 1 and 2) which later found a broad range of applications in complexity theory and beyond [7, 28, 36, 16, 13, 5].

Spiky rank adds a linear algebraic flavor to the combinatorial nature of blocky rank. This allows us to connect spiky rank to complexity measures that are both algebraic and combinatorial in their nature, such as matrix rigidity and circuits with “algebraic” gates.

Both blocky rank and spiky rank fit into a common paradigm for defining complexity measures: we begin by specifying a class of simple objects that we define to have complexity 1, and then define the complexity of a general object as the minimum number of such simple objects needed to construct it. To define blocky and spiky rank, we define our matrices of complexity 1 as follows:

Definition 1 (Blocky and Spiky Matrices).

A blocky matrix is a matrix that can be obtained from the identity matrix by permuting rows or columns, duplicating rows or columns, and adding all-zero rows or columns. Equivalently, a blocky matrix is a matrix whose rows and columns can be permuted so that it consists of diagonal blocks that are all-one submatrices (of possibly different sizes), with all off-diagonal blocks equal to zero. See Figure 1(a).

A spiky matrix is a blocky matrix in which each diagonal block is an arbitrary rank-one matrix (rather than an all-one matrix). Equivalently, a spiky matrix can be expressed as the entrywise product of a blocky matrix and a rank-one matrix. See Figure 1(c).

(a) A blocky matrix

B

.

(b) A rank-one matrix

u\otimes v

.

(c) A spiky matrix

B\circ(u\otimes v)

.

Figure 1: A spiky matrix is the entrywise product of a blocky matrix and a rank-one matrix.

We then define the complexity of general matrices as follows:

Definition 2 (Blocky and Spiky Rank).

A blocky matrix is said to have blocky rank one. The blocky rank of a matrix $M$ , denoted $\mathsf{br}(M)$ , is the minimum number $r$ such that $M$ can be written as a linear combination of $r$ blocky rank one matrices.

A spiky matrix is said to have spiky rank one. The spiky rank of a matrix $M$ , denoted $\mathsf{spr}(M)$ , is the minimum number $r$ such that $M$ can be written as a sum of $r$ spiky rank one matrices.

1.1 Motivations for Blocky and Spiky Rank

Blocky rank.

The study of blocky matrices and related decompositions has a surprisingly long and diverse history. Although the terminology “blocky matrix” is recent, the same objects have been rediscovered many times under different names across theoretical computer science and mathematics. For instance, fat matchings [22, 29], equivalence graphs [12, 2], adjacency matrices of $P_{4}$ -free graphs [9, 5], and equality matrices [36]. Various versions of blocky decompositions have been studied; blocky rank, blocky covering (union of blocky matrices), blocky partitioning (sum of blocky matrices) and more. Each of these variants has turned out to capture useful phenomena in different research areas:

$\blacksquare$

In communication complexity blocky decompositions have been used to study models of communication with access to the equality oracle [18, 28, 9, 16].
$\blacksquare$

In operator theory, it was observed [18] that blocky matrices are the contractive idempotents of Schur multiplier algebras, making blocky rank a natural way to characterize the structure of idempotents in this setting (see also [13]).
$\blacksquare$

In combinatorics, blocky coverings of different families of graphs have been studied in [12, 2, 9, 7].
$\blacksquare$

In cryptography, Applebaum and Nir [5] studied blocky covering to characterize families of graphs that can be realized with linear secret sharing schemes of constant size.
$\blacksquare$

In circuit complexity, blocky decompositions provide lower bounds: Jukna [22] used blocky partitioning to derive bounds against depth-3 circuits with parity gates, and Avraham and Yehudayoff [7] showed that blocky partitioning lower bounds depth-2 threshold circuits.
$\blacksquare$

Branching program size lower bounds were obtained via blocky covering in [29].

Perhaps the most striking and far-reaching connection is due to Williams [36], who related blocky rank to the renowned Orthogonal Vectors Conjecture (OVC). In particular, Williams showed that to refute OVC – and consequently the Strong Exponential Time Hypothesis (SETH) – it would suffice to prove that the $2^{n}\times 2^{n}$ Disjointness matrix $D_{n}$ satisfies $\mathsf{br}(D_{n})\leq 2^{o(n)}$ . On the other hand, if one could show that $\mathsf{br}(D_{n})\geq 2^{\omega(n)}$ , this would immediately yield exponential lower bounds for depth-2 exact threshold circuits by [7, 36], resolving a notorious open problem in circuit complexity. This duality highlights the importance of studying blocky rank: either upper bounds or lower bounds on $\mathsf{br}(D_{n})$ would have transformative implications in algorithms, fine-grained complexity, and circuit lower bounds.

Spiky rank.

As evident from this wide range of applications, blocky rank is a versatile measure. But it is fundamentally a combinatorial measure and, in particular, not a robust one. Small modifications to the matrix can cause its blocky rank to change drastically.

For example, in Figure 2, the identity matrix has $\mathsf{br}(I_{n})=1$ , but if we place distinct weights on the diagonal, the blocky rank jumps to $\mathsf{br}(D_{n})=n$ . Structurally these matrices are nearly the same – they are both just diagonal matrices – but blocky rank treats them in a completely different way. This lack of robustness makes blocky rank poorly suited for applications involving real-valued matrices or settings where algebraic properties matter. Spiky rank addresses this shortcoming by capturing the intuition that a diagonal matrix is expected to be simple regardless of its entries, in particular, $\mathsf{spr}(D_{n})=1$ .

I_{n}=\begin{bmatrix}1&0&0&\cdots&0\\ 0&1&0&\cdots&0\\ 0&0&1&\cdots&0\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 0&0&0&\cdots&1\end{bmatrix}\qquad D_{n}=\begin{bmatrix}1&0&0&\cdots&0\\ 0&2&0&\cdots&0\\ 0&0&3&\cdots&0\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 0&0&0&\cdots&n\end{bmatrix}

Figure 2: The identity matrix

I_{n}

(left) and the diagonal matrix

D_{n}

(right).

This extra flexibility makes spiky rank well-suited for problems that have both combinatorial and algebraic character. In this work, we demonstrate two such applications:

$\blacksquare$

Spiky rank lower bounds matrix rigidity, a central problem in circuit and communication complexity (Section 1.2.1),
$\blacksquare$

Spiky rank lower bounds the size of depth-2 ReLU circuits, which sit at the intersection of complexity theory and modern machine learning (Section 1.2.2).

Finally, note that spiky rank strictly strengthens blocky rank: every blocky decomposition is also spiky, so $\mathsf{spr}(M)\leq\mathsf{br}(M)$ for all $M$ . Thus, lower bounds for spiky rank have the same implications as for blocky rank. On the other hand, upper bounds can be even more significant. As with blocky rank, upper bounds for spiky rank of the Disjointness matrix have far-reaching consequences: if the $2^{n}\times 2^{n}$ Disjointness matrix $\textup{{Disj}}_{n}$ satisfies $\mathsf{spr}(\textup{{Disj}}_{n})\leq 2^{o(n)}$ , then Orthogonal Vector Conjecture (and thus SETH) would be false [37].

1.2 Results

Our main contribution is conceptual: we introduce spiky rank as a new matrix complexity measure, demonstrate its applicability to problems in complexity theory, and establish its basic properties. On the technical side, we prove lower bounds for both random and explicit matrix families and relate spiky rank to other classical parameters. Our main results are:

1.

We demonstrate the natural applicability of spiky rank to two problems in complexity theory: matrix rigidity (Section 1.2.1) and ReLU circuits (Section 1.2.2).
2.

We show that most Boolean matrices have spiky rank $\Omega(N/\log N)$ (matching blocky rank), while most real matrices have spiky rank $\Omega(N)$ (Section 1.2.3).
3.
We give the following bounds on the spiky rank of specific $N\times N$ matrices of interest:
- $\blacksquare$
  
  $\Omega(\sqrt{\log N})$ for the 1-Hamming Distance matrix (Section 6.2), simultaneously improving the previous $\log\log N$ bound for blocky rank as well [18].
- $\blacksquare$
  
  $\Omega(\log N)$ for adjacency matrices of certain expander graphs (Section 6.3).
- $\blacksquare$
  
  $\Omega(\log N/\log\log N)$ for the Inner Product and Disjointness matrix (Section 6.4) (likely far from optimal but it represents a first step toward stronger bounds).
4.

For Boolean matrices, we establish a dimension-free relation between blocky and spiky rank, implying in particular that constant spiky rank yields constant blocky rank (Section 1.2.5). In the full version, we further bound spiky rank in terms of matrix sparsity, separate it from the $\gamma_{2}$ -norm, and highlight gaps between the approximate and sign variants of blocky and spiky rank.

1.2.1 Application to Matrix Rigidity

Matrix rigidity, introduced by Valiant [32] and Grigoriev [17], asks how far a matrix is from having low rank: the rank- $r$ rigidity $\mathcal{R}_{M}(r)$ is the minimum number of entry modifications required to reduce the rank of $M$ to $r$ .

Highly rigid matrices are central to long-standing open problems in complexity theory. Valiant showed that if $M\in\mathbb{R}^{N\times N}$ satisfies $\mathcal{R}_{M}(\epsilon N)\geq\Omega(N^{1+\delta})$ for some $\epsilon,\delta>0$ , then any log-depth linear circuit computing the linear transformation $x\mapsto Mx$ must have superlinear size. Additionally, Razborov [30] linked rigidity to communication complexity, showing that matrices in $\textsf{PH}^{cc}$ – the communication complexity analogue of the polynomial hierarchy – are upper-bounded in their rigidity. In particular, if a $N\times N$ Boolean matrix $M\notin\textsf{PH}^{cc}$ , then its rigidity over $\mathbb{F}_{2}$ must satisfy

\mathcal{R}^{\mathbb{F}_{2}}_{M}(2^{(\log\log N)^{\omega(1)}})\geq\frac{N^{2}}% {2^{(\log\log N)^{O(1)}}}.

Hence, constructing sufficiently rigid matrices would yield lower bounds for $\textsf{PH}^{cc}$ and ultimately separate it from $\textsf{PSPACE}^{cc}$ – both of which remain major open problems in communication complexity.

Despite extensive study, progress has been limited on finding explicit rigid matrices: the best explicit constructions fall well short of the parameters needed for Valiant’s or Razborov’s applications.

A direct link between rigidity and spiky rank is rather straightforward to show: matrices with large spiky rank are also highly rigid.

Theorem 1.

Let $M$ be a matrix and $0<r\leq\mathsf{spr}(M)$ . Then,

\mathcal{R}_{M}(r)\;\geq\;\frac{(\mathsf{spr}(M)-r)^{2}}{4}.

This has two key consequences. First, for Valiant’s target rank $\epsilon N$ , an explicit matrix with $\mathsf{spr}(M)=\Omega(N)$ would achieve the strongest possible rigidity bound $\Omega(N^{2})$ . Note that, since Boolean matrices have spiky rank at most ${N/\log N}$ , the only candidate matrices with spiky rank $\Omega(N)$ are the real matrices.

Second, for Razborov’s target rank $2^{(\log\log N)^{\omega(1)}}$ , we would need to find an explicit matrix with spiky rank at least (see Corollary 33)

\frac{N}{2^{(\log\log N)^{O(1)}}}.

This shows that spiky rank is not only a structural parameter, but also a potential tool for constructing explicit rigid matrices. With this goal in mind, we highlight the following open challenges to guide future research in this direction.

Major Open Problem 2.

Find an explicit real matrix $M\in\mathbb{R}^{N\times N}$ with $\mathsf{spr}(M)=\Omega(N)$ .

Major Open Problem 3.

Find an explicit Boolean matrix $M\in\{0,1\}^{N\times N}$ with

\mathsf{spr}(M)=\frac{N}{2^{(\log\log N)^{O(1)}}}.

Although most Boolean matrices have spiky rank at least $\Omega(N/\log N)$ and most real matrices have $\Omega(N)$ (see Section 1.2.3), constructing explicit examples that meet these bounds remains elusive. We expect that solving either problem above will be quite challenging. At present, the best lower bounds we can prove for explicit matrices are of order $\Omega(\log N)$ (see Section 1.2.4).

Finally, we remark that Theorem 1 allows known non-rigidity results to translate into upper bounds on spiky rank. For instance, Alman and Williams [1] proved that for sufficiently small $\varepsilon>0$ , the Inner Product matrix $\mathrm{IP}_{n}$ of size $2^{n}\times 2^{n}$ satisfies

\mathcal{R}_{\mathrm{IP}_{n}}(2^{n(1-f(\varepsilon))})\leq 2^{n(1+\varepsilon)},

where $f(\varepsilon)=\Theta(\varepsilon^{2}/\log(1/\varepsilon)).$ By Theorem 1, this yields an upper bound $\mathsf{spr}(\mathrm{IP}_{n})\leq 2^{(1-\delta)n}$ for some constant $\delta>0$ , improving on the trivial bound of ${2^{n}}/{n}$ (see Section 1.2.3).

1.2.2 Application to Circuit Complexity

Connections between blocky rank and circuit complexity were first observed by Jukna [22], and later by Avraham and Yehudayoff [7], who showed that the blocky rank of a matrix lower bounds the size of any $\Sigma\circ\operatorname{LTF}$ circuit computing¹¹1In this paper, a circuit computes a matrix $M$ if it takes as input a row label $r$ and a column label $c$ and outputs the value of the entry $M[r,c]$ . it up to a certain loss factor (implicit in [20]). Here, $\Sigma\circ\operatorname{LTF}$ denotes linear combinations of linear threshold functions (LTFs), where an LTF is a Boolean function of the form $T(x)=\mathbbm{1}[\langle w,x\rangle\geq\alpha]$ for some $w\in\mathbb{R}^{n}$ and $\alpha\in\mathbb{R}$ .

Naturally this connection extends to spiky rank and to $\Sigma\circ\operatorname{ReLU}$ circuits, where ReLU functions generalize threshold functions by outputting $\max\{0,\langle w,x\rangle-\alpha\}$ . The following proposition admits a simple proof, yet it is conceptually important.

Proposition 4.

For $M\colon\{0,1\}^{n}\times\{0,1\}^{n}\to\mathbb{R}$ , let $s$ be the size of a $\Sigma\circ\operatorname{ReLU}$ circuit that computes $M$ . Then

s\geq\frac{\mathsf{spr}(M)}{3(n+1)}.

Observe that $\Sigma\circ\mathrm{LTF}$ circuits which compute Boolean functions can be simulated by $\Sigma\circ\operatorname{ReLU}$ circuits with only constant factor blowup in size. This follows from the fact that $\mathrm{LTF}$ gates for Boolean functions can have $w\in\mathbb{Z}^{n}$ and $\alpha\in\mathbb{Z}$ without loss of generality (see e.g. [26]) and the relation

\mathbbm{1}[\langle w,x\rangle\geq\alpha]=\max\{0,\langle w,x\rangle-\alpha+1% \}-\max\{0,\langle w,x\rangle-\alpha\}

which is true when $w\in\mathbb{Z}^{n}$ and $\alpha\in\mathbb{Z}$ .

Linear threshold and ReLU circuits are central models in both complexity theory and machine learning. $\Sigma\circ\mathrm{LTF}$ circuits capture linear combinations of halfspaces and have been studied since the early days of threshold logic. On the other hand, ReLU gates have become the dominant activation function in modern neural networks, thus $\Sigma\circ\mathrm{ReLU}$ circuits are the basic building blocks of modern neural networks. However, our understanding of their expressive power from a Boolean complexity perspective remains limited. Understanding the power and limitations of these models is therefore both an important task in circuit complexity and in machine learning.

Despite decades of work, the best known lower bounds for these circuits are very weak: even for $\Sigma\circ\operatorname{LTF}$ , essentially no superlinear lower bounds are known for explicit functions [31]. Williams [35] gave the strongest results to date, proving that for every $k$ there exists a function in NP that requires circuit size $n^{k}$ in both the $\Sigma\circ\operatorname{LTF}$ and $\Sigma\circ\operatorname{ReLU}$ models. For explicit functions, the strongest known result is due to Kane and Williams [23], who showed that even the stronger class $\operatorname{LTF}\circ\operatorname{LTF}$ requires size $\Omega(n^{3/2})$ to compute the $n$ -variate Andreev function. Mukherjee and Basu [27] extend this to prove a lower bound of $\Omega(n^{1-\delta})$ for $\operatorname{LTF}\circ\operatorname{ReLU}$ circuits computing the Andreev function.

Our theorem shows that spiky rank serves as a lower bound measure for depth-two neural networks with ReLU activation, just as blocky rank does for $\Sigma\circ\operatorname{LTF}$ circuits. In particular, proving spiky rank lower bounds of $\omega((\log N)^{5/2})$ for explicit $N\times N$ matrices would immediately yield new circuit lower bounds. At present, our lower bounds are of order $\log N$ ; the first milestone toward this goal would be to establish any super-logarithmic spiky rank lower bounds for explicit matrices.

Open Problem 5.

Find an explicit real matrix $M\in\mathbb{R}^{N\times N}$ with $\mathsf{spr}(M)=\omega((\log N)^{5/2})$ .

1.2.3 Bounds for Random Matrices

How large can the spiky rank of a matrix be? Trivially, both the spiky rank and blocky rank of an $N\times N$ Boolean matrix are at most $N$ . For blocky rank, this bound can be improved to $\tfrac{N}{\log N}$ [29, 7], and therefore the same upper bound applies to spiky rank as well. A natural question is whether spiky rank admits a substantially stronger upper bound. Avraham and Yehudayoff [7] showed that most matrices are maximally hard for blocky rank. We prove that the same phenomenon holds for spiky rank.

Theorem 6 (Informal).

A random Boolean matrix of size $N\times N$ has spiky rank of order $\Omega\big(\tfrac{N}{\log N}\big)$ with high probability.

For real matrices, the situation is more extreme: the trivial upper bound of $N$ turns out to be essentially tight.

Theorem 7 (Informal).

A random real matrix of size $N\times N$ has spiky rank at least $\tfrac{N}{2}$ with high probability.

This mirrors what is known for many other natural measures in complexity theory, such as circuit complexity and communication complexity, where random functions or matrices almost always exhibit the largest possible complexity.

1.2.4 Bounds for Specific Matrices

The lower bounds discussed above, while strong, are for random (non-explicit) matrices. For applications in complexity theory, however, it is essential to establish lower bounds for explicit families of matrices.

For blocky rank, the best known lower bounds for explicit families of matrices are of order $\Omega(\log N)$ (Greater-Than [7], Inner-Product, Disjointness [18]).

For spiky rank, we develop a general lower bound framework (Theorem 37) and apply it to two examples: adjacency matrices of the Hamming cube and expander graphs. The common properties of these graphs that we use are:

Thinness:: every small subgraph has smaller edge-to-node ratio compared to the entire graph;
Induced matchings:: there are large induced matchings in all large subgraphs.

This framework can only yield lower bounds up to $\Theta(\log N)$ , the bottleneck is in the use of a variation of a lemma from [6, Lemma 12].

Hamming distance. Consider the matrix $\mathrm{HD}_{1}^{n}$ of size $N\times N$ with $N=2^{n}$ , whose rows and columns are indexed by all $n$ -bit strings, and where

\mathrm{HD}_{1}^{n}(x,y)=\begin{cases}1&\text{if $x$ and $y$ differ in exactly% $1$ coordinate,}\\ 0&\text{otherwise.}\end{cases}

Applying our framework to this matrix yields the following bound:

Theorem 8.

$\mathsf{spr}(\mathrm{HD}_{1}^{n})\geq\Omega(\sqrt{\log N}).$

This bound is not far from the optimal; upper bound on the spiky rank is $\mathsf{spr}(\mathrm{HD}_{1}^{n})\leq\mathsf{br}(\mathrm{HD}_{1}^{n})\leq\log N$ , where the last upper bound follows from the following blocky matrix decomposition: Let $M_{i}$ be the matrix such that $M_{i}(x,y)=1$ iff $x_{i}\neq y_{i}$ and all the other entries of $x$ and $y$ coincide. Then $M_{i}$ is a permutation matrix, so $\mathsf{br}(M_{i})=1$ and $\mathrm{HD}_{1}^{n}=M_{1}+\dots+M_{n}$ .

This lower bound is quite remarkable considering that $\mathrm{HD}_{1}^{n}$ matrix is very simple with respect to many other matrix complexity measures, as we discuss in Section 1.2.5.

Open Problem 9.

Is $\mathsf{spr}(\mathrm{HD}_{1}^{n})\geq\Omega(\log N)$ ?

Expander graphs. As a second application, let $G$ be an $(N,d,\lambda)$ -spectral expander: a $d$ -regular graph with the second largest eigenvalue of the adjacency matrix not exceeding $\lambda$ , denote its adjacency matrix with $M_{G}$ . We prove:

Theorem 10.

$\mathsf{spr}(M_{G})\geq\Omega\!\left(\min\!\left(\tfrac{d}{\lambda},\log\tfrac% {N}{d^{2}}\right)\right).$

This implies (see Corollary 40) an explicit $\Omega(\log N)$ lower bound for the spiky rank of adjacency matrices of $(N,\Theta(\log^{2}N),\Theta(\log N))$ -spectral expanders.

Inner Product. The Boolean inner product matrix is defined by $\mathrm{IP}_{n}(x,y)=\sum_{i\in[n]}x_{i}y_{i}\bmod 2$ for $x,y\in\{0,1\}^{n}$ . For $\mathrm{IP}_{n}$ we obtain bounds that are weak but improve over the trivial ones:

\frac{n}{\log n}\leq\mathsf{spr}(\mathrm{IP}_{n})\leq 2^{(1-\delta)n},

for some constant $\delta>0$ . The lower bound is established in Section 6.4, while the upper bound follows from non-rigidity results (Section 1.2.1).

Disjointness. The Disjointness matrix $\textup{{Disj}}_{n}$ is the $2^{n}\times 2^{n}$ Boolean matrix whose rows and columns are indexed by $\{0,1\}^{n}$ , with $\textup{{Disj}}_{n}(x,y)=1$ iff $x$ and $y$ have no common $1$ ’s. For the Disjointness matrix we observe the same lower bound as for $\mathrm{IP}_{n}$ (Section 6.4), so we have

\frac{n}{\log n}\leq\mathsf{spr}(\textup{{Disj}}_{n})\leq 5^{n/5}

where the upper bound follows from the $\mathsf{br}(\textup{{Disj}}_{n})$ upper bound by Williams [36].

We believe the true lower bounds for $\textup{{Disj}}_{n}$ and $\mathrm{IP}_{n}$ are much closer to the upper bounds, and in particular ask:

Open Problem 11.

Is it true that $\mathsf{spr}(\mathrm{IP}_{n})=\omega(n)$ or $\mathsf{spr}(\textup{{Disj}}_{n})=\omega(n)$ ?

Figure 3: The picture illustrates the upper and lower bounds for spiky rank: above the scale there are known lower bounds and upper bounds. Below the scale are consequences of the corresponding lower bounds. The dashed part of the scale represents the state of the art of explicit lower bounds. Here

N

is always the size of the matrix, so for

\mathrm{HD}_{1}^{n}

,

\textup{{Disj}}_{n}

, and

\mathrm{IP}_{n}

,

N=2^{n}

.

1.2.5 Relations to other matrix parameters

When introducing a new matrix parameter, a natural and useful question to understand is how it compares to existing ones: is it stronger, weaker, or qualitatively different? We defer the proofs of these relations to the full version.

Blocky rank

Since spiky rank can be seen as an algebraic strengthening of blocky rank, the first step is to ask whether this additional flexibility actually increases its power. Is blocky rank equivalent to spiky rank?

Question 12.

Does every Boolean matrix $M$ satisfy $\mathsf{br}(M)\leq\mathrm{poly}(\mathsf{spr}(M))$ ?

We answer this question qualitatively: there is a dimension-free relation between spiky and blocky rank:

Theorem 13.

For any Boolean matrix $M$ , $\mathsf{br}(M)\leq\mathsf{spr}(M)^{O(\mathsf{spr}(M))}.$

This situation is reminiscent of tantalizing log-rank conjecture. There, too, a combinatorial parameter – the partition number – is vastly strengthened by adding algebraic property via matrix rank. Similar to Theorem 13, an exponential upper bound is known, and the challenge is whether this relation can be improved to a quasi-polynomial one.

$\gamma_{2}$ -norm

Since our main goal is to establish lower bounds on spiky rank, it is natural to compare it with matrix parameters that are more amenable to analysis – particularly matrix norms. A well-studied example, with many applications in complexity theory, is the $\gamma_{2}$ -norm (see [8] and references within). For a matrix $M$ , it is defined as

\gamma_{2}(M)=\min_{U,V:M=UV}\|U\|_{\operatorname{row}}\|V\|_{\operatorname{% col}},

where $\|U\|_{\operatorname{row}}$ denotes the maximum $\ell_{2}$ -norm of the rows of $U$ , and $\|V\|_{\operatorname{col}}$ denotes the maximum $\ell_{2}$ -norm of the columns of $V$ .

Strong lower bounds are known for $\gamma_{2}$ -norm for functions of interest; for instance, $\gamma_{2}(\mathrm{IP}_{n})\geq N^{\Omega(1)}$ , where $\mathrm{IP}_{n}(a,b)=\sum_{i\in[n]}a_{i}b_{i}\bmod 2$ (see e.g. [25]). This motivates comparing $\gamma_{2}$ with rank-based parameters such as blocky rank and spiky rank. For blocky rank, it is known that for every Boolean matrix $M$ , $\mathsf{br}(M)\geq\log\gamma_{2}(M)$ [18, Proposition 3.1]. For spiky rank, while an analogous inequality currently seems out of reach, we observe a simple non-explicit separation:

Theorem 14.

There exists a Boolean matrix $M$ such that $\mathsf{spr}(M)\geq\Omega(\gamma_{2}^{2}(M))$ .

The reverse direction – whether blocky rank is upper-bounded by a function of $\gamma_{2}$ -norm – is a conjecture asked in [18], and is equivalent to a conjecture in operator theory. Very recently, Goh and Hatami [13] proved that for $N\times N$ Boolean matrix $M$ , $\mathsf{br}(M)\leq 2^{\gamma_{2}(M)}(\log N)^{2}$ , and the same bound also applies to spiky rank.

Sparsity

One of the most basic and easily computable parameters of a matrix is its sparsity, the number of non-zero entries. We show that sparse matrices necessarily have low spiky rank, a fact that becomes useful when relating spiky rank to matrix rigidity (Lemma 29). In particular, for any real matrix $M$ with sparsity $m$ , we prove

\mathsf{spr}(M)\leq\sqrt{m}.

For Boolean matrices, this bound can be sharpened, and even expressed directly in terms of blocky rank. Specifically, for any Boolean matrix $M$ with sparsity $m$ , it holds

\mathsf{br}(M)\leq O\left(\frac{\sqrt{m}\log\log m}{\log m}\right).

Sign and approximate measures

Some computational models are naturally characterized not by exact matrix parameters but by their approximate or sign variants. For instance, randomized communication complexity is lower-bounded by approximate rank, while unbounded-error communication complexity is captured by sign-rank. Formally, for a matrix measure $\mu\colon\{0,1\}^{N\times N}\to\mathbb{R}$ , we define its approximate version by

\mu_{\epsilon}(M)\coloneqq\inf\{\mu(M^{\prime})\mid\|M-M^{\prime}\|_{\infty}% \leq\epsilon\text{ , }M^{\prime}\in\mathbb{R}^{N\times N}\}.

Similarly, the sign version of $\mu$ is $\mu_{\pm}(M)\coloneqq\inf\{\mu(M^{\prime})\mid\mathrm{sign}(M)=\mathrm{sign}(M% ^{\prime})\}$ .

Approximate measures tend to be stronger than their exact counterparts, and often defy intuition developed for them. For example, the approximate version of the log-rank conjecture is false [10]. In case of spiky rank, it is sharply separated from all related approximate and sign measures of a matrix: $\mathsf{spr}(\mathrm{HD}_{1}^{n})\geq\sqrt{\log N}$ (Theorem 8), while $\mathrm{rk}_{\pm}(\mathrm{HD}_{1}^{n})=O(1)$ [15], $\gamma_{2,\varepsilon}(\mathrm{HD}_{1}^{n})=O(1)$ [11], $\mathsf{br}_{\epsilon}(\mathrm{HD}_{1}^{n})=\mathrm{poly}(\log\log N)$ .

This highlights an interesting contrast between the spiky and blocky rank. For blocky rank, there is a dimension-free relation with its sign version: we show that $\mathsf{br}(M)\leq 2^{\mathsf{br}_{\pm}(M)}$ . By contrast, for spiky rank we have $\mathsf{spr}(\mathrm{HD}_{1}^{n})\geq\Omega(\sqrt{\log N})$ but $\mathsf{spr}_{\pm}(\mathrm{HD}_{1}^{n})\leq\mathrm{rk}_{\pm}(\mathrm{HD}_{1}^{% n})=O(1)$ , ruling out any dimension-free relation between $\mathsf{spr}$ and $\mathsf{spr}_{\pm}$ .

Thus, proving lower bounds for sign spiky rank is an even harder challenge. At the same time, this opens a promising direction to seek explicit versions of the known non-explicit bounds below the logarithmic barrier of our framework. For example, we know that the adjacency matrix of a random degree- $d$ graph has sign spiky rank $\Omega(d)$ . A natural candidate for derandomization is a spectral expander, leading to the following question:

Question 15.

What is $\mathsf{spr}_{\pm}(M_{G})$ for a spectral expander $G$ ?

Organization.

Section 2 introduces preliminaries. In Section 3, we prove the existence of Boolean and real matrices with high spiky rank. The applications to matrix rigidity and circuit complexity are presented in Section 4 and Section 5, respectively. Section 6 establishes spiky rank bounds for specific explicit matrices. Additional material may be found in the full version.

2 Preliminaries

Our convention in this paper is to use capital letters for matrix dimensions, e.g. $A\in\mathbb{R}^{M\times N}$ . We use the notation $\circ$ for the entrywise product. The notation $[k]$ represents the set of integers $\{1,\ldots,k\}$ .

For a field $\mathbb{F}$ , we denote $0_{\mathbb{F}}$ for the additive identity and $1_{\mathbb{F}}$ for the multiplicative identity. Addition, multiplication, and the entrywise product of matrices over $\mathbb{F}$ are denoted $+_{\mathbb{F}}$ , $\cdot_{\mathbb{F}}$ , and $\circ_{\mathbb{F}}$ respectively.

For a matrix $M\in\mathbb{F}^{N\times N}$ its sparsity $\mathsf{spar}(M)$ is defined as the number of its non- $0_{\mathbb{F}}$ elements.

We write $\mathbbm{1}_{S}$ for $S\in[N]\times[N]$ for the matrix in $\{0,1\}^{N\times N}$ , where $\mathbbm{1}_{S}[i,j]=1$ iff $(i,j)\in S$ .

Blocky and spiky measures.

As some of our results generalize to arbitrary fields, we rewrite Definitions 1 and 2 here with respect to an arbitrary field $\mathbb{F}$ .

Definition 16.

A matrix $M\in\mathbb{F}^{M\times N}$ is blocky if there is an integer $k$ and two collections of disjoint sets $S_{1},\dots,S_{k}\subseteq[M]$ and $T_{1},\dots,T_{k}\subseteq[N]$ such that $M[i,j]=1_{\mathbb{F}}$ if $(i,j)\in\bigcup_{\ell\in[k]}S_{i}\times T_{i}$ and $M[i,j]=0_{\mathbb{F}}$ otherwise.

A matrix $M\in\mathbb{F}^{M\times N}$ is spiky if there exists a blocky matrix $B$ and a rank-one matrix $C$ (where rank is taken over $\mathbb{F}$ ) such that $M=B\circ_{\mathbb{F}}C$ .

Definition 17.

The blocky rank of a matrix $M\in\mathbb{F}^{M\times N}$ , denoted $\mathsf{br}^{\mathbb{F}}(M)$ , is the minimum $r$ such that $M=\sum_{i\in[r]}\alpha_{i}B_{i}$ where each $\alpha_{i}\in\mathbb{F}$ and each $B_{i}$ is blocky.

The spiky rank of a matrix $M\in\mathbb{F}^{M\times N}$ , denoted $\mathsf{spr}^{\mathbb{F}}(M)$ , is the minimum $r$ such that $M=\sum_{i\in[r]}S_{i}$ where each $S_{i}$ is spiky.

When the underlying field is $\mathbb{R}$ , we write simply $\mathsf{br}(M)$ and $\mathsf{spr}(M)$ .

Here are some easy facts about spiky rank:

Fact 18 (Subadditivity).

For any field $\mathbb{F}$ and matrices $A,B\in\mathbb{F}^{M\times N}$ , $\mathsf{spr}^{\mathbb{F}}(A+B)\leq\mathsf{spr}^{\mathbb{F}}(A)+\mathsf{spr}^{% \mathbb{F}}(B)$ .

Fact 19 (Upper bounds).

For any field $\mathbb{F}$ and matrix $A\in\mathbb{F}^{M\times N}$ , $\mathsf{spr}^{\mathbb{F}}(A)\leq{\mathrm{rank}}^{\mathbb{F}}(A)$ (where ${\mathrm{rank}}^{\mathbb{F}}$ is the rank over $\mathbb{F}$ ) and $\mathsf{spr}^{\mathbb{F}}(A)\leq\mathsf{br}^{\mathbb{F}}(A)$ .

Sign blocky rank and sign spiky rank.

We study the sign versions blocky rank and spiky rank over the reals. In the following definition, we assume that the matrices have no 0-entries. For a matrix $A$ , the value $\mathrm{sign}(A)$ is the $\mathrm{sign}$ function applied element-wise:

\mathrm{sign}(A)[i,j]=\begin{cases}1&\mbox{if }A[i,j]>0\\ -1&\mbox{if }A[i,j]<0\end{cases}.

Definition 20.

Let $A$ be a matrix in $\mathbb{R}^{M\times N}$ .

$\blacksquare$

The sign blocky rank of $A$ , denoted $\mathsf{br}_{\pm}(A)$ , is defined as

$\mathsf{br}_{\pm}(A)=\min_{B\in\mathbb{R}^{M\times N}}\{\mathsf{br}(B):\mathrm% {sign}(A)=\mathrm{sign}(B)\}.$
$\blacksquare$

The sign spiky rank of $A$ , denoted $\mathsf{spr}_{\pm}(A)$ , is defined as

$\mathsf{spr}_{\pm}(A)=\min_{B\in\mathbb{R}^{M\times N}}\{\mathsf{spr}(B):% \mathrm{sign}(A)=\mathrm{sign}(B)\}.$

Fact 21 (Upper bounds for sign measures.).

For any matrix $A\in\mathbb{R}^{M\times N}$ , $\mathsf{br}_{\pm}(A)\leq\mathsf{br}(A)$ and $\mathsf{spr}_{\pm}(A)\leq\mathsf{spr}(A)$ .

3 Non-explicit lower bounds for spiky rank

3.1 Lower bound for random Boolean matrices

We first count the number of $N\times N$ Boolean matrices that have spiky rank $r$ for a fixed number $r\leq N$ . It is sufficient to count the number of $\pm 1$ -matrices of with spiky rank $r$ . Indeed, if $M\in\{0,1\}^{N\times N}$ , then its signed version $M^{\prime}\in\{\pm 1\}^{N\times N}$ defined as $M^{\prime}=J-2M$ with $J$ being the $N\times N$ all-ones matrix, has $\mathsf{spr}(M^{\prime})\leq r+1$ .

In fact, we will actually count the number of $\pm 1$ -matrices with sign spiky rank $r$ (Definition 20). As this measure is upper-bounded by spiky rank, this gives us an estimate for the number of matrices with spiky rank $r$ as well.

The idea is to use Warren’s theorem [34] to count the number of possible sign patterns. The same idea and argument were used to count the number of matrices with sign rank $r$ in [4]. Before stating the theorem, let us set it up first.

Let $P_{1},P_{2},\ldots,P_{m}$ be real polynomials in $\ell$ variables each. For $x\in\mathbb{R}^{\ell}$ , such that no polynomial among $\{P_{i}\}$ vanishes at $x$ , its sign pattern is the vector

\big(\mathrm{sign}(P_{1}(x)),\mathrm{sign}(P_{2}(x)),\ldots,\mathrm{sign}(P_{m% }(x))\big)\in\{-1,1\}^{m}.

Theorem 22 ([34]).

Let $P_{1},P_{2},\ldots,P_{m}$ be real polynomials, each in $\ell$ variables and of degree at most $k$ . If $m\geq\ell$ , then the number of different sign pattern for $x$ ranging over all $\mathbb{R}^{\ell}$ is at most $\left(4ekm/\ell\right)^{\ell}$ .

Lemma 23.

The number of $N\times N$ sign matrices with sign spiky rank $r\leq N/2$ is at most $N^{6rN}$ .

Proof.

Let $M$ be a $N\times N$ sign matrix with sign spiky rank $r$ . Let $A\coloneqq A_{1}+\dots+A_{r}\in\mathbb{R}^{N\times N}$ be the sign representation of $M$ : $M=\mathrm{sign}(A_{1}+\dots+A_{r})$ . Let us represent each $A_{i}=B_{i}\circ C_{i}$ where $B_{i}$ is a blocky matrix and $C_{i}$ is a rank- $1$ matrix. There are at most $N^{4rN}$ collections $B_{1},\dots,B_{r}$ , so let us fix one and count the number of potential matrices $M$ that appear as we change $C_{1},\dots,C_{r}$ .

With fixed $B_{1},\dots,B_{r}$ each entry of $A$ can be written as a degree-2 polynomial in $2Nr$ . Let for each $i\in[r]$ , $C_{i}=x_{i}^{T}y_{i}$ for some vectors $x_{i},y_{i}\in\mathbb{R}^{N}$ . Then for $j,k\in[N]$ we have $A_{jk}=\sum_{i\in[r]}(B_{i})_{jk}\cdot x_{ij}y_{ik}$ . Then by Theorem 22 we get that the number of different sign matrices $M$ of form $\mathrm{sign}(B_{1}\circ C_{1}+\dots+B_{r}\circ C_{r})$ with fixed $B_{1},\dots,B_{r}$ is at most $\left(4e\cdot\tfrac{2N^{2}}{2rN}\right)^{2rN}\leq N^{2rN}$ , so in total there are at most $N^{4rN}\cdot n^{2rN}$ matrices of sign spiky rank $r$ . $\hfill\blacktriangleleft$

Combining the lemma with the observation that $\mathsf{spr}_{\pm}(M)\leq\mathsf{spr}(M)$ , we get that a uniformly random Boolean matrix has high spiky rank with high probability. More precisely,

Theorem 24.

If $M$ is a $N\times N$ uniformly random Boolean matrix, then

\Pr\Big[\mathsf{spr}(M)\geq\frac{N}{12\log N}\Big]\geq\Pr\Big[\mathsf{spr}_{% \pm}(M)\geq\frac{N}{12\log N}\Big]\geq 1-{2^{-\frac{N^{2}}{2}}}.

Proof.

The number of matrices of sign spiky rank less than $N/(12\log N)$ is at most $N^{6N^{2}/(12\log N)}\leq 2^{N^{2}/2}$ by Lemma 23 and the total number of $N\times N$ sign matrices is $2^{N^{2}}$ . $\hfill\blacktriangleleft$

3.2 Lower bound for real matrices

The spiky rank of any $N\times N$ real matrix is trivially bounded above by $N$ , since the real rank of a matrix is at most $N$ , and every rank-one matrix is also a spiky matrix. For Boolean matrices, even blocky rank can be bounded above by $O({N}/{\log N})$ . However, for general real matrices, we show that the trivial upper bound is essentially tight: there exist matrices whose spiky rank is $\Omega(N)$ . The key point in the proof as in Lemma 23 is that all spiky matrices with a fixed blocky pattern can be seen as evaluations of a polynomial.

We will need the following standard probabilistic notions: a distribution $\mu$ over $\mathbb{R}^{m}$ is absolutely continuous if there exists an integrable density function $f\colon\mathbb{R}^{m}\to\mathbb{R}^{+}$ such that for every Lebesgue-measurable set $A\subseteq\mathbb{R}^{m}$ we have $\mu(A)=\int_{A}fd\lambda$ where $\lambda$ is the Lebesgue measure. Examples of absolutely continuous distributions include the uniform distribution over $[0,1]^{m}$ and the Gaussian distribution.

Theorem 25.

Let $\mu$ be any absolutely continuous probability distribution over $\mathbb{R}_{N\times N}$ . Then

\Pr_{M\sim\mu}[\mathsf{spr}(M)\geq N/2]=1.

In particular this holds for $M\sim[0,1]^{N\times N}$ .

Proof.

It suffices to show that the Lebesgue measure of the set of all matrices with spiky rank at most $N/2-1$ is zero. This immediately implies the existence of a matrix with spiky rank at least $N/2$ .

Let $M\in\mathbb{R}^{N\times N}$ be a matrix with $\mathsf{spr}(M)=r$ . Then $M=\sum_{i\in[r]}S_{i}$ , where each $S_{i}$ is a spiky matrix. Each spiky matrix $S_{i}$ can be viewed as an entrywise product of a blocky matrix $B_{i}$ and a rank-1 matrix $a_{i}^{T}b_{i}$ for some vectors $a_{i},b_{i}\in\mathbb{R}^{n}$ . Fix a collection of blocky matrices $B_{1},\dots,B_{r}\in\{0,1\}^{N\times N}$ , and define the corresponding set of spiky rank- $r$ matrices with the blocky pattern $B_{1},\dots,B_{r}$ :

\mathcal{S}_{B_{1},\dots,B_{r}}=\Big\{\sum_{i\in[r]}(a_{i}^{T}b_{i})\circ B_{i% }\mid a_{1},\dots,a_{r},b_{1},\dots,b_{r}\in\mathbb{R}^{N}\Big\},

where $\circ$ is the Hadamard (entrywise) product. Then, the set of all matrices in $\mathbb{R}^{N\times N}$ of spiky rank at most $r$ is equal to the union over all such choices of $B_{1},\dots,B_{r}$ : $\bigcup_{B_{1},\ldots B_{r}}\mathcal{S}_{B_{1},\dots,B_{r}}.$ Since the number of blocky matrices is finite (trivially it does not exceed $2^{N^{2}}$ ), to show that the union set has measure zero it is sufficient to show that each set $\mathcal{S}_{B_{1},\dots,B_{r}}$ has measure zero whenever $r\leq N/2-1$ .

To show that $\mathcal{S}_{B_{1},\dots,B_{r}}$ has Lebesgue measure zero, define a smooth function $f\colon\mathbb{R}^{2r\cdot n}\to\mathbb{R}^{n\times n}$ as follows: for $a_{1},\ldots a_{r},b_{1},\ldots,b_{r}\in\mathbb{R}^{N}$ and $i,j\in[N]$ , let

f(a_{1},b_{1},\dots,a_{r},b_{r})[i,j]=\sum_{\ell\in[r]}1_{B_{\ell}[i,j]=1}% \cdot a_{\ell}[i]\cdot b_{\ell}[j].

The image of $f$ is exactly $\mathcal{S}_{B_{1},\dots,B_{r}}$ .

Fact 26.

Suppose $f_{1},\dots,f_{n}\colon\mathbb{R}^{m}\to\mathbb{R}$ are polynomials and $A\subseteq\mathbb{R}^{m}$ is a set with Lebesgue measure zero. Then $f(A)\coloneqq\{(f_{1}(x),\dots,f_{n}(x))\mid x\in A\}$ also has Lebesgue measure zero.

Proof.

Since polynomials are $C^{1}$ -differentiable (in fact, infinitely differentiable) we apply the more general standard result (see e.g. [14, Proposition 1.3]) that states that any $C^{1}$ -differentiable transformation maps a measure-zero set to a measure-zero set. $\hfill\blacktriangleleft$

Since $\mathbb{R}^{2r\cdot N}$ has measure zero when $2rN<N^{2}$ and $\mathcal{S}_{B_{1},\dots,B_{r}}=f(\mathbb{R}^{2r\cdot N})$ , by Fact 26 $\mathcal{S}_{B_{1},\dots,B_{r}}$ has measure zero for all $r<N/2$ , and so does their finite union. $\hfill\blacktriangleleft$

4 Connection to matrix rigidity

Definition 27 (Rigidity).

For a matrix $M\in\mathbb{F}^{N\times N}$ over a field $\mathbb{F}$ , the rank- $r$ rigidity $\mathcal{R}^{\mathbb{F}}_{M}(r)$ is the minimum number of entries that must be modified to reduce the rank of $M$ to $r$ . Formally,

\mathcal{R}^{\mathbb{F}}_{M}(r)=\min\{\,s\mid M=A+_{\mathbb{F}}C,\;{\mathrm{% rank}}^{\mathbb{F}}(A)\leq r,\;\mathsf{spar}(C)\leq s\,\}.

We show that matrices with large spiky rank must also be highly rigid. Our main result is the following generalization of Theorem 1 to arbitrary fields.

Theorem 28.

Let $M$ be a matrix over a field $\mathbb{F}$ and $0<r\leq\mathsf{spr}^{\mathbb{F}}(M)$ . Then,

\mathcal{R}^{\mathbb{F}}_{M}(r)\geq\frac{(\mathsf{spr}^{\mathbb{F}}(M)-r)^{2}}% {4}.

The key ingredient is that sparse matrices have small spiky rank.

Lemma 29.

Let $M\in\mathbb{F}^{N\times N}$ be a matrix over an arbitrary field $\mathbb{F}$ with at most $m$ non-zero entries. Then,

\mathsf{spr}^{\mathbb{F}}(M)\leq 2\sqrt{m}.

We defer the proof to the full version. This immediately yields the following relationship between spiky rank and matrix rigidity.

Proof of Theorem 28.

Assume $\mathcal{R}^{\mathbb{F}}_{M}(r)=s$ for some $r\leq N$ . Then $M$ can be written as $M=A+_{\mathbb{F}}C$ , where $A\in\mathbb{F}^{N\times N}$ has ${\mathrm{rank}}^{\mathbb{F}}(A)=r$ and $C\in\mathbb{F}^{N\times N}$ has at most $s$ non-zero entries. By the subadditivity of spiky rank over $\mathbb{F}$ , we have

\mathsf{spr}^{\mathbb{F}}(M)=\mathsf{spr}^{\mathbb{F}}(A+_{\mathbb{F}}C)\leq% \mathsf{spr}^{\mathbb{F}}(A)+\mathsf{spr}^{\mathbb{F}}(C)\leq r+2\sqrt{s},

where the last inequality follows from Lemma 29 and the trivial observation that $\mathsf{spr}^{\mathbb{F}}(M)\leq{\mathrm{rank}}^{\mathbb{F}}(M)$ for all $M$ . Rearranging gives $s\geq(\mathsf{spr}(M)-r)^{2}/4$ , which completes the proof. $\hfill\blacktriangleleft$

$\blacktriangleright$ Remark 30.

The condition $0<r\leq\mathsf{spr}^{\mathbb{F}}(M)$ in Theorem 28 limits its applicability for proving intermediate rigidity bounds. For instance, for Valiant’s target rank $\epsilon N$ , the theorem applies only to matrices already known to have spiky rank $\Omega(N)$ .

$\blacktriangleright$ Remark 31.

Lemma 29, thus also Theorem 28, is tight for real matrices: a random real matrix has spiky rank $\Omega(N)$ by Theorem 25, and thus sparsity $\Omega(N^{2})$ and rigidity $\Omega(N^{2})$ , the maximum possible. For Boolean matrices, we can slightly improve the sparsity and spiky rank tradeoff (see the full version).

To discuss the implications of Theorem 28 for communication complexity, we use the following result of Razborov [30] and Wunderlich [38].

Theorem 32 ([38, Theorem 5.15]).

Let $\mathbb{F}$ be a finite field and let $M$ be a $N\times N$ matrix. If

\mathcal{R}_{M}^{\mathbb{F}}\left(2^{(\log\log N)^{\omega(1)}}\right)\geq% \Omega\left(\frac{N^{2}}{2^{(\log\log N)^{O(1)}}}\right).

Then $M\notin\textsf{PH}^{cc}$ .

As an immediate consequence we obtain:

Corollary 33.

Suppose a ${N\times N}$ Boolean matrix $M$ satisfies

\mathsf{spr}^{\mathbb{F}}(M)\geq\frac{N}{2^{(\log\log N)^{O(1)}}},

where $\mathbb{F}$ is the finite field. Then $M\notin\textsf{PH}^{\text{cc}}$ .

Proof.

Applying Theorem 28 with $r=\mathsf{spr}^{\mathbb{F}}(M)/2$ , we obtain

\mathcal{R}_{M}^{\mathbb{F}}\!\left(\tfrac{N}{2^{(\log\log N)^{O(1)}}}\right)% \;\;\geq\;\;\Omega\!\left(\frac{N^{2}}{2^{(\log\log N)^{O(1)}}}\right).

Since

\mathcal{R}_{M}^{\mathbb{F}}\!\left(2^{(\log\log N)^{\omega(1)}}\right)\;\;% \geq\;\;\mathcal{R}_{M}^{\mathbb{F}}\!\left(\tfrac{N}{2^{(\log\log N)^{O(1)}}}% \right),

the claim follows directly from Theorem 32. $\hfill\blacktriangleleft$

5 Connection to circuit complexity

Definition 34.

A $\operatorname{ReLU}$ gate (rectified linear unit) is a function $\ell\colon\{0,1\}^{n}\to\mathbb{R}^{+}$ such that there exist a vector $w\in\mathbb{R}^{n}$ and a scalar $a\in\mathbb{R}$ such that for all $x\in\{0,1\}^{n}$

\ell(x)=\max\{0,\langle w,x\rangle+a\}.

Intuitively, a ReLU function is a weighted linear threshold function. For our purposes it will be convenient to view a ReLU gate as a matrix: a $\operatorname{ReLU}$ gate is a matrix $L\colon\{0,1\}^{n}\times\{0,1\}^{n}\to\mathbb{R}^{+}$ such that there exist vectors $w_{1},w_{2}\in\mathbb{R}^{n}$ and a scalar $\alpha\in\mathbb{R}$ for which

L(x,y)=\max\{0,\langle w_{1},x\rangle+\langle w_{2},y\rangle+\alpha\}.

We now show that $\Sigma\circ\operatorname{ReLU}$ circuit complexity – the number of $\operatorname{ReLU}$ gates – of any function is upper bounded by its spiky rank up to an $O(n)$ factor. As a first step, we bound the spiky rank of a single ReLU gate.

Claim 35.

Let $L\colon\{0,1\}^{n}\times\{0,1\}^{n}\to\mathbb{R}^{+}$ be a $\operatorname{ReLU}$ gate. Then

\mathsf{spr}(L)\leq 3n+3.

Proof.

Let $w_{1},w_{2}\in\mathbb{R}^{n}$ and $\alpha\in\mathbb{R}$ be such that $L(x,y)=\max\{0,\langle w_{1},x\rangle+\langle w_{2},y\rangle+\alpha\}.$ Denote the underlying function $L^{\prime}(x,y)=\langle w_{1},x\rangle+\langle w_{2},y\rangle+\alpha$ . Observe that $L^{\prime}$ is a sum of three rank- $1$ matrices $\langle w_{1},x\rangle$ , $\langle w_{2},y\rangle$ and $\alpha$ (each depending only on $x$ , $y$ or being constant), so ${\mathrm{rank}}(L^{\prime})\leq 3$ .

Define $T_{L}$ as the threshold function corresponding to $L$ as follows:

T_{L}(x,y)=\begin{cases}1,\text{ if }L^{\prime}(x,y)>0\\ 0,\text{ otherwise.}\end{cases}

Avraham and Yehudayoff [7] show that any threshold function on $\{0,1\}^{n}\times\{0,1\}^{n}$ can be written as a disjoint union of at most $n+1$ blocky matrices:

T_{L}=B_{1}+\ldots+B_{n+1},

where $B_{1},\ldots,B_{n+1}$ are disjoint blocky matrices, i.e., their supports are disjoint rectangles in the matrix. We now define weighted matrices $R_{1},\ldots,R_{n+1}$ corresponding to $B_{i}$ ’s by placing the original values of $L$ on the support of each $B_{i}$ :

R_{i}(x,y)=\begin{cases}L(x,y),\text{ if }B_{i}(x,y)=1\\ 0,\text{ otherwise.}\end{cases}

Now since $B_{i}$ ’s are disjoint, we have $L=R_{1}+\ldots+R_{n+1}.$ The only problem now is that $R_{i}$ might not be a spiky matrix as it might have blocks of rank greater than 1. However, the blocks of $R_{i}$ are submatrices of $L^{\prime}$ , so each block of $R_{i}$ has rank at most $3$ . If there is a block $R_{i}$ of rank greater than $1$ , then we can decompose $R_{i}$ into at most three matrices that have rank- $1$ on that block. If multiple blocks in the same $R_{i}$ have rank greater than 1, then we can still partition $R_{i}$ into at most 3 matrices that have rank-1 on all blocks, because the blocks are on disjoint rows and columns. This shows that each $R_{i}$ can be decomposed into at most three spiky matrices. Hence, $\mathsf{spr}(M)\leq 3(n+1)$ . $\hfill\vartriangleleft$

Proposition 36.

For $M\colon\{0,1\}^{n}\times\{0,1\}^{n}\to\mathbb{R}$ , let $s$ be the size of a $\Sigma\circ\operatorname{ReLU}$ circuit that computes $M$ . Then

\frac{\mathsf{spr}(M)}{3(n+1)}\leq s.

Proof.

For the lower bound, let $M=\sum_{i=1}^{s}L_{i}$ , where $L_{i}$ are ReLU functions. Then,

\mathsf{spr}(M)\leq\sum_{i=1}^{s}\mathsf{spr}(L_{i})\leq s\cdot(3n+3).\

$\hfill\blacktriangleleft$

6 Explicit lower bounds for spiky rank

6.1 Lower bound framework

In this section we give a framework for proving spiky ranks lower bounds that applies to thin matrices such as $\mathrm{HD}_{1}^{n}$ and adjacency matrices of expander graphs.

Theorem 37.

Let $M\in\mathbb{R}^{N\times N}$ , $s, k, D$ be positive integers and $\gamma\in(0,1)$ . If

(P1)

For every $S\subseteq[N]$ and $T\subseteq[N]$ with $|S|\leq s$ and $|T|\leq s$ we have $\mathsf{spar}(M|_{S\times T})\leq k\cdot(|S|+|T|)$ .
(P2)

For every $M^{\prime}\leq M$ (entrywise) such that $\mathsf{spar}(M-M^{\prime})\leq\gamma\cdot\mathsf{spar}(M)$ , there exist sets $S\subseteq[N]$ and $T\subseteq[N]$ such that $|S|=|T|=D$ and $M^{\prime}|_{S\times T}$ is a permutation matrix.

then

\mathsf{spr}(M)\geq\Omega\left(\min\left(\frac{\gamma\cdot\mathsf{spar}(M)}{kN% },\log\left(\frac{Ds}{2N}\right)\right)\right).

We need the following lemma for the proof. The proof of it is identical to the proof of [7, Lemma 12], but we include it here for completeness.

Lemma 38.

Let $I_{N}$ be identity matrix of size $N\times N$ . If there is a blocky (or spiky) matrix $B$ , such that $B\land I_{N}=0$ (i.e. there is no entry where both $I_{N}$ and $B$ are nonzero). Then there exists $V\subset[N]$ , s.t. $|V|\geq N/4$ and $B|_{V\times V}=0$ .

Proof.

Let blocks of $B$ be $A_{1}\times B_{1},A_{2}\times B_{2},\ldots,A_{k}\times B_{k}$ . Define two random subsets of $[N]$ as follows. Let $\xi_{1},\xi_{2},\ldots,\xi_{k}$ be i.i.d. uniformly distributed on $\{0,1\}$ .

Let $S$ be the complement of $\bigcup_{a:\xi_{a}=0}S_{a}$ , and $T$ be the complement of $\bigcup_{a:\xi_{a}=1}T_{a}$ . Let $I=\{i\in[N]\mid(i,i)\in S\times T\}$ . Note that $B|_{S\times T}$ is zero matrix. For each $i\in[N]$ , the probability that $(i,i)\in S\times T$ is $1/4$ , because $B_{ii}=0$ . Thus there is a choice for $S\times T$ so that $|I|\geq N/4$ . For such $S$ and $T$ , we define $V=S\cap T$ . $\hfill\blacktriangleleft$

Proof of Theorem 37.

Figure 4: The picture illustrates the proof for the matrix

\mathrm{HD}_{1}^{5}

. The parts

T_{i}

are colored red,

H_{i}

are colored green. By 1 not too many

1

-cells (black ones) are covered by the small blocks, so by 2 we find a permutation submatrix

S\times T

with very few covered

1

-cells, and then further shrink it using Lemma 38 to

A\times B

that does not contain any red cells at all. Then the rank of

\mathrm{HD}_{1}^{5}|_{A\times B}

is maximal, but the total rank of large blocks is small, which is a contradiction.

Let $M=\sum_{i\in[t]}S_{i}$ . We call a block small, if the sum of its dimensions is at most $s$ , and big otherwise. Assume the contrary and let $t\leq\frac{\gamma\cdot\mathsf{spar}(M)}{2kN}$ and $t\leq\frac{1}{4}\log_{2}\left(\frac{Ds}{2N}\right)$ .

We represent $S_{i}=T_{i}+H_{i}$ where $T_{i}$ is comprised of the small blocks of the matrix $T_{i}$ and $H_{i}$ of the big ones (i.e. the sets of non-zero columns of $T_{i}$ and $H_{i}$ are disjoint, same for the non-zero rows).

By 1, each $T_{i}$ covers (blocky matrix covers matrix entry, if this entry is non-zero in this matrix) at most $2kN$ $1$ -entries of $M$ , because the sum of block sizes in a spiky matrix does not exceed $2N$ . This implies that all small matrices cover at most $2Ntk\leq\gamma\cdot\mathsf{spar}(M)$ ones.

By 2 we get a permutation submatrix $S\times T$ and applying Lemma 38 to it $t$ times, we obtain a permutation submatrix $A\times B$ of $M$ with $|A|=|B|=D/2^{2t}$ , s.t. for each $i$ the intersection of $T_{i}$ and $A\times B$ is empty. Thus, we obtain

\mathrm{rk}\Big(M-\sum_{i\in[t]}T_{i}\Big)\geq\frac{D}{2^{2t}}

(1)

On the other hand, each $H_{i}$ contains at most $2N/{s}$ blocks, that means

\mathrm{rk}\Big(\sum_{i\in[t]}H_{i}\Big)\leq\sum_{i\in[t]}\mathrm{rk}(H_{i})% \leq t\cdot\frac{2N}{s}.

(2)

Combining (1) and (2), we get $D\cdot 2^{-2t}\leq 2Nt/{s},$ which implies $\tfrac{Ds}{2N}\leq 2^{3t},$ which contradicts our assumption. $\hfill\blacktriangleleft$

6.2 Hamming-Distance-1

$\mathrm{HD}_{1}^{n}$ is the function which determines whether the Hamming distance between the two input strings is 1. Its matrix is the adjacency matrix of the $n$ -dimensional Hamming cube.

\mathrm{HD}_{1}^{n}(x,y)=\begin{cases}1&\mbox{if }\|x\oplus y\|_{1}=1\\ 0&\mbox{otherwise}\end{cases}

See 8 We will make use of the following lemma.

Lemma 39 (Lemma 3.10 in [24]).

If $G=(V,E)$ is a subgraph of a Hamming cube, then

|V|\geq 2^{|E|/|V|}.

Proof of Theorem 8.

We use Theorem 37 with $N=2^{n}$ , $M=\mathrm{HD}_{1}^{n}$ , $s=2^{\sqrt{n}}$ , $k=2\sqrt{N}$ , $\gamma=0.5$ , $D=N/4$ . We now prove two conditions of the theorem. 1 directly from Lemma 39 applied to $S\cup T$ .

We proceed to prove 2. The $1$ -entries of $\mathrm{HD}_{1}^{n}$ are partitioned into the following $2n$ subsets:

K_{2i-j}=\{(x,y)\mid\mathrm{HD}_{1}^{n}(x,y)=1,x_{i}=j,y_{i}=1-j\}\text{ for $% i\in[n];$ $j\in\{0,1\}$}.

Thus, each $1$ -entry in $\mathrm{HD}_{1}^{n}$ belongs to exactly one of these subsets, and each subset has size $2^{n-1}$ . The subsets have the following property: if $(x,y)$ and $(v,w)$ are distinct elements of $K_{t}$ , then $\|x-w\|_{1}>1$ and $\|v-y\|_{1}>1$ , because we have $x_{i}=v_{i}\neq y_{i}=w_{i}$ for some $i$ . Thus, we have at least half of the $1$ -entries present in $M^{\prime}$ , which means one of the groups has at least $\frac{1}{2}2^{n-1}$ elements in the intersection with $M^{\prime}$ . Without loss of generality, we assume that it is the subset $K_{1}$ . Then we set

S\subseteq\{1\}\times\{0,1\}^{n-1},\nobreak\ \nobreak\ \nobreak\ T\subseteq\{0% \}\times\{0,1\}^{n-1},

such that $S\times T$ covers exactly $2^{n-2}$ $1$ -entries of $K_{1}$ , which are present in $M^{\prime}$ , and they form a permutation submatrix. So, the desired $\Omega(\sqrt{n})$ bound is immediately implied by the theorem. $\hfill\blacktriangleleft$

6.3 Expanders

For a graph $G$ , we denote by $M_{G}\in\{0,1\}^{N\times N}$ its adjacency matrix, i.e.,

(M_{G})_{u,v}\;=\;\begin{cases}1&\text{if }(u,v)\in E,\\ 0&\text{otherwise}.\end{cases}

We recall that an $(N,d,\lambda)$ -spectral expander is a $d$ -regular graph $G=(V,E)$ on $N$ vertices such that the second largest eigenvalue of its adjacency matrix $M_{G}$ is at most $\lambda$ in absolute value (see, for example, [21]).

Theorem 10. [Restated, see original statement.]

$\mathsf{spr}(M_{G})\geq\Omega\!\left(\min\!\left(\tfrac{d}{\lambda},\log\tfrac% {N}{d^{2}}\right)\right).$

Proof.

We use Theorem 37 with $M=M_{G}$ , $s=\tfrac{N\lambda}{10d}$ , $k=\lambda$ , $D=\tfrac{N}{4d}$ , $\gamma=1/2$ . We check the theorem conditions. 1 holds by the expander mixing lemma

e(S,T)\leq\frac{d|S||T|}{N}+\lambda\sqrt{|S||T|}\leq\frac{ds}{N}\sqrt{|S||T|}+% \lambda\sqrt{|S||T|}\leq 2\lambda\sqrt{|S||T|}\leq\lambda(|S|+|T|).

Let us prove 2. We pick edges greedily. At each step, when edge $e=\{u,v\}$ is picked, we throw away all vertices that are connected either to $u$ or $v$ . At each step, at most $2d-1$ vertices are used, so there will be at least $\tfrac{\gamma N}{2d}\geq\tfrac{N}{4d}$ steps and we get at least $D\times D$ permutation submatrix.

Applying the theorem, we get the desired bound. $\hfill\blacktriangleleft$ As an implication, we get an $\Omega(\log N)$ lower bound for $(N,\Theta(\log^{2}N),\Theta(\log N))$ -expanders:

Corollary 40.

There exists an explicit graph $G$ with $N$ nodes and degree $\Theta(\log^{2}N)$ such that

\mathsf{spr}(M_{G})=\Omega(\log N).

Proof.

It is shown in [3, Section 2.3] that for every prime $p$ with $p\bmod 4=1$ there exist two primes $q_{1},q_{2}=p^{\Theta(1)}$ such that for every $\ell\geq 1$ there exists a degree $p+1$ Ramanujan graph $G_{\ell}$ with $\Theta((q_{1}q_{2})^{3\ell})$ nodes, i.e. $G_{\ell}$ is a $(\Theta((q_{1}q_{2})^{3\ell}),p+1,2\sqrt{p})$ -spectral expander. Then the number of nodes in $G_{\ell}$ is $N_{\ell}=p^{\Theta(\ell)}$ , so taking $\ell=\sqrt{p}/\log p$ we get that $N_{\ell}=2^{\Theta(\sqrt{p})}$ , so $p=\Theta(\log^{2}N_{\ell})$ . Finally, we apply Theorem 10 to get the desired result. $\hfill\blacktriangleleft$

We get a stronger corollary for ultra-lossless vertex expanders. These are known to exist, but there are currently no explicit constructions.

Theorem 41.

Let $G$ be a $d$ -regular graph with $N$ vertices and vertex expansion $d-O(1)$ for at most $N^{\delta}$ vertex subsets, where $\delta\in(0,1)$ (i.e. for any $S\subseteq V(G)$ , it has at least $(d-O(1))|S|$ neighbors). Let $M_{G}$ be its adjacency matrix. Then $\mathsf{spr}(M_{G})\geq\Omega(\min(d,\log N)).$

Proof.

The proof is similar to the proof of Theorem 10, except for the proof of 1. It is proved in the following way.

Let $S\subseteq V$ with $|S|\leq N^{\delta}$ . By the assumption of the claim, it has at least $(d-O(1))|S|$ neighbors. On the other hand the sum of degrees of vertices in $|S|$ is $d|S|$ . Thus, for any $T\subseteq V(G)$ with $|T|=|S|$ we have $e(S,T)\leq d|S|-(d-O(1))|S|+|T|=O(|S|)$ . $\hfill\blacktriangleleft$

6.4 Inner Product and Disjointness

A simple consequence of the lower bound for random Boolean matrices (Theorem 24) is the following. Suppose an explicit $N\times N$ matrix $M$ contains a $k\times 2^{k}$ submatrix with all columns distinct. Then $\mathsf{spr}_{\pm}(M)\geq\Omega\left(\tfrac{k}{\log k}\right)$ . Indeed, such a submatrix necessarily contains every possible $k\times k$ Boolean matrix (up to column permutations, which do not affect $\mathsf{spr}_{\pm}$ ), and hence in particular one with maximum sign spiky rank $\Omega\left(\tfrac{k}{\log k}\right)$ .

The largest $k$ for which this holds is exactly the Vapnik–Chervonenkis dimension ${\rm VC}(M)$ of the matrix $M$ [33]. Thus we obtain the general bound

\mathsf{spr}_{\pm}(M)\geq\Omega\left(\frac{\mathrm{VC}(M)}{\log\mathrm{VC}(M)}% \right).

This observation immediately implies sign spiky rank lower bounds for Inner Product and Disjointness matrices. Recall that $\mathrm{IP}_{n}(x,y)=\sum_{i\in[n]}x_{i}y_{i}\bmod 2$ , where $x,y\in\{0,1\}^{n}$ , and $\textup{{Disj}}_{n}\in\{0,1\}^{N\times N}$ is defined with $\textup{{Disj}}_{n}(x,y)\coloneqq\bigwedge_{i\in[n]}\lnot x_{i}\lor\lnot y_{i}$ where $x$ and $y$ are identified with their binary representations.

Proposition 42.

$\mathsf{spr}_{\pm}(\mathrm{IP}_{n})\geq\Omega(\tfrac{n}{\log n})$ and $\mathsf{spr}_{\pm}(\textup{{Disj}}_{n})\geq\Omega(\tfrac{n}{\log n})$ .

Proof.

The VC-dimension of $\mathrm{IP}_{n}$ and $\textup{{Disj}}_{n}$ is at least $n$ . Consider the $n\times 2^{n}$ submatrix of $\textup{{Disj}}_{n}$ (or $\mathrm{IP}_{n}$ ) consisting of the $n$ rows indexed by the standard basis vectors

e_{i}\coloneqq(0^{i-1},1,0^{n-i}),\quad i\in[n].

For a column indexed by $x\in\{0,1\}^{n}$ , its entries in this submatrix are as follows:

$\blacksquare$

In the inner product matrix $\mathrm{IP}_{n}$ , the column is exactly the vector $x$ .
$\blacksquare$

In the Disjointness matrix $\textup{{Disj}}_{n}$ , the column is $1^{n}-x$ , where $1^{n}$ is the all-ones vector.

Thus the submatrix captures all distinct column patterns, corresponding either to $x$ (for $\mathrm{IP}_{n}$ ) or its complement (for $\textup{{Disj}}_{n}$ ). $\hfill\blacktriangleleft$

References

[1] Josh Alman and Ryan Williams. Probabilistic rank and matrix rigidity. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pages 641–652, New York, NY, USA, 2017. Association for Computing Machinery. doi:10.1145/3055399.3055484.
[2] Noga Alon. Covering graphs by the minimum number of equivalence relations. Combinatorica, 6(3):201–206, 1986. doi:10.1007/BF02579381.
[3] Noga Alon. Explicit expanders of every degree and size. Combinatorica, 41(4):447–463, 2021. doi:10.1007/s00493-020-4429-x.
[4] Noga Alon, Shay Moran, and Amir Yehudayoff. Sign rank versus VC dimension. In Conference on Learning Theory, pages 47–80. PMLR, 2016. URL: http://proceedings.mlr.press/v49/alon16.html.
[5] Benny Applebaum and Oded Nir. The meta-complexity of secret sharing. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, pages 965–976, 2025. doi:10.1145/3717823.3718161.
[6] Daniel Avraham and Amir Yehudayoff. On blocky ranks of matrices. Technical Report TR22-137, Electronic Colloquium on Computational Complexity (ECCC), September 2022. URL: https://eccc.weizmann.ac.il/report/2022/137/.
[7] Daniel Avraham and Amir Yehudayoff. On blocky ranks of matrices. computational complexity, 33, March 2024. doi:10.1007/s00037-024-00248-1.
[8] Igor Balla, Lianna Hambardzumyan, and István Tomon. Factorization norms and an inverse theorem for MaxCut. Mathematische Annalen, 394(3):52, February 2026. doi:10.1007/s00208-026-03355-2.
[9] Alexander R. Block, Simina Brânzei, Hemanta K. Maji, Himanshi Mehta, Tamalika Mukherjee, and Hai H. Nguyen. P₄-free partition and cover numbers & applications. In Stefano Tessaro, editor, 2nd Conference on Information-Theoretic Cryptography (ITC 2021), volume 199 of Leibniz International Proceedings in Informatics (LIPIcs), pages 16:1–16:25, Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ITC.2021.16.
[10] Arkadev Chattopadhyay, Nikhil S. Mande, and Suhail Sherif. The log-approximate-rank conjecture is false. Journal of the ACM, 67, 2020. doi:10.1145/3396695.
[11] Tsun Ming Cheung, Hamed Hatami, Rosie Zhao, and Itai Zilberstein. Boolean functions with small approximate spectral norm. Discrete Analysis, September 18 2024. doi:10.19086/da.122971.
[12] Péter Frankl. Covering graphs by equivalence relations. In North-Holland Mathematics Studies, volume 60, pages 125–127. Elsevier, 1982.
[13] Marcel K Goh and Hamed Hatami. Block complexity and idempotent Schur multipliers. International Mathematics Research Notices, 2025(24):356, 2025.
[14] Martin Golubitsky and Victor Guillemin. Stable mappings and their singularities, volume 14. Springer Science & Business Media, 2012.
[15] Mika Göös, Nathaniel Harms, Valentin Imbach, and Dmitry Sokolov. Sign-rank of $k$ -Hamming Distance is constant. arXiv preprint arXiv:2506.12022, 2025. doi:10.48550/arXiv.2506.12022.
[16] Mika Göös, Nathaniel Harms, and Artur Riazanov. Equality is far weaker than constant-cost communication. arXiv preprint arXiv:2507.11162, 2025. doi:10.48550/arXiv.2507.11162.
[17] Dima Grigoriev. An application of separability and independence notions for proving lower bounds of circuit complexity. J.Soviet Math., 14:1450–1456, January 1980.
[18] Lianna Hambardzumyan, Hamed Hatami, and Pooya Hatami. Dimension-free bounds and structural results in communication complexity. Israel Journal of Mathematics, 253(2):555–616, 2023.
[19] Lianna Hambardzumyan, Konstantin Myasnikov, Artur Riazanov, Morgan Shirley, and Adi Shraibman. Spiky rank and its applications to rigidity and circuits, 2026. doi:10.48550/arXiv.2602.23503.
[20] Kristoffer Arnsfelt Hansen and Vladimir V Podolskii. Exact threshold circuits. In 2010 IEEE 25th Annual Conference on Computational Complexity, pages 270–279. IEEE, 2010. doi:10.1109/CCC.2010.33.
[21] Shlomo Hoory, Nathan Linial, and Avi Wigderson. Expander graphs and their applications. Bull. Amer. Math. Soc., 43(04):439–562, August 2006. doi:10.1090/s0273-0979-06-01126-8.
[22] Stasys Jukna. On graph complexity. Combinatorics, Probability and Computing, 15(6):855–876, 2006. doi:10.1017/S0963548306007620.
[23] Daniel M Kane and Ryan Williams. Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 633–643, 2016. doi:10.1145/2897518.2897636.
[24] Rohan Karthikeyan, Siddharth Sinha, and Vallabh Patil. On the resolution of the sensitivity conjecture. Bulletin of the American Mathematical Society, 57:1, March 2020. doi:10.1090/bull/1697.
[25] Troy Lee and Adi Shraibman. Lower bounds in communication complexity. Foundations and Trends® in Theoretical Computer Science, 3(4):263–399, 2009. doi:10.1561/0400000040.
[26] Meena Mahajan. Depth-2 threshold circuits. Resonance, 24(3):371–380, March 2019. doi:10.1007/s12045-019-0786-4.
[27] Anirbit Mukherjee and Amitabh Basu. Lower bounds over Boolean inputs for deep neural networks with relu gates. arXiv preprint arXiv:1711.03073, 2017. arXiv:1711.03073.
[28] Toniann Pitassi, Morgan Shirley, and Adi Shraibman. The strength of equality oracles in communication. In Yael Tauman Kalai, editor, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023), volume 251 of Leibniz International Proceedings in Informatics (LIPIcs), pages 89:1–89:19, Dagstuhl, Germany, 2023. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ITCS.2023.89.
[29] P. Pudlák and V. Rödl. Some combinatorial-algebraic problems from complexity theory. Discrete Mathematics, 136(1):253–279, 1994. doi:10.1016/0012-365X(94)00115-Y.
[30] Alexander Razborov. On rigid matrices (in russian), 1989. URL: https://eccc.weizmann.ac.il/report/2022/137/.
[31] Vwani P Roychowdhury, Alon Orlitsky, and Kai-Yeung Siu. Lower bounds on threshold and related circuits via communication complexity. IEEE Transactions on Information Theory, 40(2):467–474, 1994. doi:10.1109/18.312169.
[32] Leslie G Valiant. Graph-theoretic arguments in low-level complexity. In Mathematical Foundations of Computer Science 1977: Proceedings, 6th Symposium, Tatranská Lomnica September 5–9, 1977 6, pages 162–176. Springer, 1977. doi:10.1007/3-540-08353-7_135.
[33] V. N. Vapnik and A. Ya. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability & Its Applications, 16(2):264–280, 1971.
[34] Hugh E Warren. Lower bounds for approximation by nonlinear manifolds. Transactions of the American Mathematical Society, 133(1):167–178, 1968.
[35] Ryan Williams. Limits on representing Boolean functions by linear combinations of simple functions: Thresholds, ReLUs, and low-degree polynomials. arXiv preprint arXiv:1802.09121, 2018. arXiv:1802.09121.
[36] Ryan Williams. The Orthogonal Vectors Conjecture and non-uniform circuit lower bounds. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pages 1372–1387, October 2024. doi:10.1109/FOCS61266.2024.00088.
[37] Ryan Williams. Personal communication, 2024.
[38] Henning Wunderlich. On a theorem of Razborov. computational complexity, 21:431–477, 2012. doi:10.1007/S00037-011-0021-5.

[bib.bib1] [1] Josh Alman and Ryan Williams. Probabilistic rank and matrix rigidity. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pages 641–652, New York, NY, USA, 2017. Association for Computing Machinery. doi:10.1145/3055399.3055484.

[bib.bib2] [2] Noga Alon. Covering graphs by the minimum number of equivalence relations. Combinatorica, 6(3):201–206, 1986. doi:10.1007/BF02579381.

[bib.bib3] [3] Noga Alon. Explicit expanders of every degree and size. Combinatorica, 41(4):447–463, 2021. doi:10.1007/s00493-020-4429-x.

[bib.bib4] [4] Noga Alon, Shay Moran, and Amir Yehudayoff. Sign rank versus VC dimension. In Conference on Learning Theory, pages 47–80. PMLR, 2016. URL: http://proceedings.mlr.press/v49/alon16.html.

[bib.bib5] [5] Benny Applebaum and Oded Nir. The meta-complexity of secret sharing. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, pages 965–976, 2025. doi:10.1145/3717823.3718161.

[bib.bib6] [6] Daniel Avraham and Amir Yehudayoff. On blocky ranks of matrices. Technical Report TR22-137, Electronic Colloquium on Computational Complexity (ECCC), September 2022. URL: https://eccc.weizmann.ac.il/report/2022/137/.

[bib.bib7] [7] Daniel Avraham and Amir Yehudayoff. On blocky ranks of matrices. computational complexity, 33, March 2024. doi:10.1007/s00037-024-00248-1.

[bib.bib8] [8] Igor Balla, Lianna Hambardzumyan, and István Tomon. Factorization norms and an inverse theorem for MaxCut. Mathematische Annalen, 394(3):52, February 2026. doi:10.1007/s00208-026-03355-2.

[bib.bib9] [9] Alexander R. Block, Simina Brânzei, Hemanta K. Maji, Himanshi Mehta, Tamalika Mukherjee, and Hai H. Nguyen. P₄-free partition and cover numbers & applications. In Stefano Tessaro, editor, 2nd Conference on Information-Theoretic Cryptography (ITC 2021), volume 199 of Leibniz International Proceedings in Informatics (LIPIcs), pages 16:1–16:25, Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ITC.2021.16.

[bib.bib10] [10] Arkadev Chattopadhyay, Nikhil S. Mande, and Suhail Sherif. The log-approximate-rank conjecture is false. Journal of the ACM, 67, 2020. doi:10.1145/3396695.

[bib.bib11] [11] Tsun Ming Cheung, Hamed Hatami, Rosie Zhao, and Itai Zilberstein. Boolean functions with small approximate spectral norm. Discrete Analysis, September 18 2024. doi:10.19086/da.122971.

[bib.bib12] [12] Péter Frankl. Covering graphs by equivalence relations. In North-Holland Mathematics Studies, volume 60, pages 125–127. Elsevier, 1982.

[bib.bib13] [13] Marcel K Goh and Hamed Hatami. Block complexity and idempotent Schur multipliers. International Mathematics Research Notices, 2025(24):356, 2025.

[bib.bib14] [14] Martin Golubitsky and Victor Guillemin. Stable mappings and their singularities, volume 14. Springer Science & Business Media, 2012.

[bib.bib15] [15] Mika Göös, Nathaniel Harms, Valentin Imbach, and Dmitry Sokolov. Sign-rank of $k$ -Hamming Distance is constant. arXiv preprint arXiv:2506.12022, 2025. doi:10.48550/arXiv.2506.12022.

[bib.bib16] [16] Mika Göös, Nathaniel Harms, and Artur Riazanov. Equality is far weaker than constant-cost communication. arXiv preprint arXiv:2507.11162, 2025. doi:10.48550/arXiv.2507.11162.

[bib.bib17] [17] Dima Grigoriev. An application of separability and independence notions for proving lower bounds of circuit complexity. J.Soviet Math., 14:1450–1456, January 1980.

[bib.bib18] [18] Lianna Hambardzumyan, Hamed Hatami, and Pooya Hatami. Dimension-free bounds and structural results in communication complexity. Israel Journal of Mathematics, 253(2):555–616, 2023.

[bib.bib19] [19] Lianna Hambardzumyan, Konstantin Myasnikov, Artur Riazanov, Morgan Shirley, and Adi Shraibman. Spiky rank and its applications to rigidity and circuits, 2026. doi:10.48550/arXiv.2602.23503.

[bib.bib20] [20] Kristoffer Arnsfelt Hansen and Vladimir V Podolskii. Exact threshold circuits. In 2010 IEEE 25th Annual Conference on Computational Complexity, pages 270–279. IEEE, 2010. doi:10.1109/CCC.2010.33.

[bib.bib21] [21] Shlomo Hoory, Nathan Linial, and Avi Wigderson. Expander graphs and their applications. Bull. Amer. Math. Soc., 43(04):439–562, August 2006. doi:10.1090/s0273-0979-06-01126-8.

[bib.bib22] [22] Stasys Jukna. On graph complexity. Combinatorics, Probability and Computing, 15(6):855–876, 2006. doi:10.1017/S0963548306007620.

[bib.bib23] [23] Daniel M Kane and Ryan Williams. Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 633–643, 2016. doi:10.1145/2897518.2897636.

[bib.bib24] [24] Rohan Karthikeyan, Siddharth Sinha, and Vallabh Patil. On the resolution of the sensitivity conjecture. Bulletin of the American Mathematical Society, 57:1, March 2020. doi:10.1090/bull/1697.

[bib.bib25] [25] Troy Lee and Adi Shraibman. Lower bounds in communication complexity. Foundations and Trends® in Theoretical Computer Science, 3(4):263–399, 2009. doi:10.1561/0400000040.

[bib.bib26] [26] Meena Mahajan. Depth-2 threshold circuits. Resonance, 24(3):371–380, March 2019. doi:10.1007/s12045-019-0786-4.

[bib.bib27] [27] Anirbit Mukherjee and Amitabh Basu. Lower bounds over Boolean inputs for deep neural networks with relu gates. arXiv preprint arXiv:1711.03073, 2017. arXiv:1711.03073.

[bib.bib28] [28] Toniann Pitassi, Morgan Shirley, and Adi Shraibman. The strength of equality oracles in communication. In Yael Tauman Kalai, editor, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023), volume 251 of Leibniz International Proceedings in Informatics (LIPIcs), pages 89:1–89:19, Dagstuhl, Germany, 2023. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ITCS.2023.89.

[bib.bib29] [29] P. Pudlák and V. Rödl. Some combinatorial-algebraic problems from complexity theory. Discrete Mathematics, 136(1):253–279, 1994. doi:10.1016/0012-365X(94)00115-Y.

[bib.bib30] [30] Alexander Razborov. On rigid matrices (in russian), 1989. URL: https://eccc.weizmann.ac.il/report/2022/137/.

[bib.bib31] [31] Vwani P Roychowdhury, Alon Orlitsky, and Kai-Yeung Siu. Lower bounds on threshold and related circuits via communication complexity. IEEE Transactions on Information Theory, 40(2):467–474, 1994. doi:10.1109/18.312169.

[bib.bib32] [32] Leslie G Valiant. Graph-theoretic arguments in low-level complexity. In Mathematical Foundations of Computer Science 1977: Proceedings, 6th Symposium, Tatranská Lomnica September 5–9, 1977 6, pages 162–176. Springer, 1977. doi:10.1007/3-540-08353-7_135.

[bib.bib33] [33] V. N. Vapnik and A. Ya. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability & Its Applications, 16(2):264–280, 1971.

[bib.bib34] [34] Hugh E Warren. Lower bounds for approximation by nonlinear manifolds. Transactions of the American Mathematical Society, 133(1):167–178, 1968.

[bib.bib35] [35] Ryan Williams. Limits on representing Boolean functions by linear combinations of simple functions: Thresholds, ReLUs, and low-degree polynomials. arXiv preprint arXiv:1802.09121, 2018. arXiv:1802.09121.

[bib.bib36] [36] Ryan Williams. The Orthogonal Vectors Conjecture and non-uniform circuit lower bounds. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pages 1372–1387, October 2024. doi:10.1109/FOCS61266.2024.00088.

[bib.bib37] [37] Ryan Williams. Personal communication, 2024.

[bib.bib38] [38] Henning Wunderlich. On a theorem of Razborov. computational complexity, 21:431–477, 2012. doi:10.1007/S00037-011-0021-5.

Spiky Rank and Its Applications to Rigidity and Circuits

Abstract

Keywords and phrases:

Category:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Acknowledgements:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Definition 1 (Blocky and Spiky Matrices).

Definition 2 (Blocky and Spiky Rank).

1.1 Motivations for Blocky and Spiky Rank

Blocky rank.

Spiky rank.

1.2 Results

1.2.1 Application to Matrix Rigidity

Theorem 1.

Major Open Problem 2.

Major Open Problem 3.

1.2.2 Application to Circuit Complexity

Proposition 4.

Open Problem 5.

1.2.3 Bounds for Random Matrices

Theorem 6 (Informal).

Theorem 7 (Informal).

1.2.4 Bounds for Specific Matrices

Theorem 8.

Open Problem 9.

Theorem 10.

Open Problem 11.

1.2.5 Relations to other matrix parameters

Blocky rank

Question 12.

Theorem 13.

𝜸𝟐-norm

Theorem 14.

Sparsity

Sign and approximate measures

Question 15.

Organization.

2 Preliminaries

Blocky and spiky measures.

Definition 16.

Definition 17.

Fact 18 (Subadditivity).

Fact 19 (Upper bounds).

Sign blocky rank and sign spiky rank.

Definition 20.

Fact 21 (Upper bounds for sign measures.).

3 Non-explicit lower bounds for spiky rank

3.1 Lower bound for random Boolean matrices

Theorem 22 ([34]).

Lemma 23.

Proof.

Theorem 24.

Proof.

3.2 Lower bound for real matrices

Theorem 25.

Proof.

Fact 26.

Proof.

4 Connection to matrix rigidity

Definition 27 (Rigidity).

Theorem 28.

Lemma 29.

Proof of Theorem 28.

▶ Remark 30.

▶ Remark 31.

Theorem 32 ([38, Theorem 5.15]).

Corollary 33.

Proof.

5 Connection to circuit complexity

Definition 34.

Claim 35.

Proof.

$\gamma_{2}$ -norm

$\blacktriangleright$ Remark 30.

$\blacktriangleright$ Remark 31.