Edoardo Amaldi

Adjunct Assistant Professor

School of Operations Research and Industrial Engineering
Cornell Theory Center (Center for Theory and Simulation in Science and Engineering)

School of Operations Research and Cornell Theory Center
237 Rhodes Hall
Cornell University
Ithaca, NY 14853

Telephone: (607) 254-4606
Fax: (607) 255-9129
E-mail: amaldi@cs.cornell.edu

private address

Research Interests:

Algorithms and complexity theory in particular approximate solution of NP-hard optimization problems.
Discrete optimization current focus on combinatorial problems related to inconsistent linear systems with applications in several fields including image and signal processing.
Machine learning and artificial neural networks from an optimization perspective
Previous focus was on the hardness of learning problem, in particular of designing near-optimal linear classifiers. Currently we are exploring support vector machines.


In Spring 96 I taught Mathematical Programming II (OR&IE 631) with Oktay Gunluk.
I'm currently teaching Mathematical Programming I (OR&IE 630).


  1. Two constructive methods for designing compact feedforward networks of threshold units, with Bertrand Guenin, To appear in International Journal of Neural Systems.
  2. An efficient line detection algorithm based on a new combinatorial optimization formulation, with M. Mattavelli and V. Noel, Proceedings of the 1998 International Conference on Image Processing (ICIP98), Chicago IL, October 1998.
  3. On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems, with Viggo Kann, Theoretical Computer Science Vol. 209 (1998) 237-260. Preliminary version available as ECCC Technical Report 96-15.
  4. A perceptron-based approach to piecewise linear modeling with an application to time series, with Marco Mattavelli and Jean-Marc Vesin, Proceedings of International Conference on Artificial Neural Networks (ICANN'97), Lecture Notes in Computer Science, Vol. 1327, Springer-Verlag (1997) 547-552.
  5. A new approach to piecewise linear modeling of time series, with M. Mattavelli, J.-M. Vesin and R. Gruter, Proceedings of the Seventh IEEE Digital Signal Processing Workshop, Loen, Norway, IEEE Press, 1996.
  6. Estimating piecewise linear models using combinatorial optimization techniques, with M. Mattavelli, Proceedings of VIII European Signal Processing Conference (EUSIPCO'96), Trieste, Italy, 1996.
  7. The complexity and approximability of finding maximum feasible subsystems of linear relations, with Viggo Kann, Theoretical Computer Science, Vol. 147 (1995) 181-210.
  8. Using perceptron-like algorithms for the analysis and parameterization of object motion, with Marco Mattavelli, In F. Girosi et al. (editors), Neural Networks for Signal Processing V, Proceedings of the 1995 IEEE workshop, IEEE Press (1995) 303-312.
  9. From finding maximum feasible subsystems of linear systems to feedforward neural network design, Ph.D. dissertation No. 1282, Department of Mathematics, Swiss Federal Institute of Technology at Lausanne ( EPFL), October 1994.
  10. A review of combinatorial problems arising in feedforward neural networks, with Eddy Mayoraz and D. de Werra, Discrete Applied Mathematics, Vol. 52 (1994), 111-138.
  11. On the approximability of finding maximum feasible subsystems of linear systems, with Viggo Kann, Proceedings of STACS'94, Lecture Notes in Computer Science, Vol. 775 (1994), 521-532.
  12. On the complexity of training perceptrons, in T. Kohonen et al. (editors), Artificial Neural Networks, Vol. 1, Elsevier Science Publisher, North-Holland, Amsterdam (1991), 55-60.
  13. Computing optical flow across multiple scales: a coarse-to-fine approach, with Roberto Battiti and Christof Koch, International Journal of Computer Vision, Vol. 6 No. 2 (1991), 133-145.
  14. Stability-capacity diagram of a neural network with Ising bonds, with Stam Nicolis, Journal of Physics (France), (September 1989), 2333-2345.

Soon available on-line:

  1. A combinatorial optimization approach to extract piecewise linear structure in nonlinear data and an application to optical flow segmentation, with Marco Mattavelli.
  2. On the probabilistic and thermal perceptron algorithms, with Claude Diderich.
  3. The MIN PCS problem and piecewise linear model estimation, with Marco Mattavelli, extended abstract.
  4. Maximizing consistency versus minimizing disagreement and the relevance of non-learnability results.

Private address:

306 East State St Apt. 502
Ithaca, NY 14850

Telephone + Fax : (607) 273-7798