Typical case behaviour of spin systems in random graph and composite ensembles

Abstract

This thesis includes analysis of disordered spin ensembles corresponding to Exact Cover, a multi-access channel problem, and composite models combining sparse and dense interactions. The satisfiability problem in Exact Cover is addressed using a statistical analysis of a simple branch and bound algorithm. The algorithm can be formulated in the large system limit as a branching process, for which critical properties can be analysed. Far from the critical point a set of differential equations may be used to model the process, and these are solved by numerical integration and exact bounding methods. The multi-access channel problem is formulated as an equilibrium statistical physics problem for the case of bit transmission on a channel with power control and synchronisation. A sparse code division multiple access method is considered and the optimal detection properties are examined in typical case by use of the replica method, and compared to detection performance achieved by iterative decoding methods. These codes are found to have phenomena closely resembling the well-understood dense codes. The composite model is introduced as an abstraction of canonical sparse and dense disordered spin models. The model includes couplings due to both dense and sparse topologies simultaneously. Through an exact replica analysis at high temperature, and variational approaches at low temperature, several phenomena uncharacteristic of either sparse or dense models are demonstrated. An extension of the composite interaction structure to a code division multiple access method is presented. The new type of codes are shown to outperform sparse and dense codes in some regimes both in optimal performance, and in performance achieved by iterative detection methods in finite systems.

Thesis

References in corpus (17)

• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• The Bethe lattice spin glass revisited
• Glass models on Bethe lattices
• Optimisation problems and replica symmetry breaking in finite connectivity spin-glasses
• Solving Constraint Satisfaction Problems through Belief Propagation-guided decimation
• Locked constraint satisfaction problems
• Improved message passing for inference in densely connected systems
• Sparsely-spread CDMA - a statistical mechanics based analysis
• Exactness of Belief Propagation for Some Graphical Models with Loops
• Stochastic Stability
• The Phase Transition in Exact Cover
• Replica-symmetric solutions of a dilute Ising ferromagnet in a random field
• A statistical-mechanical approach to CDMA multiuser detection: propagating beliefs in a densely connected graph
• Approximating satisfiability transition by suppressing fluctuations
• Composite CDMA - A statistical mechanics analysis
• Inference by replication in densely connected systems
• Optimal sparse CDMA detection at high load

Cited by in corpus (2)

• Composite CDMA - A statistical mechanics analysis
• Optimal sparse CDMA detection at high load