Lab Home | Phone | Search
	Center for Nonlinear Studies
	Home  ▶ People   Current   Executive Committee   Postdocs   Visitors   Students   Research   Publications  ▶ Conferences   Workshops   Sponsorship  ▶ Talks   Seminars   Postdoc Seminars Archive   Quantum Lunch   Quantum Lunch Archive   P/T Colloquia   Archive   Ulam Scholar     Postdoc Nominations  ▶ Student Requests   Student Program  ▶ Visitor Requests   Description   Past Visitors  ▶ Services   General     History of CNLS     Maps, Directions   CNLS Office   T-Division   LANL				Tuesday, August 12, 200811:00 AM - 12:00 PMCNLS Conference Room (TA-3, Bldg 1690) Seminar Physics of Algorithms Talk: Front Propagation with Rejuvenation in Flipping Processes P. L. KrapivskyBoston University I will describe a directed flipping process that underlies the performance of the random edge simplex algorithm. This stochastic process takes place on a one-dimensional lattice whose sites may be either occupied or vacant; an occupied site becomes vacant at a constant rate and simultaneously it causes all sites to the right to change their state. The position of the left-most occupied site defines a front that propagates at a nontrivial velocity. I will show that the front involves a depletion zone with an excess of vacant sites; the total excess increases logarithmically with the distance from the front. Interestingly, the front exhibits rejuvenation --- young fronts are vigorous but old fronts are sluggish. We treat these phenomena using a quasi-static approximation, direct solutions of small systems, and numerical simulations. Host: T-13