Explore the vast range of titles available.

Although evidence supporting the feasibility of large-scale mobile health (mHealth) systems continues to grow, privacy protection remains an important implementation challenge. The potential scale of publicly available mHealth applications and the sensitive nature of the data involved will inevitably attract unwanted attention from adversarial actors seeking to compromise user privacy. Although privacy-preserving technologies such as federated learning (FL) and differential privacy (DP) offer strong theoretical guarantees, it is not clear how such technologies actually perform under real-world conditions. Using data from the University of Michigan Intern Health Study (IHS), we assessed the privacy protection capabilities of FL and DP against the trade-offs in the associated model's accuracy and training time. Using a simulated external attack on a target mHealth system, we aimed to measure the effectiveness of such an attack under various levels of privacy protection on the target system and measure the costs to the target system's performance associated with the chosen levels of privacy protection. A neural network classifier that attempts to predict IHS participant daily mood ecological momentary assessment score from sensor data served as our target system. An external attacker attempted to identify participants whose average mood ecological momentary assessment score is lower than the global average. The attack followed techniques in the literature, given the relevant assumptions about the abilities of the attacker. For measuring attack effectiveness, we collected attack success metrics (area under the curve [AUC], positive predictive value, and sensitivity), and for measuring privacy costs, we calculated the target model training time and measured the model utility metrics. Both sets of metrics are reported under varying degrees of privacy protection on the target. We found that FL alone does not provide adequate protection against the privacy attack proposed above, where the attacker's AUC in determining which participants exhibit lower than average mood is over 0.90 in the worst-case scenario. However, under the highest level of DP tested in this study, the attacker's AUC fell to approximately 0.59 with only a 10% point decrease in the target's R and a 43% increase in model training time. Attack positive predictive value and sensitivity followed similar trends. Finally, we showed that participants in the IHS most likely to require strong privacy protection are also most at risk from this particular privacy attack and subsequently stand to benefit the most from these privacy-preserving technologies. Our results demonstrated both the necessity of proactive privacy protection research and the feasibility of the current FL and DP methods implemented in a real mHealth scenario. Our simulation methods characterized the privacy-utility trade-off in our mHealth setup using highly interpretable metrics, providing a framework for future research into privacy-preserving technologies in data-driven health and medical applications.

Geometric constructions have been a topic of interest among mathematicians for centuries. The Euclidean tradition uses two instruments: a straightedge (ruler) and a compass. However, limited constructions have also been studied. The Mohr–Mascheroni theorem says that every construction using both instruments can be replaced by a construction of the same object that uses only a compass. (Obviously, a line cannot be drawn with a compass; we construct two distinct points on that line instead.) Another result, the Poncelet–Steiner theorem, says that in a construction using straightedge and compass, a single application of a compass suffices: if a circle with its center is given, then every straightedge–compass construction can be performed with only a straightedge. Today, such results are considered to belong to recreational mathematics, and they can be found in many books, such as [6], for example.

A nonnegative martingale with initial value equal to one measures evidence against a probabilistic hypothesis. The inverse of its value at some stopping time can be interpreted as a Bayes factor. If we exaggerate the evidence by considering the largest value attained so far by such a martingale, the exaggeration will be limited, and there are systematic ways to eliminate it. The inverse of the exaggerated value at some stopping time can be interpreted as a p-value. We give a simple characterization of all increasing functions that eliminate the exaggeration.

We establish a structure theorem for the family of Ammann A2 tilings of the plane. Using that theorem we show that every Ammann A2 tiling is self-similar in the sense of Solomyak (Discret Comput Geom 20:265–279, 1998). By the same techniques we show that Ammann A2 tilings are not robust in the sense of Durand et al. (J Comput Syst Sci 78(3):731–764, 2012).

