141 citations · 1.7k across the 117 of their papers we have counts for
10 papers · 1 filter
Statistical mechanics of the minimum vertex cover problem in stochastic block models
Masato Suzuki, Yoshiyuki Kabashima
The minimum vertex cover (Min-VC) problem is a well-known NP-hard problem. Earlier studies illustrate that the problem defined over the Erdös-Rényi random graph with a mean degree…
Relative species abundance of replicator dynamics with sparse interactions
Tomoyuki Obuchi, Yoshiyuki Kabashima, Kei Tokita
A theory of relative species abundance on sparsely-connected networks is presented by investigating the replicator dynamics with symmetric interactions. Sparseness of a network inv…
Finite size scaling of the de Almeida-Thouless instability in random sparse networks
Hisanao Takahashi, Federico Ricci-Tersenghi, Yoshiyuki Kabashima
We study, in random sparse networks, finite size scaling of the spin glass susceptibility , which is a proper measure of the de Almeida-Thouless (AT) instability of spi…
Survey propagation for the cascading Sourlas code
Jonathan PL Hatchett, Yoshiyuki Kabashima
We investigate how insights from statistical physics, namely survey propagation, can improve decoding of a particular class of sparse error correcting codes. We show that a recentl…
An LDPCC decoding algorithm based on Bowman-Levin approximation --Comparison with BP and CCCP--
Masato Inoue, Miho Komiya, Yoshiyuki Kabashima
Belief propagation (BP) and the concave convex procedure (CCCP) are both methods that utilize the Bethe free energy as a cost function and solve information processing tasks. We ha…
Statistical Mechanical Approach to Error Exponents of Lossy Data Compression
Tadaaki Hosaka, Yoshiyuki Kabashima
We present herein a scheme by which to accurately evaluate the error exponents of a lossy data compression problem, which characterize average probabilities over a code ensemble of…
Exact Analytic Continuation with Respect to the Replica Number in the Discrete Random Energy Model of Finite System Size
Kenzo Ogure, Yoshiyuki Kabashima
An expression for the moment of partition function valid for any finite system size and complex power is obtained for a simple spin glass model termed the {\em d…
Statistical mechanics of lossy data compression using a non-monotonic perceptron
T. Hosaka, Y. Kabashima, H. Nishimori
The performance of a lossy data compression scheme for uniformly biased Boolean messages is investigated via methods of statistical mechanics. Inspired by a formal similarity to th…
Statistical Mechanics of Broadcast Channels Using Low Density Parity Check Codes
Kazutaka Nakamura, Robert Morelos-Zaragoza, David Saad +1
We investigate the use of Gallager's low-density parity-check (LDPC) codes in a broadcast channel, one of the fundamental models in network information theory. Combining linear cod…
Statistical Mechanics of Low-Density Parity Check Error-Correcting Codes over Galois Fields
Kazutaka Nakamura, Yoshiyuki Kabashima, David Saad
A variation of low density parity check (LDPC) error correcting codes defined over Galois fields () is investigated using statistical physics. A code of this type is charact…