Recently a post was made in Mathoverflow seeking possible avenues for collaborative projects.

I made a proposal for Log Rank conjecture in https://mathoverflow.net/questions/219638/proposals-for-polymath-projects/219639#219639 which has been well received so far

I feel that this is a good project for collaborative approach.

I know this is a fundamental open problem in CS.

1. Is there a list of possible avenues of research that could open up if progress comes on this topic? For example, I know there are connections to Matrix Rigidity.

2. Could we have a list of possible impact of Log Rank Conjecture and related research in CS?


it seems researchers might be cautious/ unlikely to conjecture/ speculate solution to this problem would likely/ definitely open up other areas (eg one you list of matrix rigidity is provably nearly equivalent to the extremely hard challenge of proving nontrivial lower bounds on eg circuits etc) but it definitely provably touches many areas. here is a nice recent survey (Jan 2015) by Lovett that lists "many connections" sec 6 along with two other refs that show crosscutting connections/ formulations

  • 4
    $\begingroup$ I find your first "sentence" / random concatenation of words completely incomprehensible. Where does it even end? Why would researchers be cautious? What are the many other areas, besides communication complexity? The rigidity connection is not at all that strong. The log-rank conjecture itself implies nothing about rigidity, rather Lovett states a different conjecture which does. And even then the result would only slightly improve existing rigidity bounds and not imply any new circuit lower bounds. $\endgroup$ – Sasho Nikolov Oct 3 '15 at 3:47
  • $\begingroup$ @SashoNikolov I see your point now. Thank you. $\endgroup$ – user34945 Oct 4 '15 at 0:40
  • $\begingroup$ ok! point(s) taken, lets try to sort it out in Theoretical Computer Science Chat for anyone who is seriously interested in/ has time for real constructive effort expended toward a sparkling/ in depth/ unassailable answer (if one even exists) instead of just shooting down any good faith attempt. ofc encourage/ am interested in any alternative answer(s) $\endgroup$ – vzn Oct 4 '15 at 16:04
  • 2
    $\begingroup$ Or you could, you know, edit your answer for once to make it readable and clear. $\endgroup$ – Sasho Nikolov Oct 5 '15 at 0:04
  • $\begingroup$ @vzn I think you should remove your post. $\endgroup$ – user34945 Oct 5 '15 at 17:41