CAMPUS THEORY / SCIENCE AT THE EDGE SEMINAR Friday, September 5, 2003 11:30 a.m. Room 1400 Biomedical and Physical Sciences Building (Refreshments served at 11:15 a.m.) Speaker: Stefan Boettcher Physics Department Emory University Topic: "Using Extremal Dynamics to Optimize Large Disordered Systems" Abstract: Extremal Optimization (EO), a new general-purpose heuristic for the approximation of hard combinatorial problems is introduced. EO is motivated by the far-from-equilibrium dynamics of extremally driven systems, such as the Bak-Sneppen model. In this co-evolutionary process, worst-adapted variables are forced to change, driving the system into a self-organized critical state featuring large fluctuations and frequent returns to highly adapted configurations. These features motivate this new scale-free local search heuristic. Early experiments on partitioning and coloring problems established EO as a state-of-the-art alternative. Recent work on spin glasses has yielded a quite accurate (<0.1%) confirmation of ground-breaking theoretical calculations for finite connected Bethe lattices. Paired with a new technique of tracing out most spins, we can now tackle finite-dimensional spin glasses with $10^4-10^5$ variables to address some long-standing questions about low-temperature excitations.