ﻻ يوجد ملخص باللغة العربية
The graph theoretic concept of maximal independent set arises in several practical problems in computer science as well as in game theory. A maximal independent set is defined by the set of occupied nodes that satisfy some packing and covering constraints. It is known that finding minimum and maximum-density maximal independent sets are hard optimization problems. In this paper, we use cavity method of statistical physics and Monte Carlo simulations to study the corresponding constraint satisfaction problem on random graphs. We obtain the entropy of maximal independent sets within the replica symmetric and one-step replica symmetry breaking frameworks, shedding light on the metric structure of the landscape of solutions and suggesting a class of possible algorithms. This is of particular relevance for the application to the study of strategic interactions in social and economic networks, where maximal independent sets correspond to pure Nash equilibria of a graphical game of public goods allocation.
Code Division Multiple Access (CDMA) in which the spreading code assignment to users contains a random element has recently become a cornerstone of CDMA research. The random element in the construction is particular attractive as it provides robustne
We propose a theory which describes the density relaxation of loosely packed, cohesionless granular material under mechanical tapping. Using the compactivity concept we develope a formalism of statistical mechanics which allows us to calculate the de
We study the quantum version of the random $K$-Satisfiability problem in the presence of the external magnetic field $Gamma$ applied in the transverse direction. We derive the replica-symmetric free energy functional within static approximation and t
We give a statistical-mechanical theory of stress transmission in disordered arrays of rigid grains with perfect friction. Starting from the equations of microscopic force and torque balance we derive the fundamental equations of stress equilibrium.
The cortex exhibits self-sustained highly-irregular activity even under resting conditions, whose origin and function need to be fully understood. It is believed that this can be described as an asynchronous state stemming from the balance between ex