Papers from the arXiv since 1994

Codes for download : our message-passing algorithms for optimization and inference

__________________________________________________________


90% complete list

Subjects

Statistical physics, Combinatorial and Stochastic Optimization, Inference and Information Theory
Statistical Physics in Computational Biology and Neural Computation
Statistical Mechanics and Lattice Statistics
Statistical Physics of Disordered Systems
Game theoretical models
Quantum statistical mechanics
Review papers


__________________________________________________________


Statistical physics, Optimization, Inference and Information Theory


The zero-patient problem with noisy observations, F. Altarelli, A. Braunstein, L. Dall'Asta, A. Ingrosso, R. Zecchina, J. Stat. Mech. (2014) P10016
Fast and accurate multivariate Gaussian modeling of protein families: Predicting residue contacts and protein-interaction partners, Carlo Baldassi, Marco Zamparo, Christoph Feinauer, Andrea Procaccini, Riccardo Zecchina, Martin Weigt, Andrea Pagnani, PLoS ONE 9(3): e92721 (2014)
Stochastic Optimization of Service Provision with Selfish Users, F. Altarelli, A. Braunstein, C. F. Chiasserini, L. Dall'Asta, P. Giaccone, E. Leonardi, R. Zecchina, paper presented at NETSTAT Workshop, Budapest - June 2013
Containing epidemic outbreaks by message-passing techniques, F. Altarelli, A. Braunstein, L. Dall'Asta, J.R. Wakeling, R. Zecchina, Phys. Rev. X 4, 021024 (2014)
Theory and learning protocols for the material tempotron model, Carlo Baldassi, Alfredo Braunstein, Riccardo Zecchina, J. Stat. Mech. 2013(12) P12013
On the performance of a cavity method based algorithm for the Prize-Collecting Steiner Tree Problem on graphs, Indaco Biazzo, Alfredo Braunstein, Riccardo Zecchina, Phys. Rev. E 86, 026706 (2012)
Perturbation Biology: inferring signaling networks in cellular systems, E. J. Molinelli et. al. PLoS Comput Biol 9(12) e1003290 (2013)
Bayesian inference of epidemics on networks via Belief Propagation, F. Altarelli, A. Braunstein, L. Dall'Asta, A. Lage-Castellanos, R. Zecchina, Phys. Rev. Lett. 112, 118701 (2014)
Large deviations of cascade processes on graphs, F. Altarelli, A. Braunstein, L. Dall'Asta, R. Zecchina, Phys. Rev. E 87, 062115 (2013)
Modeling competing endogenous RNAs networks, Carla Bosia, Andrea Pagnani, Riccardo Zecchina, PLoS ONE 8(6): e66609 (2013)
Sign problem in the Bethe approximation, A. Ramezanpour, R. Zecchina, Phys. Rev. B 86, 155147 (2012)
Optimizing spread dynamics on graphs by message passing, F. Altarelli, A. Braunstein, L. Dall'Asta, R. Zecchina, J. Stat. Mech. 2013, P09011 (2013)
Message passing for quantified Boolean formulas, Pan Zhang, Abolfazl Ramezanpour, Lenka Zdeborová, Riccardo Zecchina, J. Stat. Mech. (2012) P05025
Cavity approach to sphere packing in Hamming space   A. Ramezanpour, RZ, Phys. Rev. E 85, 021106 (2012)
Efficient data compression from statistical physics of codes over finite fields   , A. Braunstein, F. Kahyan, R. Zecchina, Phys. Rev. E 84, 051111 (2011)
Stochastic optimization by message passing   , F. Altarelli, A. Braunstein, A. Ramezanpour, R. Zecchina, JSTAT P11009 (2011)
Statistical physics approach to graphical games: local and global interactions   , A. Ramezanpour, J. Realpe-Gomez, R. Zecchina, European Physical Journal B 81, 327 (2011)
Inference and learning in sparse systems with multiple states   , A. Braunstein, A. Ramezanpour, R. Zecchina, P. Zhang, Phys. Rev. E 83, 056114 (2011)
Stochastic Matching Problem   , F. Altarelli, A. Braunstein, A. Ramezanpour, R. Zecchina, PRL 106, 190601 (2011)
Belief propagation for weighted b matchings on arbitrary graphs and its relation to linear programs with integer solutions, M. Bayati, C. Borgs, J. Chayes, R. Zecchina, SIAM Journal on Discrete Mathematics 25, 989 (2011)
Aligning graphs and finding substructures by a cavity approach   , S. Bradde, A. Braunstein, H. Mahmoudi, F. Tria, M. Weigt, R. Zecchina, EPL 89, 37009 (2010)
Clustering with shallow trees , M. Bailly-Bechet, S. Bradde, A. Braunstein, A. Flaxman, L. Foini, R. Zecchina, JSTAT P12010 (2010)
Statistical mechanics of budget-constrained auctions   , F. Altarelli, A. Braunstein, J. Realpe-Gomez, R. Zecchina, JSTAT P072002 (2009)
A rigorous analysis of the cavity equations for the minimum spanning tree   , M. Bayati, A. Braunstein, R. Zecchina, J. Math. Phys. 49, 125206 (2008)
Pairs of SAT Assignments and Clustering in Random Boolean Formulae   , H. Daude', M. Mezard. T. Mora R. Zecchina, Theoretical Computer Science 393, 260-279 (2008)
On the exactness of the cavity method for Weighted b-Matchings on Arbitrary Graphs and its Relation to Linear Programs  , M. Bayati, C. Borgs, J. Chayes, R. Zecchina, J. Stat. Mech. (JSTAT) L06001 (2008)
Inference algorithms for gene networks: A statistical-mechanics analysis  , A. Braunstein, A. Pagnani, M. Weigt, R. Zecchina, J. Stat. Mech. (JSTAT) P12001 (2008)
Statistical Mechanics of Steiner trees  , M. Bayati, C. Borgs, A. Braunstein, J. Chayes, A. Ramezanpour, R. Zecchina, Phys. Rev. Lett. 101, 037208 (2008) In this paper we present the cavity algorithm for the bounded depth (D) minimum Steiner tree problem. While applications and analysis of the algorithm are given elsewhere, here we check the cavity equations on few examples of random graphs, namely Erdos-Renyi, Scale-free and complete graphs. In A sharp threshold for minimum bounded-depth and bounded-diameter spanning trees and Steiner trees in random networks by O. Angel, A. Flaxman and D.B. Wilson, one finds the first rigorous derivation of a non trivial scaling of the optimal cost with the depth in complete graphs. Our approximate numerical results appear to be compatible with these exact values, a fact that make us conjecture that the cavity approach could be exact for the bounded depth Steiner problem on random complete graphs.
Entropy landscape and non-Gibbs solutions in constraint satisfaction problems  , L. Dall'Asta, A. Ramezanpour, R. Zecchina, Phys. Rev. E 77, 031118 (2008)
Propagation of external regulation and asynchronous dynamics in random Boolean networks  , H. Mahmoudi, A. Pagnani, M. Weigt, R. Zecchina, CHAOS, 026109 (2007
Encoding for the Blackwell Channel with Reinforced Belief Propagation  , A. Braunstein, F. Kayhan, R. Zecchina, IEEE ISIT International Symposium on Information Theory, Nizza (Francia) 24- 29 June 2007, 2007
Statistical Mechanics of Combinatorial Auctions  , T. Galla, M. Leone, M. Marsili, M. Sellitto, M. Weigt, R. Zecchina Phys. Rev. Lett.97, 128701 (2006)
The computational core and the fixed point organization in Boolean Networks percolation  , L. Correale, M. Leone, A. Pagnani, M. Weigt, R. Zecchina, JSTAT P03002 (2006)
Learning by message passing in networks of discrete synapses  , A. Braunstein, R. Zecchina, Phys. Rev. Lett.96, 030201 (2006)
Message passing algorithm for non linear nodes and data compression  , S. Ciliberti, M. Mezard, R. Zecchina, Complexus 3, 58 (2006); (Best Paper Award)
Core percolation and onset of complexity in Boolean networks  , L. Correale, M. Leone, A. Pagnani, M. Weigt, R. Zecchina, Phys. Rev. Lett. 018101 (2006)
Pairs of SAT Assignments and Clustering in Random Boolean Formulae   , H. Daude', M. Mezard, T. Mora, R. Zecchina, Theoretical Computer Science 393, 260-279 (2008)
Lossy data compression with random gates  , S. Ciliberti, M. Mezard, R. Zecchina, Phys. Rev. Lett. 95 (2005) 038701
Clustering of solutions in the random satisfiability problem   , M. Mezard, T. Mora, R. Zecchina, Phys. Rev. Lett. 94, 197205 (2005)
From the efficient selection ground states clusters to source coding   D. Battaglia, A. Braunstein, J. Chavas, R. Zecchina, Phys. Rev. E 72, 015103 (2005)
Survey-propagation decimation through distributed local computations  J. Chavas, C. Furtlehner, M. Mezard, R. Zecchina, J. Stat. Mech. P11016 (2005)
Minimizing energy below the glass thresholds   , D. Battaglia, M. Kolar, R. Zecchina, Phys. Rev. E 70, 036107 (2004)
Survey Propagation as local equilibrium equations   , A. Braunstein, R. Zecchina, J. Stat. Mech. : Theory and Experiments (JSTAT), P06007 (2004)
New iterative algorithms for hard combinatorial problems , R. Zecchina, In "New Algorithms in Physics", book chapter in Lecture Notes in Physics, A.K. Hartmann, H. Rieger (edts.), Springer-Verlag, 2004
Complexity transitions and statistical physics algorithms for hard random combinatorial problems, R. Zecchina, book chapter in Advances in Condensed Matter and Statistical Physics. E. Korutcheva and R. Cuerno (edts). Nova Science Publishers, New York (2004)
Exact probing of glassy states by Survey Propagation , D. Battaglia, A. Braunstein, J. Chavas and R. Zecchina, Progress in Theoretical Physics Supplement (157), 330-337 (2005)
Statistical Physics, Optimization and Source Coding , R. Zecchina, Pramana - Journal of Physics, in press (2005) (proceedings of Statphys22 - Bangalore, 2004)
From statistical physics methods to algorithms , D. Battaglia, M. Kolar, R. Zecchina, Int. J. Mod. Phys. B 20, 2814-2823, (2006)
Threshold values of Random K-SAT from the cavity method   , S. Mertens, M. Mezard, R. Zecchina, Random Structures and Algorithms 28, 340-373 (2006)
Survey and Belief Propagation on random K-SAT , A. Braunstein, R. Zecchina, Lect Notes Comput Sc 2919: 519-528 (2004)
Survey Propagation: an algorithm for satisfiability   , A. Braunstein, M. Mezard, R. Zecchina, Random Structures and Algorithms 27, 201-226 (2005)
Bicoloring Random Hypergraphs   , T. Castellani, V. Napolano, F. RIcci-Tersenghi, R. Zecchina, J. Phys. A 36, 11037 (2003)
Polynomial iterative algorithms for coloring and analyzing random graphs   , A. Braunstein, R. Mulet, A. Pagnani, M. Weigt, R. Zecchina, Phys. Rev. E 68, 036702 (2003)
Coloring random graphs  , Phys. Rev. Lett. 89, 268701 (2002), with R. Mulet, A. Pagani and  M. Weigt (2002)
Random K-satisfiability: from an analytic solution to a new efficient algorithm , with M. Mezard, Phys.Rev. E E 66, 056126 (2002)
Analytic and Algorithmic Solution of Random Satisfiability Problems , Science 297, 812 (2002) (Sciencexpress published on-line 27-June-2002; 10.1126/science.1073287), with M.Mezard and G.Parisi;  Comment by Carla P. Gomes and Bart Selman: Satisfied by physics
Two solutions to diluted p-spin models and XORSAT problemswith M.Mezard and F. Ricci-Tersenghi, J. Stat. Phys. 111, 505 (2003)
Complexity transitions in global algorithms for sparse linear systems over finite fields,   J. Phys. A 35, 7559 (2002), with A. Braunstein, M. Leone, F. Ricci-Tersenghi
Optimizing search via rare events , Phys. Rev. Lett. 88 , 178701 (2002), with A. Montanari,
Hiding solutions in random satisfiability problems: A statistical mechanics approach , Phys. Rev. Lett. 88, 188701 (2002), with W. Barthel, A.K. Hartmann, M. Leone, F. Ricci-Tersenghi, M. Weigt, (2001)
Exact solutions for diluted spin glasses and optimization problems , Phys.Rev.Lett. 87, 127209 (2001) with S. Franz, M. Leone and F. Ricci-Tersenghi
Phase coexistence and finite size scaling in random combinatorial problems , J. Phys. A 34 (2001) 4615, with M. Leone, F. Ricci-Tersenghi
The simplest random K-satisfiability problem , Phys. Rev. E 63, 026702 (2001), with F. Ricci-Tersenghi, M. Weigt
Determining computational complexity from characteristic `phase transitions' , Nature 400, 133 (8-July-1999), with R. Monasson, S.Kirkpatrick, B.Selman, L.Troyansky; Comment by P.W. Anderson: Computing in finite time .
2+P SAT: Relation of Typical-Case Complexity to the Nature of the Phase Transition , Random Structures and Algorithms, 414 (1999) with R.Monasson, S.Kirkpatrick,B.Selman, L.Troyansky.
Entropy of the K-Satisfiability Problem , Phys. Rev. Lett. 76, 3881 (1996) with R. Monasson
Statistical mechanics of the random K-SAT model , Phys. Rev. E 56, 1357 (1997) with R. Monasson
Tricritical Points in Random Combinatorics , J. Phys. A 31, 9209 (1998) with R. Monasson
Phase transition and search cost in the 2+p-sat problem, Proceedings of PhysComp 96, T.Toffoli, M.Biafore, J.Leao eds., Boston (1996) with R. Monasson, S.Kirkpatrick, B.Selman, L.Troyansky
On the Ground State Structure of P and NP-complete Random Decision Problems Mod. Phys. Lett. B 13,1 (1999) with A.S. Gliozzi

Statistical Physics in Computational Biology and Neural Computation

Integrated transcriptional and competitive endogenous RNA networks are cross-regulated in permissive molecular environments, U. Ala et. al., PNAS 110, 7154 (2013)
Modeling competing endogenous RNAs networks, C. Bosia, A.Pagnani, R. Zecchina, PLoS ONE 8(6): e66609 (2013)
Shape similarity, better than semantic membership, accounts for the structure of visual object representations in a population of monkey inferotemporal neurons, C Baldassi, A Alemi-Neissi, M Pagan, JJ DiCarlo, R Zecchina, D Zoccolan, PLoS computational biology 9 (8), e1003167 (2013)
Direct-coupling analysis of residue coevolution captures native contacts across many protein families   F. Morcos, et. al. PNAS 108, E1293 (2011)
3D Protein Structure Predicted from evolutionary sequence variation   , D.S. Marks et. al,  PLoS O NE 6, e28766 (2011)
Finding undetected protein associations in cell signaling by belief propagation   M. Bailly-Bechet, et. al PNAS 108, 882 (2011)
An externally modulated, noise-driven switch for the regulation of SPI1 in Salmonella enterica serovar Typhimurium, M. Bailly-Bechet, A. Beneke, W.D. Hardt, V. Lanza, A. Sturm, R. Zecchina, J. Mathematical biology 63, 637 (2011)
Aligning graphs and finding substructures by a cavity approach   , S. Bradde, A. Braunstein, H. Mahmoudi, F. Tria, M. Weigt, R. Zecchina, EPL 89, 37009 (2010)
Clustering with shallow trees   , M. Bailly-Bechet, S. Bradde, A. Braunstein, A. Flaxman, L. Foini, R. Zecchina, JSTAT P12010 (2010)
Gene-network inference by message passing  , A. Braunstein, A. Pagnani, M. Weigt, R. Zecchina, J. of Physics 95, Conf. Series, 012016 (2008)
Inference algorithms for gene networks: A statistical-mechanics analysis  , A. Braunstein, A. Pagnani, M. Weigt, R. Zecchina, J. Stat. Mech. (JSTAT) P12001 (2008)
Viable flux distribution in metabolic networks  , G. Bianconi, R. Zecchina, Networks and Heterogeneous Media 3, 361 (2008)
Efficient supervised learning in networks with binary synapses  , C. Baldassi, A. Braunstein, N. Brunel, R. Zecchina, Proc. Nat. Acad. Sci. (PNAS) 104, 11079-11084 (2007)
Learning by message passing in networks of discrete synapses  , A. Braunstein, R. Zecchina, Phys. Rev. Lett., in press Feb 6 (2006)
Weight Space Structure and Internal Representations: a Direct Approach to Learning and Generalization in Multilayer Neural Network , Phys. Rev. Lett. 75, 2432 (1995) with R. Monasson
Learning and generalization theories of large committee--machines , Mod.Phys.Lett. B, 1887 (1996) with R. Monasson
Analytical and Numerical Study of Internal Representations in Multilayer Neural Networks with Binary Weights , Phys.Rev E 54, 717 (1996) with S. Cocco and R. Monasson Response Functions Improving Performance in Analog Attractor Neural Networks , Phys.Rev. E 49, R1823 (1994) with N. Brunel

Non planar lattices statistics

Counting over non planar lattices, RZ Physica A 302, 100 (2001)
Combinatorial and topological approach to the 3D Ising model , J.Phys.A 33, 741-761 (2000), with T. Regge. In this work we applied the techniques developed in J. Math. Phys. 37, 2796 (1996) to the case of the 3D cubic lattice which has a genus g=1+N/4, where N is the number of spins. Independently from us, A. Galluccio and M. Loebel developed a similar method providing the first general proof of the exactness of the Pfaffian expansion of the generating function of perfect matchings for non planar lattices (see e.g. Electronic Journal of Combinatorics 6, (1999) and PRL 84, 5294 (2000)).
Exact Solution of the Ising Model on Group Lattices of Genus g>1 , J. Math. Phys. 37, 2796 (1996), with T. Regge.

Statistical Physics of Disordered Systems

Core percolation and onset of complexity in Boolean networks   L Correale, M. Leone, A. Pagnani, M. Weigt, R. Zecchina Phys. Rev. Lett. 018101 (2006)
Ferromagnetic ordering in graphs with arbitrary degree distribution  Eur. Phys. J. B 28, 191 (2002), with M. Leone, A. Vazquez, A. Vespignani
Exact solutions for diluted spin glasses and optimization problems, , Phys. Rev. Lett. 87 (2001) 127209, with S. Franz, M. Leone, F. Ricci-Tersenghi
A ferromagnet with a glass transition, , Europhys. Lett. 55 (2001) 465, with S. Franz, M. Mezard, F. Ricci-Tersenghi, M. Weigt
Glassy dynamics near zero temperature , Phys. Rev. E62, R7567 (2000) with F. Ricci-Tersenghi
Time scale separation and heterogeneous off-equilibrium dynamics in spin models over random graphs , Phys. Rev. E59, 1299 (1999) with A. Barrat

Game theoretical models

Statistical physics approach to graphical games: local and global interactions   , A. Ramezanpour, J. Realpe-Gomez, R. Zecchina, European Physical Journal B 81, 327 (2011)
Statistical mechanics of budget-constrained auctions   , F. Altarelli, A. Braunstein, J. Realpe-Gomez, R. Zecchina, JSTAT P072002 (2009)
Statistical mechanics of asset markets with private information , J.Quant.Finance 1, 203-211 (2001) with J. Berg, M. Marsili, A. Rustichini
Statistical Mechanics of systems with heterogeneous agents: Minority Games , Phys. Rev. Lett. 84, 1824 (2000), with D. Challet, M.Marsili
Exact solution of a modified El Farol's bar problem: Efficiency and the role of market impact , with M.Marsili and D. Challet, Physica A 280, 522 (2000)
Learning to coordinate in non-stationary... , Phys. Rev. Lett., 87, 208701 (2001) with M. Marsili, R. Mulet, F. Ricci-Tersenghi

Quantum systems

Quantum dynamics of coupled bosonic wells within the Bose-Hubbard picture , with R. Franzosi and V. Penna, Int. J. Mod. Phys. B 14 (2000) 943-961
Two--Boson Hamiltonian for Shor's Algorithm , with M. Rasetti, E. Tagliati, Phys. Rev. A, 2594 (1997)
Generalized fullerene-like lattices, and itinerant interacting electrons, with M.Rasetti , Physica A 199, 539 (1993)
Superfluidity of the Bose--Hubbard Model: su(1,1) Linearization Scheme, with L. Amico, M. Rasetti, Physica A 230, 300-312 (1996)
Mean-field Studies of Hubbard Hamiltonians Coupled via Interlayer Pair Tunelling,  R. Zecchina, Mod. Phys. Lett. B, 1817 (1993)

Review papers

Statistical mechanics and combinatorial problems, R. Zecchina, Encyclopedia of Mathematical Physics, eds. J.-P. Francoise, G.L. Naber and Tsou S.T. Oxford: Elsevier, 2006 (ISBN 978-0-1251-2666-3), volume 2
Statistical mechanics methods and phase transitions in optimization problems. Theoretical Computer Science 265, 3 (2001), with O.C. Martin, R. Monasson
Lattice statistics over structures of high topological genus , review paper with T. Regge, it will never be finished.