11
$\begingroup$

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?

Improve this question
$\endgroup$
9
  • 9
    $\begingroup$ 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. $\endgroup$
    – Sasho Nikolov
    Commented Sep 13, 2015 at 5:16
  • 1
    $\begingroup$ great idea! but doesnt fit too well in stackexchange fmt. however chat rooms 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 etc. a major challenge with online/ open science seem to be incentives as identified by Nielsen in his excellent book Networked science $\endgroup$
    – vzn
    Commented Sep 13, 2015 at 17:49
  • 2
    $\begingroup$ 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. $\endgroup$
    – Thomas Klimpel
    Commented Sep 13, 2015 at 23:05
  • 6
    $\begingroup$ @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". $\endgroup$
    – Martin Berger
    Commented Sep 14, 2015 at 9:17
  • 2
    $\begingroup$ @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.) $\endgroup$
    – Sasho Nikolov
    Commented Sep 15, 2015 at 3:08

2 Answers 2

Reset to default
10
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • 5
    $\begingroup$ 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... $\endgroup$
    – J.-E. Pin
    Commented Sep 13, 2015 at 8:16
  • 3
    $\begingroup$ Matrix multiplication has become popular recently... $\endgroup$
    – Yuval Filmus
    Commented Sep 13, 2015 at 12:52
  • 2
    $\begingroup$ Finding cleaner versions of proofs of the PCP theorems might be a useful endeavor they could do. $\endgroup$
    – Phylliida
    Commented Sep 13, 2015 at 14:48
  • 4
    $\begingroup$ @J.-E.Pin: so the project was a success! $\endgroup$
    – cody
    Commented Sep 13, 2015 at 15:38
  • 5
    $\begingroup$ apparently yuval is too modest to cite his own work 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) $\endgroup$
    – vzn
    Commented Sep 13, 2015 at 17:57
2
$\begingroup$

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 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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.