Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > RIGIDITY:
Reports tagged with rigidity:
TR02-012 | 3rd February 2002
Ran Raz

#### On the Complexity of Matrix Product

We prove a lower bound of $\Omega(m^2 \log m)$ for the size of
any arithmetic circuit for the product of two matrices,
over the real or complex numbers, as long as the circuit doesn't
use products with field elements of absolute value larger than 1
(where $m \times m$ is ... more >>>

TR12-144 | 6th November 2012
Rocco Servedio, Emanuele Viola

#### On a special case of rigidity

We highlight the special case of Valiant's rigidity
problem in which the low-rank matrices are truth-tables
of sparse polynomials. We show that progress on this
special case entails that Inner Product is not computable
by small $\acz$ circuits with one layer of parity gates
close to the inputs. We then ... more >>>

TR18-188 | 7th November 2018
Zeev Dvir, Alexander Golovnev, Omri Weinstein

#### Static Data Structure Lower Bounds Imply Rigidity

Revisions: 2

We show that static data structure lower bounds in the group (linear) model imply semi-explicit lower bounds on matrix rigidity. In particular, we prove that an explicit lower bound of $t \geq \omega(\log^2 n)$ on the cell-probe complexity of linear data structures in the group model, even against arbitrarily small ... more >>>

TR21-003 | 6th January 2021
Lijie Chen, Xin Lyu

#### Inverse-Exponential Correlation Bounds and Extremely Rigid Matrices from a New Derandomized XOR Lemma

In this work we prove that there is a function $f \in \textrm{E}^\textrm{NP}$ such that, for every sufficiently large $n$ and $d = \sqrt{n}/\log n$, $f_n$ ($f$ restricted to $n$-bit inputs) cannot be $(1/2 + 2^{-d})$-approximated by $\textrm{F}_2$-polynomials of degree $d$. We also observe that a minor improvement ... more >>>

ISSN 1433-8092 | Imprint