Famous computer science results which correctness is uncertain?

Question

I am asking the following: which of the 'famous' computer science results have been thoroughly checked, and for which ones is the correctness still uncertain?

I understand that some proofs are hard to check due to their length, intricacy or technicality, and in some cases an elementary proof was found after the first published one (such as Dinur's proof of the PCP theorem). Apparently, some of the longest proofs in CS are the SPGT by Chudnovsky et al., and the Graph Minors series of papers by Robertson-Seymour, and I understand that there is an ongoing effort to simplify the latter.

The same question applies to mathematics where there are some very long proofs, such as the CFSG, which correctness is debated by experts: see List of long proofs.

I'm not sure I understand the question. Do you want to know about the status of the theorems you mentioned, like the PCP theorem, graph minors theorem, SPGT and CFSG, or do you want examples of theorems whose correctness is uncertain? And what is your threshold for uncertainty? For example, are the graph minors theorem and the classification of finite simple groups certain in your opinion or is their correctness debated? — Robin Kothari, May 23 '14 at 23:38
I haven't seen or heard anything like what you describe. Please give one or two examples of major published results in TCS whose correctness is debated among experts in the topic (and give the names of those who debate them with references). — Kaveh, May 24 '14 at 10:06
My advisor doubts the proof of the 4 color theorem because of the use of computer verification. I don't know if this doubt is shared by some graph theory experts. — Lamine, May 24 '14 at 14:04
this a sort of meta-topic of CS but rarely discussed directly that does relate to eg proof verification topics and also it is known that some proofs are later found to have glitches and/or revised. its similar to the topic of defects in software. some are minor, some are major. even knuth (with his implementation/practitioner focus) recently said in interview he doubts or does not trust some large complex algorithms devised for problems, eg many are never implemented and/or tested. see eg MO widely accepted proofs later found wrong — vzn, May 24 '14 at 14:27
see also powerful algorithms too hard to implement, how can they be right — vzn, May 24 '14 at 14:33
this is a recent case of a revision/correction of the Vazirani-Micali algorithm for graph matching. — vzn, May 24 '14 at 14:47
another interesting case study is this controversial paper in Notices AMS by Koblitz uneasy relationship between math/crypto but was subj to much later pushback by top researchers. — vzn, May 24 '14 at 14:50

Famous computer science results which correctness is uncertain?

0 Answers0