Cours

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. Nachtergaele The 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