TY - CONF AB - Proofs of space (PoS) were suggested as more ecological and economical alternative to proofs of work, which are currently used in blockchain designs like Bitcoin. The existing PoS are based on rather sophisticated graph pebbling lower bounds. Much simpler and in several aspects more efficient schemes based on inverting random functions have been suggested, but they don’t give meaningful security guarantees due to existing time-memory trade-offs. In particular, Hellman showed that any permutation over a domain of size N can be inverted in time T by an algorithm that is given S bits of auxiliary information whenever (Formula presented). For functions Hellman gives a weaker attack with S2· T≈ N2 (e.g., S= T≈ N2/3). To prove lower bounds, one considers an adversary who has access to an oracle f: [ N] → [N] and can make T oracle queries. The best known lower bound is S· T∈ Ω(N) and holds for random functions and permutations. We construct functions that provably require more time and/or space to invert. Specifically, for any constant k we construct a function [N] → [N] that cannot be inverted unless Sk· T∈ Ω(Nk) (in particular, S= T≈ (Formula presented). Our construction does not contradict Hellman’s time-memory trade-off, because it cannot be efficiently evaluated in forward direction. However, its entire function table can be computed in time quasilinear in N, which is sufficient for the PoS application. Our simplest construction is built from a random function oracle g: [N] × [N] → [ N] and a random permutation oracle f: [N] → N] and is defined as h(x) = g(x, x′) where f(x) = π(f(x′)) with π being any involution without a fixed point, e.g. flipping all the bits. For this function we prove that any adversary who gets S bits of auxiliary information, makes at most T oracle queries, and inverts h on an ϵ fraction of outputs must satisfy S2· T∈ Ω(ϵ2N2). AU - Abusalah, Hamza M AU - Alwen, Joel F AU - Cohen, Bram AU - Khilko, Danylo AU - Pietrzak, Krzysztof Z AU - Reyzin, Leonid ID - 559 SN - 978-331970696-2 TI - Beyond Hellman’s time-memory trade-offs with applications to proofs of space VL - 10625 ER - TY - JOUR AB - For large random matrices X with independent, centered entries but not necessarily identical variances, the eigenvalue density of XX* is well-approximated by a deterministic measure on ℝ. We show that the density of this measure has only square and cubic-root singularities away from zero. We also extend the bulk local law in [5] to the vicinity of these singularities. AU - Alt, Johannes ID - 550 JF - Electronic Communications in Probability SN - 1083589X TI - Singularities of the density of states of random Gram matrices VL - 22 ER - TY - CONF AB - Despite researchers’ efforts in the last couple of decades, reachability analysis is still a challenging problem even for linear hybrid systems. Among the existing approaches, the most practical ones are mainly based on bounded-time reachable set over-approximations. For the purpose of unbounded-time analysis, one important strategy is to abstract the original system and find an invariant for the abstraction. In this paper, we propose an approach to constructing a new kind of abstraction called conic abstraction for affine hybrid systems, and to computing reachable sets based on this abstraction. The essential feature of a conic abstraction is that it partitions the state space of a system into a set of convex polyhedral cones which is derived from a uniform conic partition of the derivative space. Such a set of polyhedral cones is able to cut all trajectories of the system into almost straight segments so that every segment of a reach pipe in a polyhedral cone tends to be straight as well, and hence can be over-approximated tightly by polyhedra using similar techniques as HyTech or PHAVer. In particular, for diagonalizable affine systems, our approach can guarantee to find an invariant for unbounded reachable sets, which is beyond the capability of bounded-time reachability analysis tools. We implemented the approach in a tool and experiments on benchmarks show that our approach is more powerful than SpaceEx and PHAVer in dealing with diagonalizable systems. AU - Bogomolov, Sergiy AU - Giacobbe, Mirco AU - Henzinger, Thomas A AU - Kong, Hui ID - 647 SN - 978-331965764-6 TI - Conic abstractions for hybrid systems VL - 10419 ER - TY - CONF AB - Template polyhedra generalize intervals and octagons to polyhedra whose facets are orthogonal to a given set of arbitrary directions. They have been employed in the abstract interpretation of programs and, with particular success, in the reachability analysis of hybrid automata. While previously, the choice of directions has been left to the user or a heuristic, we present a method for the automatic discovery of directions that generalize and eliminate spurious counterexamples. We show that for the class of convex hybrid automata, i.e., hybrid automata with (possibly nonlinear) convex constraints on derivatives, such directions always exist and can be found using convex optimization. We embed our method inside a CEGAR loop, thus enabling the time-unbounded reachability analysis of an important and richer class of hybrid automata than was previously possible. We evaluate our method on several benchmarks, demonstrating also its superior efficiency for the special case of linear hybrid automata. AU - Bogomolov, Sergiy AU - Frehse, Goran AU - Giacobbe, Mirco AU - Henzinger, Thomas A ID - 631 SN - 978-366254576-8 TI - Counterexample guided refinement of template polyhedra VL - 10205 ER - TY - JOUR AB - We show that matrix elements of functions of N × N Wigner matrices fluctuate on a scale of order N−1/2 and we identify the limiting fluctuation. Our result holds for any function f of the matrix that has bounded variation thus considerably relaxing the regularity requirement imposed in [7, 11]. AU - Erdös, László AU - Schröder, Dominik J ID - 1144 JF - Electronic Communications in Probability TI - Fluctuations of functions of Wigner matrices VL - 21 ER - TY - JOUR AB - Color texture reproduction in 3D printing commonly ignores volumetric light transport (cross-talk) between surface points on a 3D print. Such light diffusion leads to significant blur of details and color bleeding, and is particularly severe for highly translucent resin-based print materials. Given their widely varying scattering properties, this cross-talk between surface points strongly depends on the internal structure of the volume surrounding each surface point. Existing scattering-aware methods use simplified models for light diffusion, and often accept the visual blur as an immutable property of the print medium. In contrast, our work counteracts heterogeneous scattering to obtain the impression of a crisp albedo texture on top of the 3D print, by optimizing for a fully volumetric material distribution that preserves the target appearance. Our method employs an efficient numerical optimizer on top of a general Monte-Carlo simulation of heterogeneous scattering, supported by a practical calibration procedure to obtain scattering parameters from a given set of printer materials. Despite the inherent translucency of the medium, we reproduce detailed surface textures on 3D prints. We evaluate our system using a commercial, five-tone 3D print process and compare against the printer’s native color texturing mode, demonstrating that our method preserves high-frequency features well without having to compromise on color gamut. AU - Elek, Oskar AU - Sumin, Denis AU - Zhang, Ran AU - Weyrich, Tim AU - Myszkowski, Karol AU - Bickel, Bernd AU - Wilkie, Alexander AU - Krivanek, Jaroslav ID - 486 IS - 6 JF - ACM Transactions on Graphics SN - 07300301 TI - Scattering-aware texture reproduction for 3D printing VL - 36 ER - TY - CONF AB - For many cryptographic primitives, it is relatively easy to achieve selective security (where the adversary commits a-priori to some of the choices to be made later in the attack) but appears difficult to achieve the more natural notion of adaptive security (where the adversary can make all choices on the go as the attack progresses). A series of several recent works shows how to cleverly achieve adaptive security in several such scenarios including generalized selective decryption (Panjwani, TCC ’07 and Fuchsbauer et al., CRYPTO ’15), constrained PRFs (Fuchsbauer et al., ASIACRYPT ’14), and Yao garbled circuits (Jafargholi and Wichs, TCC ’16b). Although the above works expressed vague intuition that they share a common technique, the connection was never made precise. In this work we present a new framework that connects all of these works and allows us to present them in a unified and simplified fashion. Moreover, we use the framework to derive a new result for adaptively secure secret sharing over access structures defined via monotone circuits. We envision that further applications will follow in the future. Underlying our framework is the following simple idea. It is well known that selective security, where the adversary commits to n-bits of information about his future choices, automatically implies adaptive security at the cost of amplifying the adversary’s advantage by a factor of up to 2n. However, in some cases the proof of selective security proceeds via a sequence of hybrids, where each pair of adjacent hybrids locally only requires some smaller partial information consisting of m ≪ n bits. The partial information needed might be completely different between different pairs of hybrids, and if we look across all the hybrids we might rely on the entire n-bit commitment. Nevertheless, the above is sufficient to prove adaptive security, at the cost of amplifying the adversary’s advantage by a factor of only 2m ≪ 2n. In all of our examples using the above framework, the different hybrids are captured by some sort of a graph pebbling game and the amount of information that the adversary needs to commit to in each pair of hybrids is bounded by the maximum number of pebbles in play at any point in time. Therefore, coming up with better strategies for proving adaptive security translates to various pebbling strategies for different types of graphs. AU - Jafargholi, Zahra AU - Kamath Hosdurg, Chethan AU - Klein, Karen AU - Komargodski, Ilan AU - Pietrzak, Krzysztof Z AU - Wichs, Daniel ED - Katz, Jonathan ED - Shacham, Hovav ID - 637 SN - 978-331963687-0 TI - Be adaptive avoid overcommitting VL - 10401 ER - TY - GEN AB - Mathematica notebooks used to generate figures. AU - Etheridge, Alison AU - Barton, Nicholas H ID - 9842 TI - Data for: Establishment in a new habitat by polygenic adaptation ER - TY - THES AB - Restriction-modification (RM) represents the simplest and possibly the most widespread mechanism of self/non-self discrimination in nature. In order to provide bacteria with immunity against bacteriophages and other parasitic genetic elements, RM systems rely on a balance between two enzymes: the restriction enzyme, which cleaves non-self DNA at specific restriction sites, and the modification enzyme, which tags the host’s DNA as self and thus protects it from cleavage. In this thesis, I use population and single-cell level experiments in combination with mathematical modeling to study different aspects of the interplay between RM systems, bacteria and bacteriophages. First, I analyze how mutations in phage restriction sites affect the probability of phage escape – an inherently stochastic process, during which phages accidently get modified instead of restricted. Next, I use single-cell experiments to show that RM systems can, with a low probability, attack the genome of their bacterial host and that this primitive form of autoimmunity leads to a tradeoff between the evolutionary cost and benefit of RM systems. Finally, I investigate the nature of interactions between bacteria, RM systems and temperate bacteriophages to find that, as a consequence of phage escape and its impact on population dynamics, RM systems can promote acquisition of symbiotic bacteriophages, rather than limit it. The results presented here uncover new fundamental biological properties of RM systems and highlight their importance in the ecology and evolution of bacteria, bacteriophages and their interactions. AU - Pleska, Maros ID - 202 SN - 2663-337X TI - Biology of restriction-modification systems at the single-cell and population level ER - TY - THES AB - The main objects considered in the present work are simplicial and CW-complexes with vertices forming a random point cloud. In particular, we consider a Poisson point process in R^n and study Delaunay and Voronoi complexes of the first and higher orders and weighted Delaunay complexes obtained as sections of Delaunay complexes, as well as the Čech complex. Further, we examine theDelaunay complex of a Poisson point process on the sphere S^n, as well as of a uniform point cloud, which is equivalent to the convex hull, providing a connection to the theory of random polytopes. Each of the complexes in question can be endowed with a radius function, which maps its cells to the radii of appropriately chosen circumspheres, called the radius of the cell. Applying and developing discrete Morse theory for these functions, joining it together with probabilistic and sometimes analytic machinery, and developing several integral geometric tools, we aim at getting the distributions of circumradii of typical cells. For all considered complexes, we are able to generalize and obtain up to constants the distribution of radii of typical intervals of all types. In low dimensions the constants can be computed explicitly, thus providing the explicit expressions for the expected numbers of cells. In particular, it allows to find the expected density of simplices of every dimension for a Poisson point process in R^4, whereas the result for R^3 was known already in 1970's. AU - Nikitenko, Anton ID - 6287 SN - 2663-337X TI - Discrete Morse theory for random complexes ER -