Main Page

From Werner KRAUTH

Jump to: navigation, search
50px
Werner Krauth
Laboratoire de Physique
École normale supérieure
24 rue Lhomond
75005 Paris
France
werner.krauth@ens.fr


CNRS Research Director - Theoretical Physics (Directeur de recherche CNRS - classe exceptionnelle).

Visiting Professor in Physics - University of Oxford (2023 - 26).

Keeley Visiting Fellow - Wadham College (Oxford, UK) (October 2023 - March 2024).

Distinguished Visiting Professor, Simons Center for Computational Physical Chemistry, New York University, New York (NY, USA) - April, May 2024

From January to June 2018, I was the 2018 Martin-Gutzwiller fellow at the Max-Planck-Institute for the Physics of Complex Systems in Dresden (Germany).

In 2018, I was a recipient of the Humboldt research award (Alexander von Humboldt Foundation).


Contents

[edit]

Oxford Lectures 2025

Since 2023, I have enjoyed myself tremendously as Visiting Professor in Physics at the University of Oxford where, again this year, I spend several months. I'm heavily engaged in research within an incredibly active and collaborative environment. I also give a set of public lectures on Algorithms and Computations in theoretical physics (see the announcement for a syllabus). Lecture notes are made available step by step, or rather "with the flow of the water", as we say in French.

I am very grateful to the Department and the University to have arranged for me to lecture on one of my favorite subjects, and also to have made these lectures "public". Anyone can attend: Students at the Oxford Physics department (or not), postdocs (or not), young and old, from all walks of life. This year's lectures started on 21 January 2025, and they take place (or rather: they took place) every Tuesday afternoon at 2pm until 11 March 2025.

Public Lectures at University of Oxford, Tuesdays 2-4pm, 21 January through 11 March 2025
Public Lectures at University of Oxford, Tuesdays 2-4pm, 21 January through 11 March 2025


[edit]

Research over the ages

