Two groups of topics will be studied. The first group deals with approximation algorithms. Since for many important problems exact solution cannot be determined in reasonable time, one needs to provide as good solutions as possible, given the available computational resources. The investigators will concentrate on two paradigms: local search heuristics and relaxations of integer linear programs. The design and analysis of heuristics for combinatorial optimization problems is proposed. Problems of relevance to Numerical Analysis and Circuit Design are emphasized. The second group deals with reliable computations of neural networks. The goal of this research is to determine the adequacy of neural networks as a computational abstraction of the brain. The starting point of this study is the observation that the brain computes reliably in spite of unreliable individual components. Existing methods for constructing fault- tolerant bounded degree networks will be used in combination with new techniques to handle unbounded fan-in processing elements.
