License: 
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2009.2327
URN: urn:nbn:de:0030-drops-23278
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2009/2327/
Kumar, Abhinav ;
Lokam, Satyanarayana V. ;
Patankar, Vijay M. ;
Sarma M. N., Jayalal
Using Elimination Theory to construct Rigid Matrices
Abstract
The rigidity of a matrix $A$ for target rank $r$ is the minimum number
of entries of $A$ that must be changed to ensure that the rank of
the altered matrix is at most $r$. Since its introduction by Valiant
\cite{Val77}, rigidity and similar rank-robustness functions of
matrices have found numerous applications in circuit complexity,
communication complexity, and learning complexity. Almost all $\nbyn$
matrices over an infinite field have a rigidity of $(n-r)^2$. It is a
long-standing open question to construct infinite families of
\emph{explicit} matrices even with superlinear rigidity when $r=\Omega(n)$.
In this paper, we construct an infinite family of complex matrices
with the largest possible, i.e., $(n-r)^2$, rigidity. The entries of
an $\nbyn$ matrix in this family are distinct primitive roots of unity
of orders roughly \SL{$\exp(n^4 \log n)$}. To the best of our knowledge, this is
the first family of concrete (but not entirely explicit) matrices
having maximal rigidity and a succinct algebraic description.
Our construction is based on elimination theory of polynomial
ideals. In particular, we use results on the existence of polynomials
in elimination ideals with effective degree upper bounds (effective
Nullstellensatz). Using elementary algebraic geometry, we prove that
the dimension of the affine variety of matrices of rigidity at
most $k$ is exactly $n^2 - (n-r)^2 +k$. Finally, we use elimination theory to
examine whether the rigidity function is semicontinuous.
BibTeX - Entry
@InProceedings{kumar_et_al:LIPIcs:2009:2327,
author = {Abhinav Kumar and Satyanarayana V. Lokam and Vijay M. Patankar and Jayalal Sarma M. N.},
title = {{Using Elimination Theory to construct Rigid Matrices}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
pages = {299--310},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-13-2},
ISSN = {1868-8969},
year = {2009},
volume = {4},
editor = {Ravi Kannan and K. Narayan Kumar},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2009/2327},
URN = {urn:nbn:de:0030-drops-23278},
doi = {10.4230/LIPIcs.FSTTCS.2009.2327},
annote = {Keywords: Matrix Rigidity, Lower Bounds, Circuit Complexity}
}
|
Keywords: |
|
Matrix Rigidity, Lower Bounds, Circuit Complexity |
|
Collection: |
|
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science |
|
Issue Date: |
|
2009 |
|
Date of publication: |
|
14.12.2009 |
