Efficient LDPC Codes over GF(q) for Lossy Data Compression (2009)
Braunstein, Alfredo, Kayhan, Farbod, Zecchina, Riccardo
In this paper we consider the lossy compression of a binary symmetric source. We present a scheme that provides a low complexity lossy compressor with near optimal empirical performance. The proposed...
Pairs of SAT Assignment in Random Boolean Formulae (2008)
Daudé, Hervé, Mezard, Marc, Mora, Thierry, Zecchina, Riccardo
We investigate geometrical properties of the random K-satisfiability problem using the notion of x-satisfiability: a formula is x-satisfiable if there exist two SAT assignments differing in Nx...
Pairs of SAT Assignment in Random Boolean Formulae (2008)
Daudé, Hervé, Mezard, Marc, Mora, Thierry, Zecchina, Riccardo
We investigate geometrical properties of the random K-satisfiability problem using the notion of x-satisfiability: a formula is x-satisfiable if there exist two SAT assignments differing in Nx...
Statistical Physics of the Random (2007)
Satisfiability Problem Remi, Riccardo Zecchina, Summary Olivier Dubois, Remi Monasson, Remi Monasson
n abrupt threshold behaviour, separating a SAT phase from an UNSAT one, has indeed been rigourously confirmed for 2-SAT, which is in P, with ff c (2) = 1 [2, 5]. For larger K 3, K-SAT is in NP and...
Rémi Monasson, Riccardo Zecchina, Scott Kirkpatrick, Bart Selman, Lidror Troyansky
We give analytical and numerical results concerning a new Satisfiability problem for random Boolean expressions. Our model smoothly interpolates between the polynomial 2--SAT problem and the...
Response Functions Improving Performance in Analogue Attractor Neural Networks (2007)
Nicolas Brunel, Riccardo Zecchina, Typeset Using Revt
In the context of attractor neural networks, we study how the equilibrium analogue neural activities, reached by the network dynamics during memory retrieval, may improve storage performance by...
Antonio S. Gliozzi, Riccardo Zecchina
The structure of the space of solutions of a prototype model of complexity theory and random structures is analyzed. Depending on a single control parameter, the model interpolates between di#erent...
Bayati, Mohsen, Borgs, Christian, Chayes, Jennifer, Zecchina, Riccardo
We consider the general problem of finding the minimum weight b-matching on arbitrary graphs. We prove that, whenever the linear programming (LP) relaxation of the problem has no fractional...
Efficient supervised learning in networks with binary synapses (2007)
Baldassi, Carlo, Braunstein, Alfredo, Brunel, Nicolas, Zecchina, Riccardo
Recent experimental studies indicate that synaptic changes induced by neuronal activity are discrete jumps between a small number of stable states. Learning in systems with discrete synapses is known...
Efficient supervised learning in networks with binary synapses (2007)
Baldassi, Carlo, Braunstein, Alfredo, Brunel, Nicolas, Zecchina, Riccardo
No abstract available.
Statistical physics methods in computational biology (2007)
Micheletti, Cristian, Leone, Michele, Zecchina, Riccardo, Zagordi, Osvaldo
The interest of statistical physics for combinatorial optimization is not new, it suffices to think of a famous tool as simulated annealing. Recently, it has also resorted to statistical inference to...
Viable flux distribution in metabolic networks (2007)
Bianconi, Ginestra, Zecchina, Riccardo
The metabolic networks are very well characterized for a large set of organisms, a unique case in within the large-scale biological networks. For this reason they provide a a very interesting...
Propagation of external regulation and asynchronous dynamics in random Boolean networks (2007)
Mahmoudi, Hamed, Pagnani, Andrea, Weigt, Martin, Zecchina, Riccardo
Boolean Networks and their dynamics are of great interest as abstract modeling schemes in various disciplines, ranging from biology to computer science. Whereas parallel update schemes have been...
Pairs of SAT Assignment in Random Boolean Formulae (2006)
Mora, Thierry, Mezard, Marc, Zecchina, Riccardo
We investigate geometrical properties of the random K-satisfiability problem using the notion of x-satisfiability: a formula is x-satisfiable if there exist two SAT assignments differing in Nx...
Survey Propagation Methods for Efficient Optimization and Probing of Glassy States (2006)
Zecchina, Riccardo, Santoro, Giuseppe E., Battaglia, Demian A.
Statistical mechanics of combinatorial auctions (2006)
Galla, Tobias, Leone, Michele, Marsili, Matteo, Sellitto, Mauro, Weigt, Martin, Zecchina, Riccardo
Combinatorial auctions are formulated as frustrated lattice gases on sparse random graphs, allowing the determination of the optimal revenue by methods of statistical physics. Transitions between...
Threshold values of Random K-SAT from the cavity method (2006)
Mertens, Stephan, Mezard, Marc, Zecchina, Riccardo
Using the cavity equations of \cite{mezard:parisi:zecchina:02,mezard:zecchina:02}, we derive the various threshold values for the number of clauses per variable of the random $K$-satisfiability...
Survey-propagation decimation through distributed local computations (2005)
Chavas, Joel, Furtlehner, Cyril, Mezard, Marc, Zecchina, Riccardo
We discuss the implementation of two distributed solvers of the random K-SAT problem, based on some development of the recently introduced survey-propagation (SP) algorithm. The first solver, called...
Survey-propagation decimation through distributed local computations (2005)
Chavas, Joel, Furtlehner, Cyril, Mezard, Marc, Zecchina, Riccardo
We discuss the implementation of two distributed solvers of the random K-SAT problem, based on some development of the recently introduced survey-propagation (SP) algorithm. The first solver, called...
Learning by message-passing in networks of discrete synapses (2005)
Braunstein, Alfredo, Zecchina, Riccardo
We show that a message-passing process allows to store in binary "material" synapses a number of random patterns which almost saturates the information theoretic bounds. We apply the learning...
Pairs of SAT Assignments and Clustering in Random Boolean Formulae (2005)
Mora, Thierry, Mezard, Marc, Zecchina, Riccardo
We investigate geometrical properties of the random K-satisfiability problem. For large enough K, we prove that there exists a region of clause density, below the satisfiability threshold, where SAT...
Pairs of SAT Assignments and Clustering in Random Boolean Formulae (2005)
Mora, Thierry, Mezard, Marc, Zecchina, Riccardo
We investigate geometrical properties of the random K-satisfiability problem. For large enough K, we prove that there exists a region of clause density, below the satisfiability threshold, where SAT...
Pairs of SAT Assignments and Clustering in Random Boolean Formulae (2005)
Mora, Thierry, Mezard, Marc, Zecchina, Riccardo
We investigate geometrical properties of the random K-satisfiability problem. For large enough K, we prove that there exists a region of clause density, below the satisfiability threshold, where SAT...
Pairs of SAT Assignment in Random Boolean Formulae (2005)
Daudé, Hervé, Mezard, Marc, Mora, Thierry, Zecchina, Riccardo
We investigate geometrical properties of the random K-satisfiability problem using the notion of x-satisfiability: a formula is x-satisfiable if there exist two SAT assignments differing in Nx...
Alternative solutions to diluted p-spin models and XORSAT problems (2005)
Mézard, Marc, Ricci-Tersenghi, Federico, Zecchina, Riccardo
We derive analytical solutions for p-spin models with finite connectivity at zero temperature. These models are the statistical mechanics equivalent of p-XORSAT problems in theoretical computer...
The random K-satisfiability problem: from an analytic solution to an efficient algorithm (2005)
Mézard, Marc, Zecchina, Riccardo
We study the problem of satisfiability of randomly chosen clauses, each with K Boolean variables. Using the cavity method at zero temperature, we find the phase diagram for the K=3 case. We show the...
A ferromagnet with a glass transition (2005)
Franz, Silvio, Mézard, Marc, Ricci-Tersenghi, Federico, Weigt, Martin, Zecchina, Riccardo
We introduce a finite-connectivity ferromagnetic model with a three-spin interaction which has a crystalline (ferromagnetic) phase as well as a glass phase. The model is not frustrated, it has a...
Statistical mechanics methods and phase transitions in optimization problems (2005)
Martin, Olivier, Monasson, Rémi, Zecchina, Riccardo
Recently, it has been recognized that phase transitions play an important role in the probabilistic analysis of combinatorial optimization problems. However, there are in fact many other relations...
Survey-propagation decimation through distributed local computations (2005)
Chavas, Joel, Furtlehner, Cyril, Mezard, Marc, Zecchina, Riccardo
We discuss the implementation of two distributed solvers of the random K-SAT problem, based on some development of the recently introduced survey-propagation (SP) algorithm. The first solver, called...
Threshold values of Random K-SAT from the cavity method (2005)
Mertens, Stephan, Mezard, Marc, Zecchina, Riccardo
Using the cavity equations of \cite{mezard:parisi:zecchina:02,mezard:zecchina:02}, we derive the various threshold values for the number of clauses per variable of the random $K$-satisfiability...
Threshold values of Random K-SAT from the cavity method (2005)
Mertens, Stephan, Mezard, Marc, Zecchina, Riccardo
Using the cavity equations of \cite{mezard:parisi:zecchina:02,mezard:zecchina:02}, we derive the various threshold values for the number of clauses per variable of the random $K$-satisfiability...
Survey-propagation decimation through distributed local computations (2005)
Chavas, Joel, Furtlehner, Cyril, Mezard, Marc, Zecchina, Riccardo
We discuss the implementation of two distributed solvers of the random K-SAT problem, based on some development of the recently introduced survey-propagation (SP) algorithm. The first solver, called...
Source coding by efficient selection of ground states clusters (2004)
Battaglia, Demian, Braunstein, Alfredo, Chavas, Joël, Zecchina, Riccardo
In this letter, we show how the Survey Propagation algorithm can be generalized to include external forcing messages, and used to address selectively an exponential number of glassy ground states....
Minimizing energy below the glass thresholds (2004)
Battaglia, Demian, Kolář, Michal, Zecchina, Riccardo
Focusing on the optimization version of the random K-satisfiability problem, the MAX-K-SAT problem, we study the performance of the finite energy version of the Survey Propagation (SP) algorithm. We...
Minimizing energy below the glass thresholds (2004)
Battaglia, Demian A., Kolar, Michal, Zecchina, Riccardo
Focusing on the optimization version of the random K-satisfiability problem, the MAX-K-SAT problem, we study the performance of the finite energy version of the Survey Propagation (SP) algorithm. We...
Threshold values of Random K-SAT from the cavity method (2003)
Mertens, Stephan, Mezard, Marc, Zecchina, Riccardo
Using the cavity equations of \cite{mezard:parisi:zecchina:02,mezard:zecchina:02}, we derive the various threshold values for the number of clauses per variable of the random $K$-satisfiability...
Bicoloring Random Hypergraphs (2003)
Castellani, Tommaso, Napolano, Vincenzo, Ricci-Tersenghi, Federico, Zecchina, Riccardo
We study the problem of bicoloring random hypergraphs, both numerically and analytically. We apply the zero-temperature cavity method to find analytical results for the phase transitions (dynamic and...
Alternative solutions to diluted p-spin models and XORSAT problems (2003)
Mézard, Marc, Ricci-Tersenghi, Federico, Zecchina, Riccardo
We derive analytical solutions for p-spin models with finite connectivity at zero temperature. These models are the statistical mechanics equivalent of p-XORSAT problems in theoretical computer...
Alternative solutions to diluted p-spin models and XORSAT problems (2003)
Mézard, Marc, Ricci-Tersenghi, Federico, Zecchina, Riccardo
We derive analytical solutions for p-spin models with finite connectivity at zero temperature. These models are the statistical mechanics equivalent of p-XORSAT problems in theoretical computer...
The random K-satisfiability problem: from an analytic solution to an efficient algorithm (2002)
Mezard, Marc, Zecchina, Riccardo
We study the problem of satisfiability of randomly chosen clauses, each with K Boolean variables. Using the cavity method at zero temperature, we find the phase diagram for the K=3 case. We show the...
The random K-satisfiability problem: from an analytic solution to an efficient algorithm (2002)
Mézard, Marc, Zecchina, Riccardo
We study the problem of satisfiability of randomly chosen clauses, each with K Boolean variables. Using the cavity method at zero temperature, we find the phase diagram for the K=3 case. We show the...
The random K-satisfiability problem: from an analytic solution to an efficient algorithm (2002)
Mézard, Marc, Zecchina, Riccardo
We study the problem of satisfiability of randomly chosen clauses, each with K Boolean variables. Using the cavity method at zero temperature, we find the phase diagram for the K=3 case. We show the...
Complexity transitions in global algorithms for sparse linear systems over finite fields (2002)
Braunstein, Alfredo, Leone, Michele, Ricci-Tersenghi, Federico, Zecchina, Riccardo
We study the computational complexity of a very basic problem, namely that of finding solutions to a very large set of random linear equations in a finite Galois Field modulo q. Using tools from...
Boosting search by rare events (2001)
Montanari, Andrea, Zecchina, Riccardo
Randomized search algorithms for hard combinatorial problems exhibit a large variability of performances. We study the different types of rare events which occur in such out-of-equilibrium stochastic...
Statistical mechanics of asset markets with private information (2001)
Berg, Johannes, Marsili, Matteo, Rustichini, Aldo, Zecchina, Riccardo
Traders in a market typically have widely different, private information on the return of an asset. The equilibrium price of the asset may reflect this information more accurately if the number of...
A ferromagnet with a glass transition (2001)
Franz, Silvio, Mézard, Marc, Ricci-Tersenghi, Federico, Weigt, Martin, Zecchina, Riccardo
We introduce a finite-connectivity ferromagnetic model with a three-spin interaction which has a crystalline (ferromagnetic) phase as well as a glass phase. The model is not frustrated, it has a...
Statistical mechanics methods and phase transitions in optimization problems (2001)
Martin, Olivier, Monasson, Rémi, Zecchina, Riccardo
Recently, it has been recognized that phase transitions play an important role in the probabilistic analysis of combinatorial optimization problems. However, there are in fact many other relations...
A ferromagnet with a glass transition (2001)
Franz, Silvio, Mézard, Marc, Ricci-Tersenghi, Federico, Weigt, Martin, Zecchina, Riccardo
We introduce a finite-connectivity ferromagnetic model with a three-spin interaction which has a crystalline (ferromagnetic) phase as well as a glass phase. The model is not frustrated, it has a...
Statistical mechanics methods and phase transitions in optimization problems (2001)
Martin, Olivier, Monasson, Rémi, Zecchina, Riccardo
Recently, it has been recognized that phase transitions play an important role in the probabilistic analysis of combinatorial optimization problems. However, there are in fact many other relations...
Phase coexistence and finite-size scaling in random combinatorial problems (2001)
Leone, Michele, Ricci-Tersenghi, Federico, Zecchina, Riccardo
We study an exactly solvable version of the famous random Boolean satisfiability problem, the so called random XOR-SAT problem. Rare events are shown to affect the combinatorial "phase diagram"...
Exact Solutions for Diluted Spin Glasses and Optimization Problems (2001)
Franz, Silvio, Leone, Michele, Ricci-Tersenghi, Federico, Zecchina, Riccardo
Glassy dynamics near zero temperature (2000)
Ricci-Tersenghi, Federico, Zecchina, Riccardo
We numerically study finite-dimensional spin glasses at low and zero temperature, finding evidences for (i) strong time/space heterogeneities, (ii) spontaneous time scale separation and (iii) power...
Combinatorial and topological approach to the 3D Ising model (1999)
Regge, Tullio, Zecchina, Riccardo
We extend the planar Pfaffian formalism for the evaluation of the Ising partition function to lattices of high topological genus g. The 3D Ising model on a cubic lattice, where g is proportional to...
Exact solution of a modified El Farol's bar problem: Efficiency and the role of market impact (1999)
Marsili, Matteo, Challet, Damien, Zecchina, Riccardo
We discuss a model of heterogeneous, inductive rational agents inspired by the El Farol Bar problem and the Minority Game. As in markets, agents interact through a collective aggregate variable --...
Remi Monasson, Riccardo Zecchina, Scott Kirkpatrick, Bart Selman, Lidror Troyansky
ABSTRACT: Heuristic methods for solution of problems in the NP-complete class of decision problems often reach exact solutions, but fail badly at ‘‘phase boundaries,’ ’ across which the...
Tricritical Points in Random Combinatorics: the (2+p)-SAT case (1998)
Monasson, Remi, Zecchina, Riccardo
The (2+p)-Satisfiability (SAT) problem interpolates between different classes of complexity theory and is believed to be of basic interest in understanding the onset of typical case complexity in...
Cocco, Simona, Monasson, Remi, Zecchina, Riccardo
We study the weight space structure of the parity machine with binary weights by deriving the distribution of volumes associated to the internal representations of the learning examples. The learning...
Exact Solution of the Ising Model on Group Lattices of Genus $g>1$ (1996)
Regge, Tullio, Zecchina, Riccardo
We discuss how to apply the dimer method to Ising models on group lattices having non trivial topological genus $g$. We find that the use of group extension and the existence of both external and...
The Entropy of the K-Satisfiability Problem (1996)
Monasson, Remi, Zecchina, Riccardo
The threshold behaviour of the K-Satisfiability problem is studied in the framework of the statistical mechanics of random diluted systems. We find that at the transition the entropy is finite and...
Learning and generalization theories of large committee--machines (1996)
Monasson, Remi, Zecchina, Riccardo
The study of the distribution of volumes associated to the internal representations of learning examples allows us to derive the critical learning capacity ($\alpha_c=\frac{16}{\pi} \sqrt{\ln K}$) of...
Phase transition and search cost in the 2+p-sat problem (1996)
Riccardo Zecchina, Scott Kirkpatrick, Bart Selman, Lidror Troyansky
We give analytical and numerical results concerning a new Satisfiability problem for random Boolean expressions. Our model smoothly interpolates between the polynomial 2--SAT problem and the...
Phase Transition and Search Cost in the 2+p--SAT Problem (1996)
Riccardo Zecchina, Scott Kirkpatrick, Bart Selman, Lidror Troyansky
this paper, we give a preliminary discussion of a new SAT model, hereafter referred to as 2+p--SAT model. The model interpolates smoothly between 2--SAT and 3--SAT, and allows us to address the above...
Phase Transition and Search Cost in the 2+p-SAT Problem (1996)
Rémi Monasson, Riccardo Zecchina, Scott Kirkpatric, Bart Selman, Lidror Troyansky
this paper, we give a preliminary discussion of a new SAT model, hereafter referred to as 2+p--SAT model. The model interpolates smoothly between 2--SAT and 3--SAT, and allows us to address the above...
Learning and Generalization Theories of Large Committee-Machines (1996)
Rémi Monasson, Riccardo Zecchina
The study of the distribution of volumes associated to the internal representations of learning examples allows us to derive the critical learning capacity (ff c = 16 ß p ln K) of large committee...
Rémi Monasson, Riccardo Zecchina
We analytically derive the geometrical structure of the weight space in multilayer neural networks (MLN), in terms of the volumes of couplings associated to the internal representations of the...
Response Functions Improving Performance in Analog Attractor Neural Networks (1994)
Brunel, Nicolas, Zecchina, Riccardo
In the context of attractor neural networks, we study how the equilibrium analog neural activities, reached by the network dynamics during memory retrieval, may improve storage performance by...
Efficient supervised learning in networks with binary synapses
Baldassi, Carlo, Braunstein, Alfredo, Brunel, Nicolas, Zecchina, Riccardo
Recent experimental studies indicate that synaptic changes induced by neuronal activity are discrete jumps between a small number of stable states. Learning in systems with discrete synapses is known...
Statistical mechanics of asset markets with private information
Johannes Berg, Matteo Marsili, Aldo Rustichini, Riccardo Zecchina
Traders in a market typically have widely different, private information on the return of an asset. The equilibrium price of the asset may reflect this information more accurately if the number of...
Statistical mechanics of combinatorial auctions
Tobias Galla, Michele Leone, Matteo Marsili, Mauro Sellitto, Martin Weigt, Riccardo Zecchina
Combinatorial auctions are formulated as frustrated lattice gases on sparse random graphs, allowing the determination of the optimal revenue by methods of statistical physics. Transitions between...