Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > MATRIX RIGIDITY:
Reports tagged with Matrix Rigidity:
TR97-043 | 25th September 1997
Bruno Codenotti, Pavel Pudlak, Giovanni Resta

#### Some structural properties of low rank matrices related to computational complexity

We consider the conjecture stating that a matrix with rank
$o(n)$ and ones on the main diagonal must contain nonzero
entries on a $2\times 2$ submatrix with one entry on the main
diagonal. We show that a slightly stronger conjecture implies
that ... more >>>

TR98-075 | 9th December 1998

#### Graph Nonisomorphism has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses.

We establish hardness versus randomness trade-offs for a
broad class of randomized procedures. In particular, we create efficient
nondeterministic simulations of bounded round Arthur-Merlin games using
a language in exponential time that cannot be decided by polynomial
language with ... more >>>

TR05-070 | 6th July 2005
Mahdi Cheraghchi

#### On Matrix Rigidity and the Complexity of Linear Forms

The rigidity function of a matrix is defined as the minimum number of its entries that need to be changed in order to reduce the rank of the matrix to below a given parameter. Proving a strong enough lower bound on the rigidity of a matrix implies a nontrivial lower ... more >>>

TR08-065 | 11th July 2008
Noga Alon, Rina Panigrahy, Sergey Yekhanin

#### Deterministic Approximation Algorithms for the Nearest Codeword Problem

The Nearest Codeword Problem (NCP) is a basic algorithmic question in the theory of error-correcting codes. Given a point v in an n-dimensional space over F_2 and a linear subspace L in F_2^n of dimension k NCP asks to find a point l in L that minimizes the (Hamming) distance ... more >>>

TR09-008 | 15th January 2009
Stasys Jukna, Georg Schnitger

#### Min-Rank Conjecture for Log-Depth Circuits

A completion of an m-by-n matrix A with entries in {0,1,*} is obtained
by setting all *-entries to constants 0 or 1. A system of semi-linear
equations over GF(2) has the form Mx=f(x), where M is a completion of
A and f:{0,1}^n --> {0,1}^m is an operator, the i-th coordinate ... more >>>

TR09-084 | 24th September 2009

#### Linear systems over composite moduli

We study solution sets to systems of generalized linear equations of the following form:
$\ell_i (x_1, x_2, \cdots , x_n)\, \in \,A_i \,\, (\text{mod } m)$,
where $\ell_1, \ldots ,\ell_t$ are linear forms in $n$ Boolean variables, each $A_i$ is an arbitrary subset of $\mathbb{Z}_m$, and $m$ is a composite ... more >>>

TR10-086 | 17th May 2010
Henning Wunderlich

#### On a Theorem of Razborov

In an unpublished Russian manuscript Razborov proved that a matrix family with high
rigidity over a finite field would yield a language outside the polynomial hierarchy
in communication complexity.

We present an alternative proof that strengthens the original result in several ways.
In particular, we replace rigidity by the strictly ... more >>>

TR10-149 | 22nd September 2010
Boaz Barak, Zeev Dvir, Avi Wigderson, Amir Yehudayoff

#### Rank Bounds for Design Matrices with Applications to Combinatorial Geometry and Locally Correctable Codes

Revisions: 1

A $(q,k,t)$-design matrix is an m x n matrix whose pattern of zeros/non-zeros satisfies the following design-like condition: each row has at most $q$ non-zeros, each column has at least $k$ non-zeros and the supports of every two columns intersect in at most t rows. We prove that the rank ... more >>>

TR11-044 | 25th March 2011
Shubhangi Saraf, Sergey Yekhanin

#### Noisy Interpolation of Sparse Polynomials, and Applications

Let $f\in F_q[x]$ be a polynomial of degree $d\leq q/2.$ It is well-known that $f$ can be uniquely recovered from its values at some $2d$ points even after some small fraction of the values are corrupted. In this paper we establish a similar result for sparse polynomials. We show that ... more >>>

TR12-133 | 21st October 2012
Noga Alon, Gil Cohen

#### On Rigid Matrices and Subspace Polynomials

Revisions: 1

We introduce a class of polynomials, which we call \emph{subspace polynomials} and show that the problem of explicitly constructing a rigid matrix can be reduced to the problem of explicitly constructing a small hitting set for this class. We prove that small-bias sets are hitting sets for the class of ... more >>>

TR13-043 | 25th March 2013
Oded Goldreich, Avi Wigderson

#### On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions

Revisions: 1

We propose that multi-linear functions of relatively low degree
over GF(2) may be good candidates for obtaining exponential
lower bounds on the size of constant-depth Boolean circuits
(computing explicit functions).
Specifically, we propose to move gradually from linear functions
to multilinear ones, and conjecture that, for any $t\geq2$,
more >>>

TR14-172 | 12th December 2014
Alex Samorodnitsky, Ilya Shkredov, Sergey Yekhanin

#### Kolmogorov Width of Discrete Linear Spaces: an Approach to Matrix Rigidity

A square matrix $V$ is called rigid if every matrix $V^\prime$ obtained by altering a small number of entries of $V$ has sufficiently high rank. While random matrices are rigid with high probability, no explicit constructions of rigid matrices are known to date. Obtaining such explicit matrices would have major ... more >>>