A (big) number of months ago, in 1988-89 (sic!), we were fascinated by a certain problem in the then new field of neural-networks research, namely the binary perceptron. The question was about the storage capacity of the now famous Hopfield model that, in a certain continuous case, had long been proven to be 2N, a result due to Thomas M. Cover (1965) and reinterpreted by E. Gardner (1987). We found this result depressing, as it stated that you needed (with, here on the website, a few shortcuts) N real numbers in order to store 2N single bits 0 and 1. This is like paying N gold coins (floats) to buy 2N copper dimes (single bits), clearly a bad deal. So we were very interested in finding out what would happen in the binary perceptron where, instead of N real numbers (the weights of one row of the Hopfield net) you had N bits (the weights of the binary Hopfield net). Together with Manfred Opper, who then visited ENS (where I did my thesis) from the University of Giessen in Germany, we wrote a computational paper, which quite clearly showed that the capacity was reduced from 2 (Cover's result) to a strange number very close to 0.82. At the time, we were quite proud of the two tricks which made our approach work namely, on the one hand, that we approximated the binary patterns with Gaussians patterns (which greatly improved the finite-size scaling) and, on the other hand, that we used the Gray code for a certain enumeration job. A few months later, again in 1989, with Marc Mézard, we conjectured, based on a one-step replica-symmetry-breaking calculation, that the critical capacity had to be equal to 0.833, a known function. In the conclusion of our 1989 paper, we speculated that our solution might well be exact

... conclusions of a 1989 paper...
... conclusions of a 1989 paper...


As I mentioned above, this was in 1989, before the bicentennial celebration of the French Revolution and many other events. For a fair number of years (months, I should say), the question of the critical capacity of the binary perceptron fascinated physicists, mathematicians and computer scientists, as it had first fascinated us. But it always appeared that "some more work" was "needed". Then finally, early in 2024, a keystone paper was written by Brice Huang, a MIT graduate student in Mathematics. He completed an enormous body of previous works, actually showed that our 0.833 had been correct all along. Brice was awarded the very prestigious Machtey award for best student paper in 2024. Bravo, congratulations, and celebrations, Brice --- the long wait was worth it and, indeed, "some more analytical work had been required..."!

[edit]

Milestone Research

A paper, on a first-order transition in two dimensions, by a collaboration on three continents (!) that I published a few years ago in Physical Review E together with M. Engel, J. A. Anderson, S. C. Glotzer, M. Isobe, and E. P. Bernard, was chosen as the milestone article for 2013 by the journal's editorial board. This 2013 paper confirmed research published in 2011, in Physical Review Letters, with Etienne Bernard, on what really goes on in two-dimensional melting. See here for the story of the paper.

[edit]

Video recordings of research talks

Hard-disk packings and two phase transitions of two-dimensional particle systems Invited talk at the workshop "Optimal Point Configurations on Manifolds", Erwin Schrödinger International Institute for Mathematics and Physics, University of Vienna, Vienna (Austria), 2021 (online talk)

Fast stochastic sampling with irreversible, totally asymmetric, Markov chains (Invited talk at Institute for Pure & Applied Mathematics, UCLA, Los Angeles (USA), 2017)

[edit]

Current research

Go to Past Research Notices

I am deeply interested in statistical and condensed-matter physics, often in connection to computation and algorithms. Current interests are in hard spheres, mainly the melting transition in two-dimensional disks and in two-dimensional melting, bosons (in collaboration with the experimental groups at ENS), and the theory of convergence and of coupling in Markov chains. Recent work in my research group has led to the redefinition of the dominant Markov-chain Monte Carlo paradigm, namely the Metropolis algorithm. This has already allowed us to propose powerful algorithms for particle systems, continuous spin models and long-range systems, and to obtain important physical results. Research on the beyond-Metropolis paradigm, together with applications in classical and quantum physics and its interfaces will likely be a focus of my research activity in the next few years.

[edit]

Fast, approximation-free molecular simulation of the SPC/Fw water model using non-reversible Markov chains

Many fields of computational science concern the sampling of configurations x from a distribution pi(x) which can often be written as pi(x) = exp[-beta E(x)] (that is, as a Boltzmann distribution). The configuration x then refers to the positions of thousands or millions of atoms with complicated, often long-ranged, interactions. Over the years, I have been interested in sampling methods which do not evaluate the energy E (or the difference of energies, or the gradient of E) in order to sample pi(x) = exp[-beta E(x)]. This is possible because of our use of the factorized Metropolis filter within the framework of the event-chain Monte Carlo algorithm. In July 2024, finally, the manuscript ["Fast, approximation-free molecular simulation ... "] on which I had worked together with Philipp Höllmer and A. C. Maggs was published in the Journal "Scientific Reports". It actually proves that one can simulate large water systems (in our case, the SPC/Fw water model) without any approximation. We generate millions of samples, but absolutely do not know what is the energy of our configurations.

The remarkable efficiency of our simulation method is rooted in three paradoxes. First, the Markov process is non-reversible (that is, effectively out-of-equilibrium), yet its steady state coincides with the equilibrium Boltzmann distribution. Second, the Boltzmann distribution exp(−βU) is sampled without any approximation and with great efficiency although the total potential U and its derivatives, the forces, are never evaluated. This sidesteps all the problems with limited-precision calculations of energies and forces. The third paradox is the bundling of O(N) independent decisions to interrupt the straight-line trajectory of the piecewise-deterministic Markov process into an expression that can be evaluated in constant time. The paper is openly accessible, and even all the computer code has been rendered open-source.

[edit]

Fast, approximation-free molecular simulation of the SPC/Fw water model using non-reversible Markov chains

[edit]

Lifted TASEP: a Bethe ansatz integrable paradigm for non-reversible Markov chains

In recent years, my colleagues and I have worked on a multitude of computational algorithms which improve on the classical methods. Specifically, we have worked on Monte Carlo algorithms based on non-reversible Markov chains. Such algorithms have had successes in applications but are generally difficult to analyze, resulting in a scarcity of exact results. In a recent manuscript Lifted TASEP: a Bethe ansatz integrable paradigm for non-reversible Markov chains, now published in Physical Review X with my colleague Fabian Essler (Oxford), we introduce the “lifted” TASEP (totally asymmetric simple exclusion process) as a paradigm for non-reversible Markov chains. Our model can be viewed as a second-generation lifting of the reversible Metropolis algorithm on a one-dimensional lattice and is exactly solvable by an unusual kind of coordinate Bethe ansatz. We establish the integrability of the model and present strong evidence that the lifting leads to relaxation on shorter timescales than in the KPZ (Kardar–Parisi–Zhang) universality class.

Here the "Popular Summary" that accompanied our paper:

Markov-chain Monte Carlo (MCMC) algorithms formulate the sampling problem for complex probability distributions as a simulation of fictitious physical systems in equilibrium, where all motion is diffusive and time reversible. But nonreversible algorithms can, in principle, sample distributions much more efficiently. In recent years, a class of “lifted” Markov chains has implemented this idea in practice, but the resulting algorithms are extremely difficult to analyze. In this work, we introduce an exactly solvable paradigm for nonreversible Markov chains.

Our paradigm, which we term the lifted totally asymmetric simple exclusion process (TASEP), describes a particular type of nonreversible dynamics for particles on a one-dimensional lattice. We show that this dynamics allows for polynomial speedups in particle number compared to the famous Metropolis MCMC algorithm. The lifted-TASEP dynamics is, in fact, faster than that of any other known class of models. To arrive at our conclusions, we combine exact methods from the theory of integrable models with extensive numerical simulations. In particular, we prove that the lifted TASEP is integrable and determine the scaling of its relaxation and mixing times with system size.

Our work opens the door to obtaining mathematically rigorous results for speedups of nonreversible MCMC algorithms, and more generally, of lifted Markov chains arising in interacting many-particle systems.



Continue with Past Research Notices

[edit]

Upcoming events

Here is the schedule of past events

[edit]

Text book

Cover of a book I wrote in 2006 Here is the book's website
Cover of a book I wrote in 2006 Here is the book's website


[edit]

Interview, Popular story, video conference

2012 interview at Ecole normale supérieure (in French)

CNRS special on our work on two-dimensional melting (June 2013) (in French) in Japanese (!)

2012 Conference on time's arrow (video, in French) in the framework of the Festival "acceleration" Sacre Doctoral school

Video presentation of the Massive Open Online course at ENS

Editorial "Coming home from a MOOC", about teaching a Massive Open Online Course (MOOC) (October 2014)

Grande conférence scientifique "Du déterminisme au stochastique : du hasard classique à l'aléatoire quantique", for the incoming science students at ENS (in French, September 2015)

"The largest Lecture Hall in the world", Article in "Physik Journal" on MOOCs, and in particular on my own MOOC (in German, March 2017)

[edit]

A picture book of algorithms

Direct-sampling algorithm for ideal bosons in a trap (see article with M. Holzmann). Adapted for interacting bosons, this algorithm was used in a variety of articles.
Direct-sampling algorithm for ideal bosons in a trap (see article with M. Holzmann). Adapted for interacting bosons, this algorithm was used in a variety of articles.
Event-chain Monte Carlo algorithm for hard spheres and related systems (see article with E. P. Bernard and D. B. Wilson, including Python implementation). This (fantastic) algorithm, about two orders of magnitude faster than local Monte Carlo, was used in our discovery of the first-order liquid-hexatic phase transition in hard disks. The method can be generalized to continuous potentials, and we used it to map out the phase diagrams of soft-disk systems. Look here for an implementation of the event-chain algorithm
Event-chain Monte Carlo algorithm for hard spheres and related systems (see article with E. P. Bernard and D. B. Wilson, including Python implementation). This (fantastic) algorithm, about two orders of magnitude faster than local Monte Carlo, was used in our discovery of the first-order liquid-hexatic phase transition in hard disks. The method can be generalized to continuous potentials, and we used it to map out the phase diagrams of soft-disk systems. Look here for an implementation of the event-chain algorithm


Exact diagonalization algorithm for Dynamical mean field theory (see article with M. Caffarel). This algorithm has been instrumental in our discovery of a first-order Mott transition in the Hubbard model in infinite dimensions. Much of our early work in the field is written up in our review with Georges, Kotliar, and Rozenberg
Exact diagonalization algorithm for Dynamical mean field theory (see article with M. Caffarel). This algorithm has been instrumental in our discovery of a first-order Mott transition in the Hubbard model in infinite dimensions. Much of our early work in the field is written up in our review with Georges, Kotliar, and Rozenberg
Rejection-free cluster algorithm for dimers (see article with R. Moessner). This algorithm was used for our discovery of a critical phase in three-dimensional dimer models (paper with Huse, Sondhi, and Moessner). Note that dimers flip about a symmetry axis between one valid configuration and another.
Rejection-free cluster algorithm for dimers (see article with R. Moessner). This algorithm was used for our discovery of a critical phase in three-dimensional dimer models (paper with Huse, Sondhi, and Moessner). Note that dimers flip about a symmetry axis between one valid configuration and another.
Alder and Wainwright's event-driven Molecular Dynamics algorithm (1957). (Animation by Maxim Berman).
Alder and Wainwright's event-driven Molecular Dynamics algorithm (1957). (Animation by Maxim Berman).


Retrieved from "http://www.lps.ens.fr/~krauth/index.php/Main_Page"
Personal tools