AF: Small: Approximate Counting, Stochastic Local Search and Nonlinear Dynamics

点击翻译按钮获取中文摘要

Theoretical Computer Science (TCS) is concerned with core questions in algorithms and complexity theory, and also with many questions in other scientific disciplines viewed through the so-called "computational lens." This refers to the study of many scientific phenomena that are fundamentally computational in nature and can therefore benefit from a TCS perspective. This project addresses both core topics and connections with other disciplines, notably statistical physics and population genetics. A unifying theme in the project is techniques for the analysis of random and physical processes arising in all of these fields. The project will engage as collaborators experts in fields such as complex analysis, applied probability and statistical physics to work on these interface areas. The project affords many opportunities for graduate student and postdoctoral training and ideas from this research will find their way into course curricula. The investigator also maintains a strong interest in undergraduate and K-12 teaching, the latter through his involvement with the Berkeley Math Circle.On a more technical level, the project contains three broad themes:1. Approximate counting: the development of approximation algorithms for counting problems, with special emphasis on the emerging technique of "geometry of polynomials" and its connections to the more classical techniques of Markov chain Monte Carlo and correlation decay. Applications include generating functions in combinatorics, partition functions in statistical physics, the computation of volumes, and the analysis of graphical models in machine learning.2. Stochastic local search algorithms: the study of a novel framework, arising from recent advances on the algorithmic Lovasz Local Lemma, for the design and analysis of stochastic local search algorithms, which search for combinatorial structures with desired properties by successively eliminating "flaws". The new framework is based on matrix norms and is inspired by linear time invariant analysis in control theory.3. Nonlinear dynamics: the study of computational aspects of two distinct, but related nonlinear dynamical systems: mass action kinetics and the "red-queen" dynamics. Mass action kinetics is a standard model for chemical reaction networks, and also captures other processes such as the Boltzmann equation in statistical physics, genetic algorithms and recombination in population genetics. The more speculative red-queen dynamics is a novel model for the evolution of multiple species under selection.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.