TR15-079 | 7th May 2015
Oded Goldreich, Avishay Tal

#### Matrix Rigidity of Random Toeplitz Matrices

We prove that random $n$-by-$n$ Toeplitz (alternatively Hankel) matrices over $GF(2)$ have rigidity $\Omega(\frac{n^3}{r^2\log n})$ for rank $r \ge \sqrt{n}$, with high probability. This improves, for $r = o(n/\log n \log\log n)$, over the $\Omega(\frac{n^2}{r} \cdot\log(\frac{n}{r}))$ bound that is known for many explicit matrices.

Our result implies that the explicit ... more >>>

TR16-093 | 4th June 2016
Cyrus Rashtchian

#### Bounded Matrix Rigidity and John's Theorem

Using John's Theorem, we prove a lower bound on the bounded rigidity of a sign matrix, defined as the Hamming distance between this matrix and the set of low-rank, real-valued matrices with entries bounded in absolute value. For Hadamard matrices, our asymptotic leading constant is tighter than known results by ... more >>>

TR17-193 | 31st December 2017
Oded Goldreich, Avishay Tal

#### On Constant-Depth Canonical Boolean Circuits for Computing Multilinear Functions

We consider new complexity measures for the model of multilinear circuits with general multilinear gates introduced by Goldreich and Wigderson (ECCC, 2013).
These complexity measures are related to the size of canonical constant-depth Boolean circuits, which extend the definition of canonical depth-three Boolean circuits.
We obtain matching lower and upper ... more >>>

TR19-143 | 25th October 2019
Sivaramakrishnan Natarajan Ramamoorthy, Cyrus Rashtchian

#### Equivalence of Systematic Linear Data Structures and Matrix Rigidity

Recently, Dvir, Golovnev, and Weinstein have shown that sufficiently strong lower bounds for linear data structures would imply new bounds for rigid matrices. However, their result utilizes an algorithm that requires an $NP$ oracle, and hence, the rigid matrices are not explicit. In this work, we derive an equivalence between ... more >>>

TR20-039 | 25th March 2020
Pranjal Dutta, Nitin Saxena, Thomas Thierauf

#### Lower bounds on the sum of 25th-powers of univariates lead to complete derandomization of PIT

We consider the univariate polynomial $f_d:=(x+1)^d$ when represented as a sum of constant-powers of univariate polynomials. We define a natural measure for the model, the support-union, and conjecture that it is $\Omega(d)$ for $f_d$.

We show a stunning connection of the conjecture to the two main problems in algebraic ... more >>>

TR20-041 | 29th March 2020
Mrinal Kumar, Ben Lee Volk

#### A Polynomial Degree Bound on Defining Equations of Non-rigid Matrices and Small Linear Circuits

Revisions: 2

We show that there is a defining equation of degree at most poly(n) for the (Zariski closure of the) set of the non-rigid matrices: that is, we show that for every large enough field $\mathbb{F}$, there is a non-zero $n^2$-variate polynomial $P \in \mathbb{F}(x_{1, 1}, \ldots, x_{n, n})$ of degree ... more >>>

TR20-075 | 6th May 2020

#### Rigid Matrices From Rectangular PCPs

Revisions: 2

We introduce a variant of PCPs, that we refer to as *rectangular* PCPs, wherein proofs are thought of as square matrices, and the random coins used by the verifier can be partitioned into two disjoint sets, one determining the *row* of each query and the other determining the *column*.

We ... more >>>

TR20-150 | 7th October 2020
Lijie Chen, Xin Lyu, Ryan Williams

#### Almost-Everywhere Circuit Lower Bounds from Non-Trivial Derandomization

In certain complexity-theoretic settings, it is notoriously difficult to prove complexity separations which hold almost everywhere, i.e., for all but finitely many input lengths. For example, a classical open question is whether $\mathrm{NEXP} \subset \mathrm{i.o.-}\mathrm{NP}$; that is, it is open whether nondeterministic exponential time computations can be simulated on infinitely ... more >>>

TR20-173 | 18th November 2020
Kunal Mittal, Ran Raz

#### Block Rigidity: Strong Multiplayer Parallel Repetition implies Super-Linear Lower Bounds for Turing Machines

Revisions: 1

We prove that a sufficiently strong parallel repetition theorem for a special case of multiplayer (multiprover) games implies super-linear lower bounds for multi-tape Turing machines with advice. To the best of our knowledge, this is the first connection between parallel repetition and lower bounds for time complexity and the first ... more >>>

TR21-179 | 8th December 2021
tatsuie tsukiji

#### Smoothed Complexity of Learning Disjunctive Normal Forms, Inverting Fourier Transforms, and Verifying Small Circuits

This paper aims to derandomize the following problems in the smoothed analysis of Spielman and Teng. Learn Disjunctive Normal Form (DNF), invert Fourier Transforms (FT), and verify small circuits' unsatisfiability. Learning algorithms must predict a future observation from the only $m$ i.i.d. samples of a fixed but unknown joint-distribution $P(G(x),y)$ ... more >>>