Special issue of DAM

[Marco Protasi]

                                CALL FOR PAPERS

                                Special Issue on
                        Discrete vs analog computation:
               Links between computational complexity and local minima

                        Discrete Applied Mathematics (Elsevier)
                            M. Gori and  M. Protasi (Eds)
================================================================================
In the last few years, the resurgence of interest in fields like artificial
neural networks has been raising some very intriguing theoretical questions
on the links between discrete and analog computation. Basically, most
analog schemes massively adopted in machine learning and combinatorial
optimization rely on function optimization. In this setting, the inherent
complexity of the problem at hand seems to appear in terms of local minima
and, more generally, in terms of  numerical problems of the chosen
optimization algorithm.
While most practitioners use to accept without reluctance the flavor of
suspiciousness which arises from function optimization (in which one has
often no guarantee to reach the global optimum), most theoreticians are
instead quite skeptical. On the other hand, the success of analog
computation  for either learning or problem solving is often related to the
problem at hand and, therefore, one can expect an excellent behavior for a
class of problems, while one can raise serious suspects about the solution
of others. To the best of our knowledge, this intuitive idea has not been
satisfactorily explained from a theoretical point of view. Basically, there
is neither theory to support naturally the intuitive concept of
suspiciousness which arises from approaches based on continuous
optimization, nor theory to relate this concept to computational
complexity, traditionally developed in the discrete setting.
The study of the complexity of algorithms has been essentially performed on
discrete structures and an impressive theory has been developed in the last
two decades. On the other hand optimization theory has a twofold face:
discrete optimization and continuous optimization. Actually there are some
important approaches of the computational complexity theory that were
proposed for the continuous cases, for instance, the information
based-complexity (Traub) and real Turing Machines (Blum-Shub-Smale). These
approaches can be fruitfully applied to problems arising in continuous
optimization but, generally speaking, the formal study of the efficiency
of algorithms and problems has received much more attention in the discrete
environment, where the theory can be easily used and error and precision
problems are not present. The face that the complexity assumes in the
analog setting is not very clear and, moreover, the links with traditional
computational complexity for the discrete setting still need to be
explored.
The aim of the special issue is mainly to study the links between discrete
and continuous versions of the same problem. Since, until now, these links
have been rarely explored, the special issue is supposed to stimulate
different points of view; people working on discrete optimization are in
fact likely not to be expert on the continuous side and vice-versa.
Prospecting authors are theoretical computer scientists working in the
field of algorithms, operations research people, researchers working in
neural network, and researchers in nonlinear system theory.
Possible topics for papers submitted to the special issue include, but are
not limited to:

- Links between the complexity of algorithms in the continuous and
discrete settings

- Approximate solutions of problems in the continuous and discrete
settings

- Analog computing and dynamical systems

- Combinatorial optimization by neural networks: Complexity issues

- Learning in artificial neural networks: Local minima and complexity
issues

All submissions will undergo thorough refereeing process, according to the
usual standards of the journal.
Prospective authors should submit six copies of a manuscript to one of the
Guest Editors by April10, 1998.
================================================================================
Marco Gori
Dipartimento di Ingegneria dell'Informazione
Universita' di Siena
Via Roma, 56
53100 Siena (Italy)
Voice: +39 (577) 26.36.10
Fax:   +39 (577) 26.36.02
E-mail: marco at ing.unisi.it
WWW: http://www-dsi.ing.unifi.it/neural/~marco

Marco Protasi
Dipartimento di Matematica
Universita' di Roma "Tor Vergata"
Via della Ricerca Scientifica
00133 Roma (Italy)
Voice: +39 (6) 72.59.46.78
Fax:   +39 (6) 72.59.46.99 or 72.59.42.95
E-mail: protasi at mat.utovrm.it
WWW:http://www.mat.utovrm.it

-----------------------------------------------------------------------------
Marco Protasi                        Tel: +39-6-72594678
Dipartimento di Matematica           Fax: +39-6-72594699
Universita' di Roma "Tor Vergata"    e-mail: protasi at mat.utovrm.it
Via della Ricerca Scientifica                protasi at utovrm.it
00133 Roma - Italy
----------------------------------------------------------------------------