Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR97-043 | 28th August 1998 00:00

Some structural properties of low rank matrices related to computational complexity Revision of: TR97-043

RSS-Feed




Revision #1
Authors: Bruno Codenotti, Pavel Pudlak, Giovanni Resta
Accepted on: 28th August 1998 00:00
Downloads: 3427
Keywords: 


Abstract:

We consider the problem of the presence of short cycles in the
graphs of nonzero elements of matrices which have sublinear rank
and nonzero entries on the main diagonal, and analyze the connection between
these properties and the rigidity of matrices. In particular, we
exhibit a family of matrices which
shows that sublinear rank does not imply the existence of
triangles. This family can also be used to give a constructive
bound of the order of $k^{3/2}$ on the Ramsey number $R(3,k)$, which matches
the best known bound. On the other hand we show that sublinear
rank implies the existence of 4-cycles. Finally, we prove some
partial results towards establishing lower bounds on matrix
rigidity and consequently on the size of logarithmic depth arithmetic
circuits for computing certain explicit linear transformations.


Paper:

TR97-043 | 25th September 1997 00:00

Some structural properties of low rank matrices related to computational complexity





TR97-043
Authors: Bruno Codenotti, Pavel Pudlak, Giovanni Resta
Publication: 25th September 1997 18:52
Downloads: 2226
Keywords: 


Abstract:

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 an explicit linear transformation cannot be computed by
linear size and logarithmic depth circuits. We prove some
partial results supporting the conjecture.


Comment(s):

Comment #1 to TR97-043 | 3rd December 1997 08:33

A remark on the 'Triangle Conjecture' Comment on: TR97-043





Comment #1
Authors: Bruno Codenotti, Pavel Pudlak, Giovanni Resta
Accepted on: 3rd December 1997 08:33
Downloads: 1825
Keywords: 


Abstract:

Some of the results of the paper have been based on the
'Triangle Conjecture'. Here we show that this conjecture,
in its general form, is false, by describing the construction
of a matrix with ones on the main diagonal, with sublinear rank,
and such that the graph obtained by associating edges to nonzero
entries of the matrix does not have 'transitive triangles'.
As a byproduct of the above result, we find a constructive bound on
the Ramsey number $R(3,n)$. The bound is asymptotically the same as
the one by Alon in "Explicit Ramsey graphs and orthonormal labelings"
(Electronic Journal of Combinatorics 1 (1994), R12), but our
construction is far simpler.




ISSN 1433-8092 | Imprint