# Nicolas Macris

## Biography

I received a PhD degree in theoretical physics from EPFL and then pursued my scientific activity at the mathematics department of Rutgers University (NJ, USA). Then I joined the Faculty of Basic Science of EPFL, where I worked in the field of quantum statistical mechanics and mathematical aspects of the quantum Hall effect. Since 2005 I am with the Communication Theories Laboratory of the School of Communication and Computer Science and am currently working at the interface between the theory of error correcting codes, statistical mechanics and information theory. I have held visiting appointments and collaborated with the University College and the Institute of Advanced studies in Dublin, the Ecole Normale Superieure de Lyon, the Centre de Physique Theorique Luminy Marseille, Paris XI Orsay, the ETH Zuerich.

publications.pdf

cv.pdf

## Current and Past PhD students

Clement Luneau (present)

Eric Chun Lam Chan (present)

Mohamad Dia (present)

Rafah El-Khatib Analysis of Spatially Coupled Systems using the Potential Functional wth Applications to Coding Theory (2016)

Andrei Giurgiu Sparse Probabilistic Models: Phase Transitions and Solutions via Spatial Coupling (2015)

Hamed Hassani Polarization and Spatial Coupling: two techniques to boost performance (2013) - Information Theory Society 2014 Thomas Cover dissertation Award.

Marc Vuffray The cavity Method in Coding Theory (2013)

Shrinivas Kudekar Statistical Physics Methods for Sparse Graph Codes (2009).

Satish Korada Polar Codes for Channel and Source Coding (2009) - ABB 2010 Thesis Award.

Christian Ferrari Aspects of Two Dimensional Schrödinger operators: Quantum Hall Systems and Magnetic Stark Resonances (2003)

Claude Alain Piguet Long-range orders in models of itinerant electrons interacting with classical or quantum fields (1999)

## Publications

#### Publication list

all-publications.pdf#### Selected publications

Jean Barbier, Chun Lam Chan and Nicolas MacrisLong version with detailed proofs of ISIT 2018 submission "Adpative Path Interpolation for Sparse Systems: Application to a Simple Censored Block Model" |
Adaptive Path Interpolation Method for Sparse Systems: Application to a censored Block Model |

Dimitris Achlioptas, S. Hamed Hassani, Nicolas Macris and Ruediger Urbankepreprint pp. 1-63 |
New bounds for random constraint satisfaction problems via spatial coupling |

A. Giurgiu, N. Macris, R. UrbankeTransactions on Information Theory |
Spatial coupling as a proof technique |

S. Kumar, A. Young, N. Macris, H. Pfister
preprint, arXiv 1301.6111v2, submitted IEEE Transactions on Information Theory |
A proof of treshold saturation for spatially coupled LDPC codes on BMS channels |

Rafah El-Khatib, Nicolas Macris, Ruediger Urbankeextended version of ITW Sevilla 2013, arXiv 1304.6026v2 pp. 1-12 |
Displacement Convexity - A useful framework for the study of spatially coupled codes |

Vahid Aref, Nicoals Macris, Marc Vuffraypreprint arXiv 1307.5210v2 |
Approaching the Rate Distortion Limit with Spatial Coupling Belief Propagation and Decimation |

S. Hamed Hassani, Nicolas Macris and Ruediger UrbankeIEEE Information Theory Workshop - ITW Dublin pp 1-5 (2010) |
Coupled Graphical Models and Their Thresholds |

S. B. Korada, N. MacrisIEEE Transactions on Information Theory, vol 56, no 11, November 2010 |
Tight bounds on the capacity of binary input random CDMA systems |

Macris, NIEEE Transactions in Information Theory, vol 53, no 7, pp 2365-2375 (2007) |
Sharp bounds on generalised exit functions |

Macris, NIEEE Transactions in Information Theory, vol. 53, num. 2 (2007), p. 664-683. |
Griffiths Kelly Sherman correlation inequalities: a useful tool in the theory of error correcting codes |

