This award was made on a 'small' category proposal submitted in response to the ITR solicitation, NSF-02-168. The Divisions of Materials Research and Mathematics jointly fund this grant. It supports the application of the extremal optimization heuristic, developed by the PI, to hard optimization problems, ranging from the physics of disordered materials to combinatorial problems in computer science and artificial intelligence. The PI aims to (1) measure ground-state energies, entropies, and overlaps for spin glasses on networks and lattices, and (2) elucidate the order parameter at the SAT/UNSAT transition in combinatorial optimization problems. Extremal optimization has produced many results for lattice spin-glasses, and agrees with recent theoretical predictions on finite-connectivity Bethe-lattices to within 0.1%. A short-term objective is to produce numerical results for spin-glass systems to test the cutting-edge predictions of replica symmetry breaking on low-connectivity systems. Central to the research is the investigation of hybrid methods, derived from experimental and theoretical advances, which enable the study of much larger and more realistic systems. Comparative studies will educate practitioners about the potential of this approach to optimization with the hope of inspiring further applications. This project will introduce students to computational techniques and a spectrum of simulation methods in the process of experimenting with optimization problems on networks relevant for many physical and cross-disciplinary problems. Students will interact at the interface between computer science and physics, and as part of their education will conduct student research at Los Alamos National Laboratory's Computer and Computational Sciences division under an existing collaboration. Assessing the potential of this novel method in comparison with other optimization methods will afford undergraduate students in particular with a comprehensive learning experience. %%% This award was made on a 'small' category proposal submitted in response to the ITR solicitation, NSF-02-168. The Divisions of Materials Research and Mathematics jointly fund this grant. It supports research and education in the statistical mechanics of disordered systems. The PI will continue work on an optimization algorithm he developed and apply it to problems ranging from the physics of disordered materials to combinatorial problems in computer science and artificial intelligence. Successful algorithmic strategies will be applied to realistic systems, for instance, to help settle long-standing questions about three dimensional spin glasses. This project will introduce students to computational techniques and a spectrum of simulation methods in the process of experimenting with optimization problems on networks relevant for many physical and cross-disciplinary problems. Students will interact at the interface between computer science and physics, and as part of their education will conduct student research at Los Alamos National Laboratory's Computer and Computational Sciences division under an existing collaboration. Assessing the potential of this novel method in comparison with other optimization methods will afford undergraduate students in particular with a comprehensive learning experience. ***
