We advance the Cohn-Umans framework for developing fast matrix multiplication algorithms. We introduce, analyze, and search for a new subclass of strong uniquely solvable puzzles (SUSP), which we call simplifiable SUSPs. We show that these puzzles are efficiently verifiable, which remains an open question for general SUSPs. We also show that individual simplifiable SUSPs can achieve the same strength of bounds on the matrix multiplication exponent $\omega$ that infinite families of SUSPs can. We report on the construction, by computer search, of larger SUSPs than previously known for small width. This, combined with our tighter analysis, strengthens the upper bound on the matrix multiplication exponent from $2.66$ to $2.505$ obtainable via this computational approach, and nears the results of the handcrafted constructions of Cohn et al.

There is an increased demand for techniques that can be used to evaluate local statistical quantities such as local magnetizations and local susceptibilities(covariances) of spin systems with finite sizes in statistical physics as well as in other scientific fields. This is because the use and application of Markov random fields and probabilistic operations is widely prevalent in many areas, particularly in the field of information sciences [1, 2]. Linear response methods have been used to approximately evaluate pair correlations between non-nearest pairs by combining an advanced mean-field method, particularly the cluster variation method, with the linear response theory [3, 4]. In the current decade, a suitable technique called susceptibility propagation (SusP) (also called a variational linear response in the field of information sciences), has been developed to compute the local susceptibilities of Markov random fields [5-8]. In general, SusPs are constructed by combining belief propagation algorithms and linear response methods. Belief propagation algorithms are one of the most popular message-passing type of algorithms that is used to approximately compute local magnetizations of Markov random fields [9], and they are equivalent to Bethe approximations [10] used in statistical physics [11, 12]. It is known that SusPs can be used to compute local susceptibilities with a high degree of accuracy because linear response methods partially restore the effects of loops of networks that are neglected in the Bethe approximations[13]. SusPs have the following inconsistency due to approximation.