Dionys Baeriswyl, Nicolas MacrisCours de Troisieme Cycle de la Physique en Suisse Romande (donne en 2002, 2005 et 2008) |
N-Body Methods in Condensed Matter |

Nicolas Macrisunpublished preprint 2003 |
On the equality of edge and bulk conductance in the integer Hall effect: microscopic analysis |

Macris, NJournal of Physics A: Mathematical and General, vol. 36, num. 1565-1581 (2003), p. 1565 |
Spectral flow and level spacing of edge states for quantum Hall hamiltonians |

Macris, N; Martin, Ph A; PuleJournal of Physics A: Mathematical and General, vol. 32 (1999), p. 1985-1996 |
On edge states in semi-infinite quantum Hall systems |

Dorlas, T C; Macris, N; Pule, J VCommunications in Mathematical Physics, vol. 204, num. 2 (1999), p. 367-396 |
Characterisation of the spectrum of the Landau Hamiltonian with delta impurities |

Joel. L. Lebowitz and Nicolas MacrisJournal Mathematical Physics, vol 38 pp. 2084-2103 (1997) (special issue on condensed matter physics) |
Ground states and low temperature phases of itinerant electrons interacting with classical fields |

N. Macris, B. NachtergaeleJournal of Statistical Physics, vol 85 pp. 745-761 (1996) |
On the flux phase conjecture at half filling: an improved proof |

Antoine Maillard, Jean Barbier, Florent Krzakala, Nicolas Macris |
The Mutual Information in Random Linear Estimation Beyond i.i.d Matrices |

## Enseignement & Phd

#### Enseignement

- Communication Systems,
- Computer Science

#### Programmes doctoraux

- Doctoral program in computer and communication sciences

#### Doctorants

Luneau Clément Dominique

#### A dirigé les thèses de

Dia Mohamad Baker ...El-Khatib Rafah ...

Ferrari Christian ...

Giurgiu Andrei ...

Hassani Seyed Hamed ...

Korada Satish Babu ...

Kudekar Shrinivas ...

Vuffray Marc ...

## Cours

#### Traitement quantique de l'information

L'information est traitée et stockée dans des composants matériels. Avec leur miniaturisation, il faut remplacer le concept de bit classique par celui de bit quantique. Ce cours développe le sujet des communications, de la cryptographie et des corrélation...

#### Markov chains and algorithmic applications

#### Quantum Information Theory and Computation

Today one is able to manipulate matter at the nanoscale were quantum behavior becomes important and possibly information processing will have to take into account laws of quantum physics. We introduce concepts developed in the last 25 years to take advant...

#### Statistical Physics for Communication and Computer Science

The course introduces the student to notions of statistical physics which have found applications in communications and computer science. We focus on graphical models with the emergence of phase transitions, and their relation to the behavior of efficient...

#### Calcul quantique

La miniaturisation des ordinateurs conduit à réviser les paradigmes du calcul classique pour développer des modèles de calcul quantique. Le cours introduit les notions de bit quantique, portes logiques et circuits quantiques, traite les principaux algorit...

#### Learning theory

L'analyse des données et l'apprentiassage automatique (ou machine) jouent un role central dans plusieurs disciplines scientifiques et applications. Ce cours se concentre sur les sous-jacents théoriques de l'apprentissage automatique.

## Recherche

## Brief description

Currently my research projects are at the interface of error correcting codes, information theory, statistical physics and constraint satisfaction problems from theoretical computer science. The problems involved have deep relations, both in terms of concepts and methods, with the statistical mechanics of disordered systems and in particular spin and structural glasses on sparse or dense graphs. The recent practical success of message passing algorithms such as belief propagation and survey propagation calls for the development of a coherent mathematical framework. The emphasis is on rigorous results and methods, and these subjects are investigated using a mix of methods from mathematical and statistical physics, probability, functional analysis and discrete mathematics.I am also interested in quantum information theory and notably in quantum constraint satisfaction problems.

