Selection of papers by Riccardo Zecchina
preprints 2011
Cavity approach to sphere packing in Hamming space ,
A. Ramezanpour, R. Zecchina, ArXiv (2011)
3D Protein Structure Predicted from Sequence ,
D.S. Marks, L.J. Colwell, R. Sheridan, T.A. Hopf, A. Pagnani, R. Zecchina, C. Sander, ArXiv (2011)
Simultaneous reconstruction of multiple signaling pathways via the
prize-collecting Steiner forest problem ,
N. Tuncbag, A.Braunstein, A. Pagnani, S.-S.C. Huang, J. Chayes,
C. Borgs, R. Zecchina, E. Fraenkel, RECOMB 2012
Statistical physics, Combinatorial and Stochastic Optimization, Inference and Information Theory
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 trvial 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 detph 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 problems, with 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
Finding undetected protein associations in cell signaling by belief propagation
M. Bailly-Bechet, C. Borgs, J. Chayes, A. Dagkessamanskaia , J-M. Francois, R. Zecchina,
PNAS 108, 882 (2011)
An externally modulated, noise-driven switch for the regulation of SPI1 in Salmonella enterica serovar Typhimurium ,
M. Bailly-Bechetm 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 , 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, still to be finished.
Return to my
home page.