tag:blogger.com,1999:blog-3722233.post112065935867045745..comments2023-09-30T21:44:03.907-05:00Comments on Computational Complexity: Matrix RigidityLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-3722233.post-1120778822473117312005-07-07T18:27:00.000-05:002005-07-07T18:27:00.000-05:00----------------------------------------Why was th...----------------------------------------<BR/>Why was this very simple proof missed before? Is it because people focused on so-called generalized Hadamard matrices and were thus determined to use spectral techniques?<BR/>----------------------------------------<BR/>Well, as I understand the applications for this problem: a lower bound for ANY EXPLICIT matrix is welcomed from the point of view of circuits complexity. For communication complexity, any explicit (0,1)-matrix is interesting.<BR/><BR/>----------------------------------------<BR/>This isn't the proof Nisan used for "totally non-singular" matrices?<BR/>----------------------------------------<BR/>I have not read Nisan's proof (and how I could?), but I guess I didn't prove that Sylvester matrix is totally non-singular.<BR/><BR/>----------------------------------------<BR/>In fact, it's so trivial that no one ever thinks about explicitly mentioning it in a publication!<BR/>----------------------------------------<BR/>Hmm, I didn't found this <B>so</B> trivial fact even mentioned at many papers I went through, despite more trivial facts were mentioned. Even in a low-level survey paper by B. Codenotti (Matrix Rigidity, Linear Algebra and its Applications, 304(1-3):181�192. 2000.) <BR/><BR/>----------------------------------------<BR/>I guess every sensible person who has just tried to (rather seriously) think about matrix rigidity comes up with a similar result after a short time.<BR/>----------------------------------------<BR/>I know at least one researcher on this field that didn't know this fact before.<BR/><BR/><BR/><BR/>The moral of this story: those who write serious publications and survey papers should sometimes mention trivial facts as well for new ones in the field. Anyway, I agree, this paper is not much more than a curiosity.<BR/><BR/>--GatisAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1120730840111034692005-07-07T05:07:00.000-05:002005-07-07T05:07:00.000-05:00It's a very good point to write up simple results ...It's a very good point to write up simple results (because you never know if it's as simple for the others or not), but of course this simple proof hasn't been missed before. In fact, it's so trivial that no one ever thinks about explicitly mentioning it in a publication! I guess every sensible person who has just tried to (rather seriously) think about matrix rigidity comes up with a similar result after a short time. So this is more or less a "warm-up exercise," but of course, as I said, is still worth putting on arXiv. Unfortunately, the proof doesn't give much to us, as it doesn't deeply go down into the specific combinatorial structure of the matrix. Moreover, the result of Shokrollahi et al. (1997) shows a stronger lower bound of $\Omega(n^2/r log(n/r))$ for the same problem based on a similar principle (minors with high ranks), still far from implying nontrivial complexity results. Their proof is already simple enough.<BR/><BR/>Finally, one can as easily show a lower bound $\Omega(n^2/r)$ for the rigidity any matrix whose $t \times t$ submatrices have rank $\Omega(t)$ "on average." (apologies for using TeX macros here!!)<BR/><BR/>Precisely, let $A+B=C$, where $rk(C) <= r$, and the "expected rank" of a random $t \times t$ minor be at least $t/c$, for some constant $c$. Now, let $t=2rc$ and A0 be a $t \times t$ minor of A. Let B0 and C0 be the corresponding minors in B and C (minors chosen with the same pattern). We have: <BR/><BR/>$2r = t/c <= E[rk(A0)] <= E[rk(C0)]+E[rk(B0)] <= E[rk(C)]+E[rk(B0)] <= r+E[rk(B0)] <= r+E[wt(B0)] <= r+(t/n)^2 wt(B)$<BR/><BR/>Hence, $r <= (4c^2r^2/n^2) Rig_A(r)$ and we're done.<BR/><BR/>One example of such matrices is the generalized (complex) Hadamard matrix. So we've just proved the best known lower bound for rigidity of the general case of Hadamard matrices (modulo showing that the expected ranks are high which is a bit messy but straightforward spectral analysis for the case of Hadamard matrices). In fact, the proof of Kashin and Razborov (1998) goes along similar lines.<BR/><BR/>In any case, it's very nice to see new works being done on rigid matrices. They hopefully draw researchers' attention to put more efforts on this long-standing but nowadays less-cared-about problem.Mahdihttps://www.blogger.com/profile/12382401759237060260noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1120703257960107462005-07-06T21:27:00.000-05:002005-07-06T21:27:00.000-05:00I believe this is a well-known proof for showing t...I believe this is a well-known proof for showing that the Hadamard matrix has rigidity function n^2/r, and it is due (in unpublished form) independently to Grigoriev and Nisan (over ten years ago).<BR/><BR/>There are more sophisticated counting techniques based on the same principle (i.e. the non-singularity of sub-matrices). See, for instance,<BR/>http://www-math.mit.edu/~spielman/Research/rigid.html.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1120692338691977262005-07-06T18:25:00.000-05:002005-07-06T18:25:00.000-05:00Why was this very simple proof missed before? Is ...Why was this very simple proof missed before? Is it because people focused on so-called generalized Hadamard matrices and were thus determined to use spectral techniques? This isn't the proof Nisan used for "totally non-singular" matrices?Anonymousnoreply@blogger.com