Abstract. Isomanifolds are the generalization of isosurfaces to arbitrary dimension and codimension, i.e., submanifolds of [Formula: see text] defined as the zero set of some multivariate multivalued smooth function [Formula: see text], where [Formula: see text] is the intrinsic dimension of the manifold. A natural way to approximate a smooth isomanifold [Formula: see text] is to consider its piecewise linear (PL) approximation [Formula: see text] based on a triangulation [Formula: see text] of the ambient space [Formula: see text]. In this paper, we describe a simple algorithm to trace isomanifolds from a given starting point. The algorithm works for arbitrary dimensions [Formula: see text] and [Formula: see text], and any precision [Formula: see text]. Our main result is that, when [Formula: see text] (or [Formula: see text]) has bounded complexity, the complexity of the algorithm is polynomial in [Formula: see text] and [Formula: see text] (and unavoidably exponential in [Formula: see text]). Since it is known that for [Formula: see text], [Formula: see text] is [Formula: see text]-close and isotopic to [Formula: see text], our algorithm produces a faithful PL-approximation of isomanifolds of bounded complexity in time polynomial in [Formula: see text]. Combining this algorithm with dimensionality reduction techniques, the dependency on [Formula: see text] in the size of [Formula: see text] can be completely removed with high probability. We also show that the algorithm can handle isomanifolds with boundary and, more generally, isostratifolds. The algorithm for isomanifolds with boundary has been implemented and experimental results are reported, showing that it is practical and can handle cases that are far ahead of the state-of-the-art.

International audience

Abstract We quantise Whitney’s construction to prove the existence of a triangulation for any $$C^2$$ C2 manifold, so that we get an algorithm with explicit bounds. We also give a new elementary proof, which is completely geometric.

Nine years before Snapchat and its ephemeral messages, Aumann, Ding, and Rabin introduced the idea of everlasting security: an encryption that could not be decrypted after a certain date, no matter the adversary's computing power. Their method is efficient but not adapted to real-life constraints and cannot effectively be used today. In this paper we look at potential entropy sources available today, and propose a new solution that makes use of the already existing communications from pornography distribution networks, and look at its social implications. The method proposed has multiple advantages stemming from the fact that pornography is shameful in most societies, and it is usable off-the-shelf by individuals with limited technical skills, although it still requires some effort.