<p>If a massively online collaboration is set up, then it should try to focus on problems with a reasonable chance of success. The three classical construction problems of antiquity are known as "squaring the circle", "trisecting an angle", and "doubling a cube". Modern mathematics resolved all three, but much more important was the earlier Descartes revolution, which enabled mathematics to free itself from the mental prison of compass and straightedge constructions. Notice that the Greeks used compass and straightedge as a practical computational device, as witnessed by the <a href="https://en.wikipedia.org/wiki/Deferent_and_epicycle" rel="nofollow">efficient epicycle approximation scheme</a> for celestial mechanics computations.</p>

<p>Many conjectures and generalizations of solved conjectures from graph theory should be amenable to solutions by collaboration. However, typical experience with collaborations suggest that teams of 2-4 members are far more effective than significantly larger teams. An example of a very successful team in this area are N. Robertson, P.D. Seymour and R. Thomas, which attacked problems like the strong perfect graph conjecture, generalizations of the four color theorem, and graph minor related conjectures. The elapsed time between announcement of new results and their actual publication has been notoriously long, also for other teams of researchers in the same area, indicating that pure workload volume here is slowing things down, so that collaboration (which already happens) could be beneficial to speed things up. (I'm still curious when some of the announced generalizations of graph minor related results for directed graphs will be published, and whether the people who will finally publish them will be the ones which initially announced the results.)</p>

<p>I currently try to understand the role of completeness of intuitionistic logic in practical applications of computer assisted proof refutation. But if you really plan to do proofs by massively online collaborations, then having a solid computer assisted proof refutation system in place might really be important. After all, if you don't know your collaborators sufficiently well, how will you be able to judge whether you can trust their contributions, without wasting a significant amount of time checking everything they did? (I have the impression that mathematicians are more used to proof refutation and enjoy its positive sides like direct personal feedback, while computer scientists show less routine with this sort of feedback.) Anyway, establishing that proof refutation is a natural part of collaboration when tackling difficult problems seems like a good idea to me.</p>

CC BY-SA 3.0
2015-09-13T16:33:54.310Z
2015-09-13T16:33:54.310Z
Thomas Klimpel
<p>Polymath projects seems to succeed when a breakthrough happens, and one is trying to optimize the result of the breakthrough or come up with simpler or better proof. See <a href="https://en.wikipedia.org/wiki/Polymath_Project#Problems_solved">https://en.wikipedia.org/wiki/Polymath_Project#Problems_solved</a>. As such, you would have to pick a problem of this nature in CS. The only one that comes immediately to mind is improving the constant in matrix multiplication <a href="https://en.wikipedia.org/wiki/Matrix_multiplication#Algorithms_for_efficient_matrix_multiplication">https://en.wikipedia.org/wiki/Matrix_multiplication#Algorithms_for_efficient_matrix_multiplication</a>, which is currently at 2.4... But frankly, I am not sure enough people care about it enough to work on it...</p>

<p>Questions for which I would expect polymath to fail miserably: P=NP, online optimality, UGC, etc. </p>

CC BY-SA 3.0
2015-09-13T08:16:27.520Z
Well, some time ago, there was a kind of polymath project to analyze an announced proof of P = NP, which turned out to be incorrect...
J.-E. Pin
CC BY-SA 3.0
2015-09-13T12:52:12.093Z
Matrix multiplication has become popular recently...
Yuval Filmus
CC BY-SA 3.0
2015-09-13T14:48:05.127Z
Finding cleaner versions of proofs of the PCP theorems might be a useful endeavor they could do.
Phylliida
CC BY-SA 3.0
2015-09-13T15:38:21.757Z
@J.-E.Pin: so the project was a success!
cody
CC BY-SA 3.0
2015-09-13T17:57:52.807Z
apparently yuval is too modest to cite his own [work](https://speedupblogger.wordpress.com/2014/07/20/limits-on-the-recent-progress-on-matrix-multiplication-algorithms-guest-post-by-yuval-filmus/) on matrix multiplication. if anyone posts any comments on that post (zero currently), it could start a cyber collabortion right there. demonstrating that the challenge is not the technical infrastructure at all, which has been there for years, but (1) lack of experts, and (2) experts in the area applying themselves in other typical/ conventional ways (eg writing papers, attending conferences etc)
vzn
CC BY-SA 3.0
2015-09-18T02:08:55.510Z
2.3... is the exponent ?
Suresh Venkat
CC BY-SA 3.0
2015-09-13T04:30:46.987Z
2015-09-13T04:30:46.987Z
Sariel Har-Peled
<p>In Polymath projects a large group work on an open problem. </p>

<p>What kind of problems seem to work best in this framework?<br>
Are there any good candidates for a polymath project in theoretical computer science?<br>
Are there any obstacles that make Polymath projects less likely to succeed in theoretical computer science in comparison to other areas of mathematics?</p>

CC BY-SA 3.0
2015-09-13T05:16:42.860Z
Polymath4 already focused on a TCS question: designing a faster deterministic algorithm to find a prime in a given range. Polymath3 focused on the polynomial Hirsch conjecture, which is closely related to analysis of simplex algorithms. My point is, TCS is math, and a TCS polymath project need not be any different from any other polymath project.
Sasho Nikolov
CC BY-SA 3.0
2015-09-13T17:49:33.223Z
***great idea!*** but doesnt fit too well in stackexchange fmt. however [chat rooms](https://vzn1.wordpress.com/chat/) can be a natural/ effective place to organize & have already been used for some of these purposes. there has been some occasional TCS group work eg on the [deolalikar proof review](https://vzn1.wordpress.com/volunteer/) etc. a major challenge with online/ open science seem to be _incentives_ as identified by Nielsen in his excellent book [Networked science](http://www.amazon.com/Reinventing-Discovery-The-Networked-Science/dp/0691148902/)
vzn
CC BY-SA 3.0
2015-09-13T23:05:49.007Z
I think the HoTT project with its dedicated blog, several GitHub repositories, face-to-face meetings (and public founding) is a more promising model for collaborative theoretical computer science research than the "superstar math prodigy powered" Polymath projects.
Thomas Klimpel
CC BY-SA 3.0
2015-09-13T23:07:31.327Z
@ThomasKlimpel instead of doing HOTT why not just proof theory in general.
Joshua Herman
CC BY-SA 3.0
2015-09-14T09:17:36.290Z
@ThomasKlimpel Given that Hott originated from a Fields medalist, and that the Hott book was written at, and financed by the IAS, it's hard to see how Hott isn't also "superstar math prodigy powered".
Martin Berger
CC BY-SA 3.0
2015-09-15T03:08:48.393Z
@ThomasKlimpel I am sorry for being harsh but I think this is a ridiculous comment. For one thing, you are comparing an effort that took considerable financing and non-trivial organizational work to a model that can be set up immediately by anyone and essentially has zero cost. For another, the dismissiveness of "superstar math prodigies" is unnecessary and misguided. Gowers, Tao, and Kalai are accomplished mathematicians who are active online. Who else to lead such a thing? (And as Martin pointed out, Voevodsky is a Fields medalist, too.)
Sasho Nikolov
CC BY-SA 3.0
2015-09-15T22:17:04.133Z
@SashoNikolov If Timothy Gowers or Terence Tao will take care of summarizing and publishing the results, then a blog alone can be sufficient, especially if we are talking about breakthrough results. But for more standard achievements (complexity of matrix multiplication, for example), the explanations and presentations of results constitute a nontrivial amount of work, and a GitHub repository helps sharing that work. Face-to-face meetings can boost motivation. (And founding should not be neglected either, for example to cover the costs of face-to-face meetings.)
Thomas Klimpel
CC BY-SA 3.0
2015-09-16T11:18:26.480Z
@Kaveh How do you think I should fix this question then? I already got an answer I wanted.
Joshua Herman
CC BY-SA 3.0
2015-09-16T16:55:11.193Z
I dont see why  you need to fix the question, and I think it will be very hard to do so. The question is fundamentally opinion based (no hope for a factual answer). You got the answer you wanted, let it go.
Sasho Nikolov
<soft-question><open-problem><research-practice>
Massive online collaboration for solving open problem in theoretical computer science
Joshua Herman
# Massive online collaboration for solving open problem in theoretical computer science

(Asked by: username_0 on 2015-09-13)

In Polymath projects a large group work on an open problem.

What kind of problems seem to work best in this framework?  
Are there any good candidates for a polymath project in theoretical computer science?  
Are there any obstacles that make Polymath projects less likely to succeed in theoretical computer science in comparison to other areas of mathematics?

**Tags:** soft-question, open-problem, research-practice

> **Comments:**
> **username_1**: Polymath4 already focused on a TCS question: designing a faster deterministic algorithm to find a prime in a given range. Polymath3 focused on the polynomial Hirsch conjecture, which is closely related to analysis of simplex algorithms. My point is, TCS is math, and a TCS polymath project need not be any different from any other polymath project.  
> **username_2**: ***great idea!*** but doesnt fit too well in stackexchange fmt. however [chat rooms](https://username_21.wordpress.com/chat/) can be a natural/ effective place to organize & have already been used for some of these purposes. there has been some occasional TCS group work eg on the [deolalikar proof review](https://username_21.wordpress.com/volunteer/) etc. a major challenge with online/ open science seem to be _incentives_ as identified by Nielsen in his excellent book [Networked science](http://www.amazon.com/Reinventing-Discovery-The-Networked-Science/dp/0691148902/)  
> **username_3**: I think the HoTT project with its dedicated blog, several GitHub repositories, face-to-face meetings (and public founding) is a more promising model for collaborative theoretical computer science research than the "superstar math prodigy powered" Polymath projects.  
> **username_0**: @ThomasKlimpel instead of doing HOTT why not just proof theory in general.  
> **username_4**: @ThomasKlimpel Given that Hott originated from a Fields medalist, and that the Hott book was written at, and financed by the IAS, it's hard to see how Hott isn't also "superstar math prodigy powered".  
> **username_1**: @ThomasKlimpel I am sorry for being harsh but I think this is a ridiculous comment. For one thing, you are comparing an effort that took considerable financing and non-trivial organizational work to a model that can be set up immediately by anyone and essentially has zero cost. For another, the dismissiveness of "superstar math prodigies" is unnecessary and misguided. Gowers, Tao, and Kalai are accomplished mathematicians who are active online. Who else to lead such a thing? (And as Martin pointed out, Voevodsky is a Fields medalist, too.)  
> **username_3**: @SashoNikolov If Timothy Gowers or Terence Tao will take care of summarizing and publishing the results, then a blog alone can be sufficient, especially if we are talking about breakthrough results. But for more standard achievements (complexity of matrix multiplication, for example), the explanations and presentations of results constitute a nontrivial amount of work, and a GitHub repository helps sharing that work. Face-to-face meetings can boost motivation. (And founding should not be neglected either, for example to cover the costs of face-to-face meetings.)  
> **username_0**: @Kaveh How do you think I should fix this question then? I already got an answer I wanted.  
> **username_1**: I dont see why  you need to fix the question, and I think it will be very hard to do so. The question is fundamentally opinion based (no hope for a factual answer). You got the answer you wanted, let it go.  

---

## 2 answers

### Answer by username_5 on 2015-09-13. Score: 10 | Accepted answer

Polymath projects seems to succeed when a breakthrough happens, and one is trying to optimize the result of the breakthrough or come up with simpler or better proof. See <https://en.wikipedia.org/wiki/Polymath_Project#Problems_solved>. As such, you would have to pick a problem of this nature in CS. The only one that comes immediately to mind is improving the constant in matrix multiplication <https://en.wikipedia.org/wiki/Matrix_multiplication#Algorithms_for_efficient_matrix_multiplication>, which is currently at 2.4... But frankly, I am not sure enough people care about it enough to work on it...

Questions for which I would expect polymath to fail miserably: P=NP, online optimality, UGC, etc.

> **Comments:**
> **username_6**: Well, some time ago, there was a kind of polymath project to analyze an announced proof of P = NP, which turned out to be incorrect...  
> **username_7**: Matrix multiplication has become popular recently...  
> **username_8**: Finding cleaner versions of proofs of the PCP theorems might be a useful endeavor they could do.  
> **username_9**: @J.-E.Pin: so the project was a success!  
> **username_2**: apparently yuval is too modest to cite his own [work](https://speedupblogger.wordpress.com/2014/07/20/limits-on-the-recent-progress-on-matrix-multiplication-algorithms-guest-post-by-yuval-filmus/) on matrix multiplication. if anyone posts any comments on that post (zero currently), it could start a cyber collabortion right there. demonstrating that the challenge is not the technical infrastructure at all, which has been there for years, but (1) lack of experts, and (2) experts in the area applying themselves in other typical/ conventional ways (eg writing papers, attending conferences etc)  
> **username_10**: 2.3... is the exponent ?  

---

### Answer by username_3 on 2015-09-13. Score: 2

If a massively online collaboration is set up, then it should try to focus on problems with a reasonable chance of success. The three classical construction problems of antiquity are known as "squaring the circle", "trisecting an angle", and "doubling a cube". Modern mathematics resolved all three, but much more important was the earlier Descartes revolution, which enabled mathematics to free itself from the mental prison of compass and straightedge constructions. Notice that the Greeks used compass and straightedge as a practical computational device, as witnessed by the [efficient epicycle approximation scheme](https://en.wikipedia.org/wiki/Deferent_and_epicycle) for celestial mechanics computations.

Many conjectures and generalizations of solved conjectures from graph theory should be amenable to solutions by collaboration. However, typical experience with collaborations suggest that teams of 2-4 members are far more effective than significantly larger teams. An example of a very successful team in this area are N. Robertson, P.D. Seymour and R. Thomas, which attacked problems like the strong perfect graph conjecture, generalizations of the four color theorem, and graph minor related conjectures. The elapsed time between announcement of new results and their actual publication has been notoriously long, also for other teams of researchers in the same area, indicating that pure workload volume here is slowing things down, so that collaboration (which already happens) could be beneficial to speed things up. (I'm still curious when some of the announced generalizations of graph minor related results for directed graphs will be published, and whether the people who will finally publish them will be the ones which initially announced the results.)

I currently try to understand the role of completeness of intuitionistic logic in practical applications of computer assisted proof refutation. But if you really plan to do proofs by massively online collaborations, then having a solid computer assisted proof refutation system in place might really be important. After all, if you don't know your collaborators sufficiently well, how will you be able to judge whether you can trust their contributions, without wasting a significant amount of time checking everything they did? (I have the impression that mathematicians are more used to proof refutation and enjoy its positive sides like direct personal feedback, while computer scientists show less routine with this sort of feedback.) Anyway, establishing that proof refutation is a natural part of collaboration when tackling difficult problems seems like a good idea to me.


---

