^ Parametric Models for Large-Scale Agent Systems G. A. Agha,* N. Jamali, P. Thati, R. Ziaei Defense Advanced Research Projects Agency, F30602-00-2-0586
A goal of this research is to develop mathematical models to support the analysis and modeling of complex, large-scale agent systems. Instead of simple nondeterminism, the new theory will represent behavior stochastically. Moreover, instead of the current approach of using input-output behavior of individual agents, it will allow the behavior to be parametric in terms of variables that represent aggregated behavior of large numbers of agents. The approach is to use stochastic methods. The operational model uses probabilistic transitions over an abstract representation of the current state of the system. The use of statistical techniques on this model for aggregating behaviors opens up the possibility of studying conditions under which either a stable equilibrium or chaotic behavior may occur. Another goal is to develop a radically different logical framework for expressing properties of large-scale agent systems. The framework is inspired by Quantum Logics, which allow the expression of testable properties. This is in contrast to the usual algebraic approach which assumes that every sentence (whether testable or not) can be assigned a truth value. Specifically, this research will enable macroscopic properties to be expressed without implying assertions about how they arise.
^ Learning Theory D. Roth* National Science Foundation, IIS-9801638; National Science Foundation, CAREER Award, IIS-9984168
This is a study of several questions in learning theory that pertain to the problem of learning a number of concepts from common data. The study encompasses interactions and constraints imposed on outcomes. The main direction is the development of a theoretical framework for learning coherent concepts. This is a study of learning situations in which learning does not occur in isolation. Rather, the input is observed and processed by multiple learners. The goal is to understand what ways learning becomes easier and more robust in these situations.
^ Eigenvalue Problem for Graph Theory S. H. Teng* Alfred P. Sloan Research Fellowship
The graph eigenvalues and eigenvectors have been used in optimization problems that are important to information organization and parallel processing. For example, the Fiedler vector (the eigenvector of the second-smallest eigenvalue of the Laplacian matrix) can be used to find good partition of a graph, an important component of many circuit design and numerical algorithms. This method has been demonstrated by experiment to work extremely well. However, the quality of the partition has eluded precise analysis. Goals of this project are to find a mathematical explanation for why this method works in practice and then to determine how to properly use the spectral structure of a graph to design provably good optimization algorithms.