I have also worked in the field of mathematical physics on quantum Coulomb systems, quantum fermion models related to condensed matter physics, random magnetic Schroedinger operators, and aspects of the integral quantum Hall effect.

A few recent (and older) selected projects are briefly described below. This research is supported by grants of the Swiss National Foundation for Science.

## Spatial coupling in coding and constraint satisfac

Spatial coupling originated a decade ago in coding theoretical constructions that result into very performant graphical codes which allow to achieve Shannon's capacity with a low complexity decoding algorithm.We have investigated the underpinnings of this excellent behavior in various directions beyond coding theory and found that it is quite universal. In particular dynamical phase transition thresholds (or spinodal lines) are pushed towards static phase transition thresholds and the metastable states disappear. Condensation and sat-unsat thresholds (of glassy models) are not affected by coupling.

Coupled graphical models and their thresholds, IEEE Information Theory Workshop - ITW Dublin pp 1-5 (2010), S. Hamed Hassani, Nicolas Macris and Ruediger Urbanke

The following paper contains a conceptually simple proof of threshold saturation for general LDPC ensemble on general binary memoryless channels. The proof uses a "generic" variational formulation for this class of problems.

A proof of treshold saturation for spatially coupled LDPC preprint 2013 (S. Kumar, A. Young, N. Macris, H. Pfister)

We have also investigated spatial coupling, not so much from the point of view of an engineering construction, but as a new proof technique.

In particular we find that simple mathematically analysable algorithms behave much better on the coupled instances, a fact that allows to derive new rigorous lower bounds on the SAT-UNSAT thresholds of various constraint satisfaction problems. Remarkably these bounds can be proven to be valid for the original un-coupled system.

New bounds for random constraint satisfaction problems via spatial coupling prerpint 2014 (D. Achlioptas, H. Hassani, N. Macris, R. Urbanke)

It has been conjectured for some time that for LDPC codes on general binary memoryless channels the replica symmetric formula for the conditional Shannon entropy (average free energy of the associated spin glass) is exact. We prove this conjecture (theorem 6). The proof analyzes the spatially coupled ensemble and projects back onto the original un-coupled LDPC ensemble.

Spatial coupling as a proof technique preprint 2013 (A. Giurgiu, N. Macris, R. Urbanke)

## Displacement convexity: new applications in coding

In the realm of fluid mechanics and optimal mass transportation many functionals of interest are not convex but are "displacement convex". This is a relatively recent notion of convexity that is natural for functionals of measures (of a mass density). We have recently found that this notion of displacement convexity applies well to the variational formulation of spatially coupled codes over the binary erasure channel. This allows to provide new proofs of the existence and unicity of the solutions of the density evolution integral equations. The topic is currently being pursued in various directions.Analysis of Coupled Scalar Systems by Displacment Convexity preprint 2013 and ITW 2013 (R. El-Khatib, N. Macris, R. Urbanke)

Analysis of coupled scalar recursions by displacement convexity ISIT 2014 (R. El-Khatib, N. Macris, T. Richardson and R. Urbanke)

## Rigorous methods of stat mech in coding, communica

Various rigorous methods from statistical mechanics can be used to study various aspects of codes on graphs and communication systems. These include Cluster or Polymer Expansions, the Guerra-Toninelli interpolation method (further developed by Franz, Leone, Montanari, Panchenko), and classical correlation inequalities. Here is a sample of applications.The Bethe free energy allows to compute the conditional entropy of graphical code instances. A proof from the polymer expansion preprint 2013 (N. Macris, M. Vuffray).

Decay of corelations for sparse graph error correcting codes SIAM J. Discrete Math. vol 25, no 2, pp. 956-988 (2011) (special section on constraint satisfaction problems and message passing algorithms), (S. Kudekar, N. Macris).

Tight bounds on the capacity of binary input random CDMA systems

IEEE Transactions on Information Theory, vol 56, no 11, November 2010 (S. B. Korada, N. Macris)

Sharp bounds on generalised exit functions IEEE Transactions in Information Theory, vol 53, no 7, pp 2365-2375 (2007) (N. Macris)

