Event
Advanced Networks Colloquium: Michael Chertkov, "Physics of Algorithms"
Friday, September 16, 2011
11:00 a.m.
1146 A.V. Williams Building
Kimberly Edwards
301 405 6579
kedwards@umd.edu
Advanced Networks Colloquium
Physics of Algorithms: Belief Propagation and Beyond
Michael Chertkov
Los Alamos National Laboratory
| video |
Host
John Baras
Abstract
There has been an explosion of interest in the past decade to statistical problems related to computer science and information processing, such as new decoding paradigms for high-volume communication and storage, problems in search and counting through a huge set of combinatorial constraints, etc.
Novel ideas in analysis of complexity and development of approximate but systematically improvable algorithms are required for the hard statistical problems. Since the central task of statistical physics is to describe how complex behavior emerges from interaction of large number of basic elements, its tools and concepts are proven valuable in the emerging disciplines. Belief Propagation or Bethe-Peierls (BP) theory and associated algorithmic tools offer one of the most interesting recent examples of a successful synergy between statistical physics and information sciences.
I will review foundations of the BP technique used for approximate but efficient inference and counting over loopy networks and graphs. BP also allows theoretical guarantees via the so-called Loop Calculus establishing direct relation between the approximate and exact formulas for counting. To illustrate theoretical and practical power of the technique we discuss BP-based exact relations, approximations and bounds derived recently for permanents of non-negative matrices.
Biography
Dr. Chertkov's areas of interest include statistical and mathematical physics applied to information theory, computer science, hydrodynamics, optics, communication and infrastructure networks. Dr. Chertkov received his Ph.D. in physics from the Weizmann Institute of Science in 1996, and his M.Sc. in physics from Novosibirsk State University in 1990.
After his Ph.D., Dr. Chertkov spent three years at Princeton University as a R.H. Dicke Fellow in the Department of Physics.
He joined Los Alamos National Lab in 1999, initially as a J.R. Oppenheimer Fellow in the Theoretical Division. He is now a technical staff member in the same division. Dr. Chertkov has published more than 100 papers in these research areas and is currently leading Physics of Algorithms and Optimization and Control Theory for Smart Grids projects at LANL.
