From - Tue Nov 18 08:53:49 2014
X-Mozilla-Status: 1001
X-Mozilla-Status2: 00800000
X-Mozilla-Keys:
Message-ID: <546AFB0A.1020501@gmail.com>
Date: Tue, 18 Nov 2014 08:53:46 +0100
From: Francis Sergeraert
Reply-To: Francis.Sergeraert@gmail.com
User-Agent: Mozilla/5.0 (Windows NT 6.1; rv:5.0) Gecko/20110624 Thunderbird/5.0
MIME-Version: 1.0
To: "Leonard J. Schulman"
CC: Jiri Matousek ,
Lukas Vokrinek ,
Martin Cadek , Uli Wagner ,
Marek Krcal
Subject: Falty paper in SIAM JC ?
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Francis Sergeraert => Leonard J. Shulman.
==================================================
I learn the Arxiv paper:
http://arxiv.org/abs/1211.3093
is accepted for publication in the SIAM Journal of Computing.
This paper is faulty, more precisely the very kernel of this paper
is faulty. There is an essential gap in the authors' "solution" to
construct the "algorithm" announced in Theorem 1.1.
This paper is heavily based on my personal work about "Effective
Homology", a domain created by myself from scratch about 30 years ago,
to make computable the spectral sequences of Algebraic Topology,
leading to the Kenzo computer program (1998), which remains 16 years
later the only example of this sort.
The main result of the Arxiv paper was stated by myself many years
ago, and the authors of this paper, knowing my statement, solicited me
for a common work about a tentative paper about this subject.
Unfortunately these colleagues have a superficial knowledge of
computer science, and they did not make any sensible effort to
understand the unavoidable intensive use of functional programming in
the algorithms using the Effective Homology methods.
So that it was not possible to make our "common" work converge to a
correct paper. It's a pity: these men are excellent topologists. In
spite of my severe warnings about their faults in programming
technology, they finally uploaded their paper on Arxiv. I of course
refused to cosign this paper, as it was proposed: Is it correct to
cosign a paper which you would reject as referee?
If the paper does appear in Siam JC, I'll explain in details on my
web site why the paper is faulty. Not difficult.
In short, the parameter set \mathcal{I}, constantly used in the
paper, leads to the following amusing situation. The authors prove
that for every i \in \mathcal{I} they can write down an algorithm A(i)
computing the desired homotopy group. But this algorithm depends on
i. For a new value j \neq i, you have to write down another algorithm
A(j). The actual result of the paper is only a uniform polynomial
complexity of all the A(i)'s, but the *unique* algorithm claimed in
Theorem 1.1 is not obtained.
[In other words, the authors sell a computer able to compute the
product 3x4. If you want later to compute 5x6, you must buy another
computer.]
The solution is simple. To obtain the unique desired algorithm,
there remains to study the algorithm i -> A(i). But this requires a
high level of functional programming, when an algorithm must construct
an algorithm, a point totally omitted in the paper, in particular
making quite different the study of complexity, the main subject of
the paper. Making also much simpler the understanding of the final
algorithm, avoiding all the clumsy technicalities making this paper
absolutely ugly.
The algorithm i -> A(i) has been written down by myself and my
collaborators in 1997-8 and successfully used since. I know it a
litlle.
I feel sorry for the unhappy referee receiving this paper. I wonder
what intellectual process has been able to validate this faulty paper.
A situation which certainly will interest my friends of the
so-called Univalent Foundation. Read for example in:
https://www.ias.edu/sites/default/files/pdfs/publications/letter-2014-summer.pdf
the nice paper by Voevodsky (p.8).
Thanks for your work.
Bien cordialement.