Pedro Hack

Although belief propagation is a useful inference tool in several network-based contexts given its speed, its precision deteriorates when encountering loops. Generalized belief propagation (GBP) was introduced around two decades ago to mitigate this issue. However, it did not become widely used since it did not provide an explicit algorithm applicable to any network. This only changed recently, with the introduction of the first explicit and general version of GBP for networks, the Cantwell–Newman (CN)-method, which remained until now the only algorithm with such properties. Here, we provide a family of algorithms with these characteristics. We begin by considering the case where the network only has short loops. In this scenario, we improve on the CN-method by developing a algorithm with optimal time complexity, the NIB-method. We then consider networks that also have long loops. In this context, we show that the NIB-method provides advantages compared to the CN-method: it is faster for the networks where the CN-method is expected to work well, and it is applicable to more networks, i.e. highly dense networks. In general, both the CN-method and the family algorithms introduced here become non-equivalent approximations, and they can provide different levels of accuracy when applied to the same network, as we show numerically using two artificial networks. This discrepancy can have important practical implications, as we discuss in the context of decoding and error correction.

Elementary thermal operations are thermal operations that act non-trivially on at most two energy levels of a system at the same time. They were recently introduced in order to bring thermal operations closer to experimental feasibility. A key question to address is whether any thermal operation could be realized via elementary ones, that is, whether elementary thermal operations are universal. This was shown to be false in general, although the extent to which elementary thermal operations are universal remained unknown. Here, we characterize their universality in both the sense described above and a weaker one, where we do not require them to decompose any thermal operation, but to be able to reproduce any input–output pair connected via thermal operations. Moreover, we do so for the two variants of elementary thermal operations that have been proposed, one where only deterministic protocols are allowed and one where protocols can be conditioned via the realization of a random variable, and provide algorithms to emulate thermal operations whenever their elementary counterparts are (weakly or not) universal. Lastly, we show that non-deterministic protocols reproduce thermal operations better than deterministic ones in most scenarios, even when they are not universal. Along the way, we relate elementary thermal operations to random walks on graphs.

Majorization is a fundamental model of uncertainty with several applications in areas ranging from thermodynamics to entanglement theory, and constitutes one of the pillars of the resource-theoretic approach to physics. Here, we improve on its relation to measurement apparatuses. In particular, after discussing what the proper notion of second law in this scenario is, we show that, for a sufficiently large state space, any family of entropy-like functions constituting a second law must be countably infinite. Moreover, we provide an analogous result for a variation of majorization known as thermo-majorization which, in fact, does not require any constraint on the state space provided the equilibrium distribution is not uniform. Finally, we discuss the applicability of our results to molecular diffusion and catalytic majorization. In this regard, we consider a variation of majorization used in plasma physics as a model of molecular diffusion and show that no finite family of entropy-like functions constituting a second law of molecular diffusion exists. Moreover, we show how our results are useful when dealing with a conjecture regarding catalytic majorization (i.e. trumping). In particular, we show that the sort of characterizations of trumping that have been considered before require an infinite family of real-valued functions.

Computability on uncountable sets has no standard formalization, unlike that on countable sets, which is given by Turing machines. Some of the approaches to define computability in these sets rely on order-theoretic structures to translate such notions from Turing machines to uncountable spaces. Since these machines are used as a baseline for computability in these approaches, countability restrictions on the ordered structures are fundamental. Here, we show several relations between the usual countability restrictions in order-theoretic theories of computability and some more common order-theoretic countability constraints, like order density properties and functional characterizations of the order structure in terms of multi-utilities. As a result, we show how computability can be introduced in some order structures via countability order density and multi-utility constraints.

We define common thermodynamic concepts purely within the framework of general Markov chains and derive Jarzynski’s equality and Crooks’ fluctuation theorem in this setup. In particular, we regard the discrete-time case, which leads to an asymmetry in the definition of work that appears in the usual formulation of Crooks’ fluctuation theorem. We show how this asymmetry can be avoided with an additional condition regarding the energy protocol. The general formulation in terms of Markov chains allows transferring the results to other application areas outside of physics. Here, we discuss how this framework can be applied in the context of decision-making. This involves the definition of the relevant quantities, the assumptions that need to be made for the different fluctuation theorems to hold, as well as the consideration of discrete trajectories instead of the continuous trajectories, which are relevant in physics.

The study of complexity and optimization in decision theory involves both partial and complete characterizations of preferences over decision spaces in terms of real-valued monotones. With this motivation, and following the recent introduction of new classes of monotones, like injective monotones or strict monotone multi-utilities, we present the classification of preordered spaces in terms of both the existence and cardinality of real-valued monotones and the cardinality of the quotient space. In particular, we take advantage of a characterization of real-valued monotones in terms of separating families of increasing sets to obtain a more complete classification consisting of classes that are strictly different from each other. As a result, we gain new insight into both complexity and optimization, and clarify their interplay in preordered spaces.

We introduce a new class of real-valued monotones in preordered spaces, injective monotones. We show that the class of preorders for which they exist lies in between the class of preorders with strict monotones and preorders with countable multi-utilities, improving upon the known classification of preordered spaces through real-valued monotones. We extend several well-known results for strict monotones (Richter–Peleg functions) to injective monotones, we provide a construction of injective monotones from countable multi-utilities, and relate injective monotones to classic results concerning Debreu denseness and order separability. Along the way, we connect our results to Shannon entropy and the uncertainty preorder, obtaining new insights into how they are related. In particular, we show how injective monotones can be used to generalize some appealing properties of Jaynes’ maximum entropy principle, which is considered a basis for statistical inference and serves as a justification for many regularization techniques that appear throughout machine learning and decision theory.