@inproceedings{193,
abstract = {We show attacks on five data-independent memory-hard functions (iMHF) that were submitted to the password hashing competition (PHC). Informally, an MHF is a function which cannot be evaluated on dedicated hardware, like ASICs, at significantly lower hardware and/or energy cost than evaluating a single instance on a standard single-core architecture. Data-independent means the memory access pattern of the function is independent of the input; this makes iMHFs harder to construct than data-dependent ones, but the latter can be attacked by various side-channel attacks. Following [Alwen-Blocki'16], we capture the evaluation of an iMHF as a directed acyclic graph (DAG). The cumulative parallel pebbling complexity of this DAG is a measure for the hardware cost of evaluating the iMHF on an ASIC. Ideally, one would like the complexity of a DAG underlying an iMHF to be as close to quadratic in the number of nodes of the graph as possible. Instead, we show that (the DAGs underlying) the following iMHFs are far from this bound: Rig.v2, TwoCats and Gambit each having an exponent no more than 1.75. Moreover, we show that the complexity of the iMHF modes of the PHC finalists Pomelo and Lyra2 have exponents at most 1.83 and 1.67 respectively. To show this we investigate a combinatorial property of each underlying DAG (called its depth-robustness. By establishing upper bounds on this property we are then able to apply the general technique of [Alwen-Block'16] for analyzing the hardware costs of an iMHF.},
author = {Alwen, Joel F and Gazi, Peter and Kamath Hosdurg, Chethan and Klein, Karen and Osang, Georg F and Pietrzak, Krzysztof Z and Reyzin, Lenoid and Rolinek, Michal and Rybar, Michal},
booktitle = {Proceedings of the 2018 on Asia Conference on Computer and Communication Security},
location = {Incheon, Republic of Korea},
pages = {51 -- 65},
publisher = {ACM},
title = {{On the memory hardness of data independent password hashing functions}},
doi = {10.1145/3196494.3196534},
year = {2018},
}
@article{458,
abstract = {We consider congruences of straight lines in a plane with the combinatorics of the square grid, with all elementary quadrilaterals possessing an incircle. It is shown that all the vertices of such nets (we call them incircular or IC-nets) lie on confocal conics. Our main new results are on checkerboard IC-nets in the plane. These are congruences of straight lines in the plane with the combinatorics of the square grid, combinatorially colored as a checkerboard, such that all black coordinate quadrilaterals possess inscribed circles. We show how this larger class of IC-nets appears quite naturally in Laguerre geometry of oriented planes and spheres and leads to new remarkable incidence theorems. Most of our results are valid in hyperbolic and spherical geometries as well. We present also generalizations in spaces of higher dimension, called checkerboard IS-nets. The construction of these nets is based on a new 9 inspheres incidence theorem.},
author = {Akopyan, Arseniy and Bobenko, Alexander},
journal = {Transactions of the American Mathematical Society},
number = {4},
pages = {2825 -- 2854},
publisher = {American Mathematical Society},
title = {{Incircular nets and confocal conics}},
doi = {10.1090/tran/7292},
volume = {370},
year = {2018},
}
@article{530,
abstract = {Inclusion–exclusion is an effective method for computing the volume of a union of measurable sets. We extend it to multiple coverings, proving short inclusion–exclusion formulas for the subset of Rn covered by at least k balls in a finite set. We implement two of the formulas in dimension n=3 and report on results obtained with our software.},
author = {Edelsbrunner, Herbert and Iglesias Ham, Mabel},
journal = {Computational Geometry: Theory and Applications},
pages = {119 -- 133},
publisher = {Elsevier},
title = {{Multiple covers with balls I: Inclusion–exclusion}},
doi = {10.1016/j.comgeo.2017.06.014},
volume = {68},
year = {2018},
}
@phdthesis{201,
abstract = {We describe arrangements of three-dimensional spheres from a geometrical and topological point of view. Real data (fitting this setup) often consist of soft spheres which show certain degree of deformation while strongly packing against each other. In this context, we answer the following questions: If we model a soft packing of spheres by hard spheres that are allowed to overlap, can we measure the volume in the overlapped areas? Can we be more specific about the overlap volume, i.e. quantify how much volume is there covered exactly twice, three times, or k times? What would be a good optimization criteria that rule the arrangement of soft spheres while making a good use of the available space? Fixing a particular criterion, what would be the optimal sphere configuration? The first result of this thesis are short formulas for the computation of volumes covered by at least k of the balls. The formulas exploit information contained in the order-k Voronoi diagrams and its closely related Level-k complex. The used complexes lead to a natural generalization into poset diagrams, a theoretical formalism that contains the order-k and degree-k diagrams as special cases. In parallel, we define different criteria to determine what could be considered an optimal arrangement from a geometrical point of view. Fixing a criterion, we find optimal soft packing configurations in 2D and 3D where the ball centers lie on a lattice. As a last step, we use tools from computational topology on real physical data, to show the potentials of higher-order diagrams in the description of melting crystals. The results of the experiments leaves us with an open window to apply the theories developed in this thesis in real applications.},
author = {Iglesias Ham, Mabel},
pages = {171},
publisher = {IST Austria},
title = {{Multiple covers with balls}},
doi = {10.15479/AT:ISTA:th_1026},
year = {2018},
}
@article{106,
abstract = {The goal of this article is to introduce the reader to the theory of intrinsic geometry of convex surfaces. We illustrate the power of the tools by proving a theorem on convex surfaces containing an arbitrarily long closed simple geodesic. Let us remind ourselves that a curve in a surface is called geodesic if every sufficiently short arc of the curve is length minimizing; if, in addition, it has no self-intersections, we call it simple geodesic. A tetrahedron with equal opposite edges is called isosceles. The axiomatic method of Alexandrov geometry allows us to work with the metrics of convex surfaces directly, without approximating it first by a smooth or polyhedral metric. Such approximations destroy the closed geodesics on the surface; therefore it is difficult (if at all possible) to apply approximations in the proof of our theorem. On the other hand, a proof in the smooth or polyhedral case usually admits a translation into Alexandrov’s language; such translation makes the result more general. In fact, our proof resembles a translation of the proof given by Protasov. Note that the main theorem implies in particular that a smooth convex surface does not have arbitrarily long simple closed geodesics. However we do not know a proof of this corollary that is essentially simpler than the one presented below.},
author = {Akopyan, Arseniy and Petrunin, Anton},
journal = {Mathematical Intelligencer},
number = {3},
pages = {26 -- 31},
publisher = {Springer},
title = {{Long geodesics on convex surfaces}},
doi = {10.1007/s00283-018-9795-5},
volume = {40},
year = {2018},
}