Department
 Home, News, Jobs

 People
 Faculty, Staff, TA's, Fellows

 Research
 Faculty Interests

 Graduate
 Program, Scholarships

 Undergraduate
 Advising, Scholarships

 Course Offerings
 Classes, Quarterly Schedule

 Colloquium
 Schedule, Archive

 Resources
 Links, Careers

Colloquium, Winter 2006

Day: Monday February 6 Time: 4:00pm Place: BH 428 Title:  Kauffman NK Model - A Stochastic Combinatorial Optimization Model for Complex Systems Speaker: Hemanshu Kaul Abstract:  Many scenarios in theoretical biology, physics, and management science can be modeled as discrete complex systems with several interacting components that can be in various states.  The aim is to maximize a performance measure involving contributions from each component.  This measure may depend on both the state of each component and on interactions between components. In 1987, Kauffman and Levin introduced a combinatorial optimization model for such systems, called the Kauffman NK model, where N is the number of components of the system and K measures the interaction between the components.  This was proposed to model the evolution of genomes in theoretical biology but has since been applied in other areas as listed above.   Previous research on the NK model has emphasized simulations and analysis of local optima.  Here we focus on rigorous results for global optima. We describe a computational setup using a stochastic network model, which leads to applicable strategies for computing bounds on global optima. Recent papers used tools from analysis and probability to obtain bounds on the expected value of the global optima for fixed K and large N. We present bounds when K grows with N, using ideas from graph theory, probabilistic combinatorics and order statistics. These general ideas are then applied to the analysis of the cases when underlying distributions are uniform and normal distributions.