CG models of computation?
h.j.gudmundsson at tue.nl
Fri Dec 5 15:16:29 PST 2003
Dear Colleagues, I have a question about which models
of computation that are accepted in the computational
In many of the papers I have co-authored we have
strived to use the algebraic decision tree model of
computation (sometimes extended with indirect
addressing), but sometimes also using the real RAM.
Recently, I read an excellent paper where the authors
add the power of the floor function to the standard
model of computation. The running time of their
algorithm is almost linear and beats the lower bound
in the comparison model.
Somewhat puzzled and skeptical I asked my colleagues
about their opinion on this topic, only to find out that
this model was, according to my colleagues, unofficially
accepted. One of my colleagues even claimed that it was
so widely accepted that it is not even necessary to
explicitly point out in a paper if the floor function
is used or not. Amazed about this information I went
back to my office and looked at a paper I'm currently
working on. Adding the floor function would trivially
improve the running time of the algorithm from
O((m+n) log n) to O(m+n log n), maybe even more. My
question is, what is "unofficially" allowed? One could
claim that the use of floor function should be accepted
since it is used in practice and very fast. How about
bit manipulation? But then we should measure the
complexity in the number of input bits, right?
Anyway, I would be very happy if anyone could help remove
my obvious ignorance on this topic.
The compgeom mailing lists: see
or send mail to compgeom-request at research.bell-labs.com with the line:
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.
More information about the Compgeom-announce