Griffith Kelly Sherman correlation inequalities: a useful tool in the theory of error correcting codes IEEE Transactions in Information Theory, vol. 53, num. 2 (2007), p. 664-683 (N. Macris)

## Localization in magnetic fields and Hall effect

The theory of the integer quantum Hall effect rests on the existence of localized states at the band edges in the spectrum of magnetic random Schroedinger operators. This is the picture in the bulk of the two dimensional sample. The edges of the sample support extended chiral states so the spectral properties of magnetic operators with boundaries are different. Moreover one can compute the Hall conductance from bulk states or from the boundary states and of course the result can be proven to be the same: this involves a beautiful interplay of functional analysis, geometry and topology. The following papers are a contribution to the rigorous aspects of this theory.On the equality of edge and bulk conductance in the integer Hall effect: microscopic analysis unpublished 2003, N. Macris

Spectral flow and level spacing of edge states for quantum Hall hamiltonians Journal of Physics A: Mathematical and General, vol. 36, num. 1565-1581 (2003), p. 1565, N. Macris

On edge states in semi-infinite quantum Hall systems Journal of Physics A: Mathematical and General, vol. 32 (1999), p. 1985-1996, N. Macris, P. A. Martin and J. V. Pule

Characterisation of the spectrum of the Landau Hamiltonian with delta impurities

Communications in Mathematical Physics, vol. 204, num. 2 (1999), p. 367-396, T. C. Dorlas, N. Macris and J. V. Pule

The nature of the spectrum for a Landau hamiltonian with delta impurities, Journal of Statistical Physics, vol 87 pp. 847-875 (1997), T. C. Dorlas, N. Macris and J. V. Pule

Localization in a single band approximation to random Schroedinger operators in a magnetic field, Helvetica Physica Acta, vol 68 pp 329-364 (1995), T. C. Dorlas, N. Macris and J. V. Pule

## Quantum statistical mechanics

On the flux phase conjecture at half filling: an improved proof, Journal of Statistical Physics, vol 85 pp. 745-761 (1996), N. Macris, B. NachtergaeleThe Falicov-Kimball model: a review of exact results and extensions, Helvetica Physica Acta, vol 69 pp. 850-907 (1996), (special issue in honor of K. Hepp and W. Hunziker) authors: C. Gruber, N. Macris

Ground states and low temperature phases of itinerant electrons interacting with classical fields, Journal Mathematical Physics, vol 38 pp. 2084-2103 (1997) (special issue on condensed matter physics), Joel. L. Lebowitz and Nicolas Macris

On kink states of ferromagnetic chains, Physica A, vol 279 pp. 386-397 (2000), (special issue in honor of Joel Lebowitz) authors: Ky-Thuan Bach and Nicolas Macris

Higher period ordered phases on the Bethe lattice, Physical Review B, vol 63 pp. 165111:1-11 (2001), C. Gruber, N. Macris, Ph. Royer and J.K. Freericks

Diamagnetic Currents, Communications in Mathematical Physics, 117, 215-241 (1988), N. Macris, P. A. Martin and J. V. Pule

Large volume asymptotics of Brownian integrals and orbital magnetism, Large volume asymptotics of Brownian integrals and orbital magnetism, Annales Institut Henri Poincare, section A, tome 66, no 2 pp.147-183 (1997)

Ionization equilibrium in the electron-proton gas, Journal of Staistical Physics, vol 60, no5/6 (1990), N. Macris, P. A. Martin

Atomic versus ionized states in many-particle systems and the spectra of reduced density matrices: a model study, Journal of Staistical Physics, vol 67, no5/6 (1992), J. L. Lebowitz, N. Macris, P. A. Martin (1992)

Long range order in the Falicov-Kimball model near the symmetry point: extension of Kennedy-Lieb theorem, Reviews in Mathematical physics, vol 06, pp.927-946, (1994) (also reprinted in the State of Matter a volume dedicated to E.H.Lieb) authors: J. L. Lebowitz, N. Macris