@article{6944,
abstract = {We study the problem of automatically detecting if a given multi-class classifier operates outside of its specifications (out-of-specs), i.e. on input data from a different distribution than what it was trained for. This is an important problem to solve on the road towards creating reliable computer vision systems for real-world applications, because the quality of a classifier’s predictions cannot be guaranteed if it operates out-of-specs. Previously proposed methods for out-of-specs detection make decisions on the level of single inputs. This, however, is insufficient to achieve low false positive rate and high false negative rates at the same time. In this work, we describe a new procedure named KS(conf), based on statistical reasoning. Its main component is a classical Kolmogorov–Smirnov test that is applied to the set of predicted confidence values for batches of samples. Working with batches instead of single samples allows increasing the true positive rate without negatively affecting the false positive rate, thereby overcoming a crucial limitation of single sample tests. We show by extensive experiments using a variety of convolutional network architectures and datasets that KS(conf) reliably detects out-of-specs situations even under conditions where other tests fail. It furthermore has a number of properties that make it an excellent candidate for practical deployment: it is easy to implement, adds almost no overhead to the system, works with any classifier that outputs confidence scores, and requires no a priori knowledge about how the data distribution could change.},
author = {Sun, Rémy and Lampert, Christoph},
issn = {1573-1405},
journal = {International Journal of Computer Vision},
publisher = {Springer Nature},
title = {{KS(conf): A light-weight test if a multiclass classifier operates outside of its specifications}},
doi = {10.1007/s11263-019-01232-x},
year = {2019},
}
@article{7093,
abstract = {In graph theory, as well as in 3-manifold topology, there exist several width-type parameters to describe how "simple" or "thin" a given graph or 3-manifold is. These parameters, such as pathwidth or treewidth for graphs, or the concept of thin position for 3-manifolds, play an important role when studying algorithmic problems; in particular, there is a variety of problems in computational 3-manifold topology - some of them known to be computationally hard in general - that become solvable in polynomial time as soon as the dual graph of the input triangulation has bounded treewidth.
In view of these algorithmic results, it is natural to ask whether every 3-manifold admits a triangulation of bounded treewidth. We show that this is not the case, i.e., that there exists an infinite family of closed 3-manifolds not admitting triangulations of bounded pathwidth or treewidth (the latter implies the former, but we present two separate proofs).
We derive these results from work of Agol, of Scharlemann and Thompson, and of Scharlemann, Schultens and Saito by exhibiting explicit connections between the topology of a 3-manifold M on the one hand and width-type parameters of the dual graphs of triangulations of M on the other hand, answering a question that had been raised repeatedly by researchers in computational 3-manifold topology. In particular, we show that if a closed, orientable, irreducible, non-Haken 3-manifold M has a triangulation of treewidth (resp. pathwidth) k then the Heegaard genus of M is at most 18(k+1) (resp. 4(3k+1)).},
author = {Huszár, Kristóf and Spreer, Jonathan and Wagner, Uli},
issn = {1920-180X},
journal = {Journal of Computational Geometry},
number = {2},
pages = {70–98},
publisher = {Computational Geometry Laborartoy},
title = {{On the treewidth of triangulated 3-manifolds}},
doi = {10.20382/JOGC.V10I2A5},
volume = {10},
year = {2019},
}
@inproceedings{6482,
abstract = {Computer vision systems for automatic image categorization have become accurate and reliable enough that they can run continuously for days or even years as components of real-world commercial applications. A major open problem in this context, however, is quality control. Good classification performance can only be expected if systems run under the specific conditions, in particular data distributions, that they were trained for. Surprisingly, none of the currently used deep network architectures have a built-in functionality that could detect if a network operates on data from a distribution it was not trained for, such that potentially a warning to the human users could be triggered. In this work, we describe KS(conf), a procedure for detecting such outside of specifications (out-of-specs) operation, based on statistical testing of the network outputs. We show by extensive experiments using the ImageNet, AwA2 and DAVIS datasets on a variety of ConvNets architectures that KS(conf) reliably detects out-of-specs situations. It furthermore has a number of properties that make it a promising candidate for practical deployment: it is easy to implement, adds almost no overhead to the system, works with all networks, including pretrained ones, and requires no a priori knowledge of how the data distribution could change. },
author = {Sun, Rémy and Lampert, Christoph},
isbn = {9783030129385},
issn = {0302-9743},
location = {Stuttgart, Germany},
pages = {244--259},
publisher = {Springer Nature},
title = {{KS(conf): A light-weight test if a ConvNet operates outside of Its specifications}},
doi = {10.1007/978-3-030-12939-2_18},
volume = {11269},
year = {2019},
}
@phdthesis{7132,
abstract = {A major challenge in neuroscience research is to dissect the circuits that orchestrate behavior in health and disease. Proteins from a wide range of non-mammalian species, such as microbial opsins, have been successfully transplanted to specific neuronal targets to override their natural communication patterns. The goal of our work is to manipulate synaptic communication in a manner that closely incorporates the functional intricacies of synapses by preserving temporal encoding (i.e. the firing pattern of the presynaptic neuron) and connectivity (i.e. target specific synapses rather than specific neurons). Our strategy to achieve this goal builds on the use of non-mammalian transplants to create a synthetic synapse. The mode of modulation comes from pre-synaptic uptake of a synthetic neurotransmitter (SN) into synaptic vesicles by means of a genetically targeted transporter selective for the SN. Upon natural vesicular release, exposure of the SN to the synaptic cleft will modify the post-synaptic potential through an orthogonal ligand gated ion channel. To achieve this goal we have functionally characterized a mixed cationic methionine-gated ion channel from Arabidopsis thaliana, designed a method to functionally characterize a synthetic transporter in isolated synaptic vesicles without the need for transgenic animals, identified and extracted multiple prokaryotic uptake systems that are substrate specific for methionine (Met), and established a primary/cell line co-culture system that would allow future combinatorial testing of this orthogonal transmitter-transporter-channel trifecta.
Synthetic synapses will provide a unique opportunity to manipulate synaptic communication while maintaining the electrophysiological integrity of the pre-synaptic cell. In this way, information may be preserved that was generated in upstream circuits and that could be essential for concerted function and information processing.},
author = {Mckenzie, Catherine},
issn = {2663-337X},
pages = {95},
publisher = {IST Austria},
title = {{Design and characterization of methods and biological components to realize synthetic neurotransmission}},
doi = {10.15479/at:ista:7132},
year = {2019},
}
@article{7144,
abstract = {PIN-FORMED (PIN) transporters mediate directional, intercellular movement of the phytohormone auxin in land plants. To elucidate the evolutionary origins of this developmentally crucial mechanism, we analysed the single PIN homologue of a simple green alga Klebsormidium flaccidum. KfPIN functions as a plasma membrane-localized auxin exporter in land plants and heterologous models. While its role in algae remains unclear, PIN-driven auxin export is probably an ancient and conserved trait within streptophytes.},
author = {Skokan, R and Medvecká, E and Viaene, T and Vosolsobě, S and Zwiewka, M and Müller, K and Skůpa, P and Karady, M and Zhang, Yuzhou and Janacek, DP and Hammes, UZ and Ljung, K and Nodzyński, T and Petrášek, J and Friml, Jiří},
issn = {2055-0278},
journal = {Nature Plants},
number = {11},
pages = {1114--1119},
publisher = {Springer Nature},
title = {{PIN-driven auxin transport emerged early in streptophyte evolution}},
doi = {10.1038/s41477-019-0542-5},
volume = {5},
year = {2019},
}
@article{7149,
abstract = {In recent years, many genes have been associated with chromatinopathies classified as “Cornelia de Lange Syndrome‐like.” It is known that the phenotype of these patients becomes less recognizable, overlapping to features characteristic of other syndromes caused by genetic variants affecting different regulators of chromatin structure and function. Therefore, Cornelia de Lange syndrome diagnosis might be arduous due to the seldom discordance between unexpected molecular diagnosis and clinical evaluation. Here, we review the molecular features of Cornelia de Lange syndrome, supporting the hypothesis that “CdLS‐like syndromes” are part of a larger “rare disease family” sharing multiple clinical features and common disrupted molecular pathways.},
author = {Avagliano, Laura and Parenti, Ilaria and Grazioli, Paolo and Di Fede, Elisabetta and Parodi, Chiara and Mariani, Milena and Kaiser, Frank J. and Selicorni, Angelo and Gervasini, Cristina and Massa, Valentina},
issn = {1399-0004},
journal = {Clinical Genetics},
publisher = {Wiley},
title = {{Chromatinopathies: A focus on Cornelia de Lange syndrome}},
doi = {10.1111/cge.13674},
year = {2019},
}
@inproceedings{11,
abstract = {We report on a novel strategy to derive mean-field limits of quantum mechanical systems in which a large number of particles weakly couple to a second-quantized radiation field. The technique combines the method of counting and the coherent state approach to study the growth of the correlations among the particles and in the radiation field. As an instructional example, we derive the Schrödinger–Klein–Gordon system of equations from the Nelson model with ultraviolet cutoff and possibly massless scalar field. In particular, we prove the convergence of the reduced density matrices (of the nonrelativistic particles and the field bosons) associated with the exact time evolution to the projectors onto the solutions of the Schrödinger–Klein–Gordon equations in trace norm. Furthermore, we derive explicit bounds on the rate of convergence of the one-particle reduced density matrix of the nonrelativistic particles in Sobolev norm.},
author = {Leopold, Nikolai K and Pickl, Peter},
location = {Munich, Germany},
pages = {185 -- 214},
publisher = {Springer},
title = {{Mean-field limits of particles in interaction with quantised radiation fields}},
doi = {10.1007/978-3-030-01602-9_9},
volume = {270},
year = {2018},
}
@article{124,
abstract = {By investigating the in situ chemical and O-isotope compositions of olivine in lightly sintered dust agglomerates from the early Solar System, we constrain their origins and the retention of dust in the protoplanetary disk. The grain sizes of silicates in these agglomeratic olivine (AO) chondrules indicate that the grain sizes of chondrule precursors in the Renazzo-like carbonaceous (CR) chondrites ranged from <1 to 80 µm. We infer this grain size range to be equivalent to the size range for dust in the early Solar System. AO chondrules may contain, but are not solely composed of, recycled fragments of earlier formed chondrules. They also contain 16O-rich olivine related to amoeboid olivine aggregates and represent the best record of chondrule-precursor materials. AO chondrules contain one or more large grains, sometimes similar to FeO-poor (type I) and/or FeO-rich (type II) chondrules, while others contain a type II chondrule core. These morphologies are consistent with particle agglomeration by electrostatic charging of grains during collision, a process that may explain solid agglomeration in the protoplanetary disk in the micrometer size regime. The petrographic, isotopic, and chemical compositions of AO chondrules are consistent with chondrule formation by large-scale shocks, bow shocks, and current sheets. The petrographic, isotopic, and chemical similarities between AO chondrules in CR chondrites and chondrule-like objects from comet 81P/Wild 2 indicate that comets contain AO chondrules. We infer that these AO chondrules likely formed in the inner Solar System and migrated to the comet forming region at least 3 Ma after the formation of the first Solar System solids. Observations made in this study imply that the protoplanetary disk retained a dusty disk at least ∼3.7 Ma after the formation of the first Solar System solids, longer than half of the dusty accretion disks observed around other stars.},
author = {Waitukaitis, Scott R and Schrader, Devin and Nagashima, Kazuhide and Davidson, Jemma and Mccoy, Timothy and Conolly Jr, Harold and Lauretta, Dante},
journal = {Geochimica et Cosmochimica Acta},
pages = {405 -- 421},
publisher = {Elsevier},
title = {{The retention of dust in protoplanetary disks: evidence from agglomeration olivine chondrules from the outer solar system}},
doi = {10.1016/j.gca.2017.12.014},
volume = {223},
year = {2018},
}
@article{136,
abstract = {Recent studies suggest that unstable, nonchaotic solutions of the Navier-Stokes equation may provide deep insights into fluid turbulence. In this article, we present a combined experimental and numerical study exploring the dynamical role of unstable equilibrium solutions and their invariant manifolds in a weakly turbulent, electromagnetically driven, shallow fluid layer. Identifying instants when turbulent evolution slows down, we compute 31 unstable equilibria of a realistic two-dimensional model of the flow. We establish the dynamical relevance of these unstable equilibria by showing that they are closely visited by the turbulent flow. We also establish the dynamical relevance of unstable manifolds by verifying that they are shadowed by turbulent trajectories departing from the neighborhoods of unstable equilibria over large distances in state space.},
author = {Suri, Balachandra and Tithof, Jeffrey and Grigoriev, Roman and Schatz, Michael},
journal = {Physical Review E},
number = {2},
publisher = {American Physiological Society},
title = {{Unstable equilibria and invariant manifolds in quasi-two-dimensional Kolmogorov-like flow}},
doi = {10.1103/PhysRevE.98.023105},
volume = {98},
year = {2018},
}
@inproceedings{143,
abstract = {Vector Addition Systems with States (VASS) provide a well-known and fundamental model for the analysis of concurrent processes, parameterized systems, and are also used as abstract models of programs in resource bound analysis. In this paper we study the problem of obtaining asymptotic bounds on the termination time of a given VASS. In particular, we focus on the practically important case of obtaining polynomial bounds on termination time. Our main contributions are as follows: First, we present a polynomial-time algorithm for deciding whether a given VASS has a linear asymptotic complexity. We also show that if the complexity of a VASS is not linear, it is at least quadratic. Second, we classify VASS according to quantitative properties of their cycles. We show that certain singularities in these properties are the key reason for non-polynomial asymptotic complexity of VASS. In absence of singularities, we show that the asymptotic complexity is always polynomial and of the form Θ(nk), for some integer k d, where d is the dimension of the VASS. We present a polynomial-time algorithm computing the optimal k. For general VASS, the same algorithm, which is based on a complete technique for the construction of ranking functions in VASS, produces a valid lower bound, i.e., a k such that the termination complexity is (nk). Our results are based on new insights into the geometry of VASS dynamics, which hold the potential for further applicability to VASS analysis.},
author = {Brázdil, Tomáš and Chatterjee, Krishnendu and Kučera, Antonín and Novotny, Petr and Velan, Dominik and Zuleger, Florian},
isbn = {978-1-4503-5583-4},
location = {Oxford, United Kingdom},
pages = {185 -- 194},
publisher = {IEEE},
title = {{Efficient algorithms for asymptotic bounds on termination time in VASS}},
doi = {10.1145/3209108.3209191},
volume = {F138033},
year = {2018},
}
@article{148,
abstract = {Land plants evolved from charophytic algae, among which Charophyceae possess the most complex body plans. We present the genome of Chara braunii; comparison of the genome to those of land plants identified evolutionary novelties for plant terrestrialization and land plant heritage genes. C. braunii employs unique xylan synthases for cell wall biosynthesis, a phragmoplast (cell separation) mechanism similar to that of land plants, and many phytohormones. C. braunii plastids are controlled via land-plant-like retrograde signaling, and transcriptional regulation is more elaborate than in other algae. The morphological complexity of this organism may result from expanded gene families, with three cases of particular note: genes effecting tolerance to reactive oxygen species (ROS), LysM receptor-like kinases, and transcription factors (TFs). Transcriptomic analysis of sexual reproductive structures reveals intricate control by TFs, activity of the ROS gene network, and the ancestral use of plant-like storage and stress protection proteins in the zygote.},
author = {Nishiyama, Tomoaki and Sakayama, Hidetoshi and De Vries, Jan and Buschmann, Henrik and Saint Marcoux, Denis and Ullrich, Kristian and Haas, Fabian and Vanderstraeten, Lisa and Becker, Dirk and Lang, Daniel and Vosolsobě, Stanislav and Rombauts, Stephane and Wilhelmsson, Per and Janitza, Philipp and Kern, Ramona and Heyl, Alexander and Rümpler, Florian and Calderón Villalobos, Luz and Clay, John and Skokan, Roman and Toyoda, Atsushi and Suzuki, Yutaka and Kagoshima, Hiroshi and Schijlen, Elio and Tajeshwar, Navindra and Catarino, Bruno and Hetherington, Alexander and Saltykova, Assia and Bonnot, Clemence and Breuninger, Holger and Symeonidi, Aikaterini and Radhakrishnan, Guru and Van Nieuwerburgh, Filip and Deforce, Dieter and Chang, Caren and Karol, Kenneth and Hedrich, Rainer and Ulvskov, Peter and Glöckner, Gernot and Delwiche, Charles and Petrášek, Jan and Van De Peer, Yves and Friml, Jirí and Beilby, Mary and Dolan, Liam and Kohara, Yuji and Sugano, Sumio and Fujiyama, Asao and Delaux, Pierre Marc and Quint, Marcel and Theissen, Gunter and Hagemann, Martin and Harholt, Jesper and Dunand, Christophe and Zachgo, Sabine and Langdale, Jane and Maumus, Florian and Van Der Straeten, Dominique and Gould, Sven B and Rensing, Stefan},
journal = {Cell},
number = {2},
pages = {448 -- 464.e24},
publisher = {Cell Press},
title = {{The Chara genome: Secondary complexity and implications for plant terrestrialization}},
doi = {10.1016/j.cell.2018.06.033},
volume = {174},
year = {2018},
}
@inproceedings{155,
abstract = {There is currently significant interest in operating devices in the quantum regime, where their behaviour cannot be explained through classical mechanics. Quantum states, including entangled states, are fragile and easily disturbed by excessive thermal noise. Here we address the question of whether it is possible to create non-reciprocal devices that encourage the flow of thermal noise towards or away from a particular quantum device in a network. Our work makes use of the cascaded systems formalism to answer this question in the affirmative, showing how a three-port device can be used as an effective thermal transistor, and illustrates how this formalism maps onto an experimentally-realisable optomechanical system. Our results pave the way to more resilient quantum devices and to the use of thermal noise as a resource.},
author = {Xuereb, André and Aquilina, Matteo and Barzanjeh, Shabir},
editor = {Andrews, D L and Ostendorf, A and Bain, A J and Nunzi, J M},
location = {Strasbourg, France},
publisher = {SPIE},
title = {{Routing thermal noise through quantum networks}},
doi = {10.1117/12.2309928},
volume = {10672},
year = {2018},
}
@article{16,
abstract = {We report quantitative evidence of mixing-layer elastic instability in a viscoelastic fluid flow between two widely spaced obstacles hindering a channel flow at Re 1 and Wi 1. Two mixing layers with nonuniform shear velocity profiles are formed in the region between the obstacles. The mixing-layer instability arises in the vicinity of an inflection point on the shear velocity profile with a steep variation in the elastic stress. The instability results in an intermittent appearance of small vortices in the mixing layers and an amplification of spatiotemporal averaged vorticity in the elastic turbulence regime. The latter is characterized through scaling of friction factor with Wi and both pressure and velocity spectra. Furthermore, the observations reported provide improved understanding of the stability of the mixing layer in a viscoelastic fluid at large elasticity, i.e., Wi 1 and Re 1 and oppose the current view of suppression of vorticity solely by polymer additives.},
author = {Varshney, Atul and Steinberg, Victor},
journal = {Physical Review Fluids},
number = {10},
pages = {103303},
publisher = {American Physical Society},
title = {{Mixing layer instability and vorticity amplification in a creeping viscoelastic flow}},
doi = {10.1103/PhysRevFluids.3.103303},
volume = {3},
year = {2018},
}
@article{162,
abstract = {Facial shape is the basis for facial recognition and categorization. Facial features reflect the underlying geometry of the skeletal structures. Here, we reveal that cartilaginous nasal capsule (corresponding to upper jaw and face) is shaped by signals generated by neural structures: brain and olfactory epithelium. Brain-derived Sonic Hedgehog (SHH) enables the induction of nasal septum and posterior nasal capsule, whereas the formation of a capsule roof is controlled by signals from the olfactory epithelium. Unexpectedly, the cartilage of the nasal capsule turned out to be important for shaping membranous facial bones during development. This suggests that conserved neurosensory structures could benefit from protection and have evolved signals inducing cranial cartilages encasing them. Experiments with mutant mice revealed that the genomic regulatory regions controlling production of SHH in the nervous system contribute to facial cartilage morphogenesis, which might be a mechanism responsible for the adaptive evolution of animal faces and snouts.},
author = {Kaucka, Marketa and Petersen, Julian and Tesarova, Marketa and Szarowska, Bara and Kastriti, Maria and Xie, Meng and Kicheva, Anna and Annusver, Karl and Kasper, Maria and Symmons, Orsolya and Pan, Leslie and Spitz, Francois and Kaiser, Jozef and Hovorakova, Maria and Zikmund, Tomas and Sunadome, Kazunori and Matise, Michael P and Wang, Hui and Marklund, Ulrika and Abdo, Hind and Ernfors, Patrik and Maire, Pascal and Wurmser, Maud and Chagin, Andrei S and Fried, Kaj and Adameyko, Igor},
journal = {eLife},
publisher = {eLife Sciences Publications},
title = {{Signals from the brain and olfactory epithelium control shaping of the mammalian nasal capsule cartilage}},
doi = {10.7554/eLife.34465},
volume = {7},
year = {2018},
}
@inproceedings{174,
abstract = {We survey recent efforts to quantify failures of the Hasse principle in families of rationally connected varieties.},
author = {Browning, Timothy D},
location = {Salt Lake City, Utah, USA},
number = {2},
pages = {89 -- 102},
publisher = {American Mathematical Society},
title = {{How often does the Hasse principle hold?}},
doi = {10.1090/pspum/097.2/01700},
volume = {97},
year = {2018},
}
@unpublished{179,
abstract = {An asymptotic formula is established for the number of rational points of bounded anticanonical height which lie on a certain Zariski dense subset of the biprojective hypersurface x1y21+⋯+x4y24=0 in ℙ3×ℙ3. This confirms the modified Manin conjecture for this variety, in which the removal of a thin set of rational points is allowed.},
author = {Browning, Timothy D and Heath Brown, Roger},
booktitle = {Unknown},
pages = {1 -- 60},
publisher = {Unknown},
title = {{Density of rational points on a quadric bundle in ℙ3×ℙ3}},
year = {2018},
}
@article{181,
abstract = {We consider large random matrices X with centered, independent entries but possibly di erent variances. We compute the normalized trace of f(X)g(X∗) for f, g functions analytic on the spectrum of X. We use these results to compute the long time asymptotics for systems of coupled di erential equations with random coe cients. We show that when the coupling is critical, the norm squared of the solution decays like t−1/2.},
author = {Erdös, László and Krüger, Torben H and Renfrew, David T},
journal = {SIAM Journal on Mathematical Analysis},
number = {3},
pages = {3271 -- 3290},
publisher = {Society for Industrial and Applied Mathematics },
title = {{Power law decay for systems of randomly coupled differential equations}},
doi = {10.1137/17M1143125},
volume = {50},
year = {2018},
}
@inproceedings{186,
abstract = {A drawing of a graph on a surface is independently even if every pair of nonadjacent edges in the drawing crosses an even number of times. The ℤ2-genus of a graph G is the minimum g such that G has an independently even drawing on the orientable surface of genus g. An unpublished result by Robertson and Seymour implies that for every t, every graph of sufficiently large genus contains as a minor a projective t × t grid or one of the following so-called t-Kuratowski graphs: K3, t, or t copies of K5 or K3,3 sharing at most 2 common vertices. We show that the ℤ2-genus of graphs in these families is unbounded in t; in fact, equal to their genus. Together, this implies that the genus of a graph is bounded from above by a function of its ℤ2-genus, solving a problem posed by Schaefer and Štefankovič, and giving an approximate version of the Hanani-Tutte theorem on orientable surfaces.},
author = {Fulek, Radoslav and Kynčl, Jan},
location = {Budapest, Hungary},
pages = {401 -- 4014},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
title = {{The ℤ2-Genus of Kuratowski minors}},
doi = {10.4230/LIPIcs.SoCG.2018.40},
volume = {99},
year = {2018},
}
@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},
}
@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},
}