Algorithmic randomness theory starts with a notion of an individual random object. To be reasonable, this notion should have some natural properties; in particular, an object should be random with respect to the image distribution F ( P ) (for some distribution P and some mapping F ) if and only if it has a P -random F -preimage. This result (for computable distributions and mappings, and Martin-Löf randomness) was known for a long time (folklore); for layerwise computable mappings it was mentioned in Hoyrup and Rojas ( 2009 , Proposition 5) (even for more general case of computable metric spaces). In this paper we provide a proof and discuss the related quantitative results and applications.

We present several applications of simple topological arguments (such as non-contractibility of a sphere and similar results) to Kolmogorov complexity. It turns out that discrete versions of these results can be used to prove the existence of strings with prescribed complexity with O (1)-precision (instead of usual O (log n )-precision). In particular, we improve an earlier result of M. Vyugin and show that for every n and for every string x of complexity at least n + O (log n ) there exists a string y such that both C ( x ∣ y ) and C ( y ∣ x ) are equal to n + O (1). We also show that for a given tuple of strings x i (assuming they are almost independent) there exists another string y such that the condition y makes the complexities of all x i twice smaller with O (1)-precision. The extended abstract of this paper was published in [ 6 ].

The definition of conditional probability in the case of continuous distributions (for almost all conditions) was an important step in the development of mathematical theory of probabilities. Can we define this notion in algorithmic probability theory for individual random conditions? Can we define randomness with respect to the conditional probability distributions? Can van Lambalgen’s theorem (relating randomness of a pair and its elements) be generalized to conditional probabilities? We discuss the developments in this direction. We present almost no new results trying to put known results into perspective and explain their proofs in a more intuitive way. We assume that the reader is familiar with basic notions of measure theory and algorithmic randomness (see, e.g., Shen et al. ??2013 or Shen ??2015 for a short introduction).

We prove the formula C ( a , b )= K ( a | C ( a , b ))+ C ( b | a , C ( a , b ))+ O (1) that expresses the plain complexity of a pair in terms of prefix-free and plain conditional complexities of its components.

Peter Gacs showed (Gacs 1974) that for every n there exists a bit string x of length n whose plain complexity C(x) has almost maximal conditional complexity relative to x. i.e.. C(C(x)|x) ≥ log n — log⁽²⁾ n — O(1). (Here log⁽²⁾ i= log log i.) Following Elena Kalinina (Kalinina 2011). we provide a simple game-based proof of this result: modifying her argument, we get a better (and tight) bound log n — O(1). We also show the same bound for prefix-free complexity. Robert Solovay showed (Solovay 1975) that infinitely many strings x have maximal plain complexity but not maximal prefix complexity (among the strings of the same length): for some c there exist infinitely many x such that |x| — C(x) ≤ c and |x| + K(|x|) — K(x) ≥ log ⁽²⁾ |x| — c log ⁽³⁾ |x|. In fact, the results of Solovay and Gacs are closely related. Using the result above, we provide a short roof for Solovay's result. We also generalize it by showing that for some c and for all n there are strings x of length n with n — C(x) ≤ c and n + K(n) — K(x) ≥ K(K(n)|n) - 3 K(K(K(n)|n)|n) — c. We also prove a close upper bound K(K(n)|n) + O(1). Finally, we provide a direct game proof for Joseph Miller's generalization (Miller 2006) of the same Solovay's theorem: if a co-enumerable set (a set with co-enumerable complement) contains for every length a string of this length, then it contains infinitely many strings x such that |x| + K(|x|) — K(x) ≥ log⁽²⁾ |x| — O(log⁽³⁾ |x|) .

Muchnik’s theorem about simple conditional descriptions states that for all strings a and b there exists a program p transforming a to b that has the least possible length and is simple conditional on  b . In this paper we present two new proofs of this theorem. The first one is based on the on-line matching algorithm for bipartite graphs. The second one, based on extractors, can be generalized to prove a version of Muchnik’s theorem for space-bounded Kolmogorov complexity. Another version of Muchnik’s theorem is proven for a resource-bounded variant of Kolmogorov complexity based on Arthur–Merlin protocols.