@article{5678, abstract = {The order-k Voronoi tessellation of a locally finite set 𝑋⊆ℝ𝑛 decomposes ℝ𝑛 into convex domains whose points have the same k nearest neighbors in X. Assuming X is a stationary Poisson point process, we give explicit formulas for the expected number and total area of faces of a given dimension per unit volume of space. We also develop a relaxed version of discrete Morse theory and generalize by counting only faces, for which the k nearest points in X are within a given distance threshold.}, author = {Edelsbrunner, Herbert and Nikitenko, Anton}, issn = {14320444}, journal = {Discrete and Computational Geometry}, number = {4}, pages = {865–878}, publisher = {Springer}, title = {{Poisson–Delaunay Mosaics of Order k}}, doi = {10.1007/s00454-018-0049-2}, volume = {62}, year = {2019}, } @inproceedings{5947, abstract = {Graph algorithms applied in many applications, including social networks, communication networks, VLSI design, graphics, and several others, require dynamic modifications - addition and removal of vertices and/or edges - in the graph. This paper presents a novel concurrent non-blocking algorithm to implement a dynamic unbounded directed graph in a shared-memory machine. The addition and removal operations of vertices and edges are lock-free. For a finite sized graph, the lookup operations are wait-free. Most significant component of the presented algorithm is the reachability query in a concurrent graph. The reachability queries in our algorithm are obstruction-free and thus impose minimal additional synchronization cost over other operations. We prove that each of the data structure operations are linearizable. We extensively evaluate a sample C/C++ implementation of the algorithm through a number of micro-benchmarks. The experimental results show that the proposed algorithm scales well with the number of threads and on an average provides 5 to 7x performance improvement over a concurrent graph implementation using coarse-grained locking.}, author = {Chatterjee, Bapi and Peri, Sathya and Sa, Muktikanta and Singhal, Nandini}, booktitle = {ACM International Conference Proceeding Series}, isbn = {978-1-4503-6094-4 }, location = {Bangalore, India}, pages = {168--177}, publisher = {ACM}, title = {{A simple and practical concurrent non-blocking unbounded graph with linearizable reachability queries}}, doi = {10.1145/3288599.3288617}, year = {2019}, } @article{5906, abstract = {We introduce a simple, exactly solvable strong-randomness renormalization group (RG) model for the many-body localization (MBL) transition in one dimension. Our approach relies on a family of RG flows parametrized by the asymmetry between thermal and localized phases. We identify the physical MBL transition in the limit of maximal asymmetry, reflecting the instability of MBL against rare thermal inclusions. We find a critical point that is localized with power-law distributed thermal inclusions. The typical size of critical inclusions remains finite at the transition, while the average size is logarithmically diverging. We propose a two-parameter scaling theory for the many-body localization transition that falls into the Kosterlitz-Thouless universality class, with the MBL phase corresponding to a stable line of fixed points with multifractal behavior.}, author = {Goremykina, Anya and Vasseur, Romain and Serbyn, Maksym}, issn = {1079-7114}, journal = {Physical Review Letters}, number = {4}, publisher = {American Physical Society}, title = {{Analytically solvable renormalization group for the many-body localization transition}}, doi = {10.1103/physrevlett.122.040601}, volume = {122}, year = {2019}, } @misc{9790, author = {Pokusaeva, Victoria and Usmanova, Dinara R. and Putintseva, Ekaterina V. and Espinar, Lorena and Sarkisyan, Karen and Mishin, Alexander S. and Bogatyreva, Natalya S. and Ivankov, Dmitry and Akopyan, Arseniy and Avvakumov, Sergey and Povolotskaya, Inna S. and Filion, Guillaume J. and Carey, Lucas B. and Kondrashov, Fyodor}, publisher = {Public Library of Science}, title = {{A statistical summary of segment libraries and sequencing results}}, doi = {10.1371/journal.pgen.1008079.s011}, year = {2019}, } @misc{9797, author = {Pokusaeva, Victoria and Usmanova, Dinara R. and Putintseva, Ekaterina V. and Espinar, Lorena and Sarkisyan, Karen and Mishin, Alexander S. and Bogatyreva, Natalya S. and Ivankov, Dmitry and Akopyan, Arseniy and Povolotskaya, Inna S. and Filion, Guillaume J. and Carey, Lucas B. and Kondrashov, Fyodor}, publisher = {Public Library of Science}, title = {{A statistical summary of segment libraries and sequencing results}}, doi = {10.1371/journal.pgen.1008079.s011}, year = {2019}, } @misc{9789, author = {Pokusaeva, Victoria and Usmanova, Dinara R. and Putintseva, Ekaterina V. and Espinar, Lorena and Sarkisyan, Karen and Mishin, Alexander S. and Bogatyreva, Natalya S. and Ivankov, Dmitry and Akopyan, Arseniy and Avvakumov, Sergey and Povolotskaya, Inna S. and Filion, Guillaume J. and Carey, Lucas B. and Kondrashov, Fyodor}, publisher = {Public Library of Science}, title = {{Multiple alignment of His3 orthologues}}, doi = {10.1371/journal.pgen.1008079.s010}, year = {2019}, } @phdthesis{6179, abstract = {In the first part of this thesis we consider large random matrices with arbitrary expectation and a general slowly decaying correlation among its entries. We prove universality of the local eigenvalue statistics and optimal local laws for the resolvent in the bulk and edge regime. The main novel tool is a systematic diagrammatic control of a multivariate cumulant expansion. In the second part we consider Wigner-type matrices and show that at any cusp singularity of the limiting eigenvalue distribution the local eigenvalue statistics are uni- versal and form a Pearcey process. Since the density of states typically exhibits only square root or cubic root cusp singularities, our work complements previous results on the bulk and edge universality and it thus completes the resolution of the Wigner- Dyson-Mehta universality conjecture for the last remaining universality type. Our analysis holds not only for exact cusps, but approximate cusps as well, where an ex- tended Pearcey process emerges. As a main technical ingredient we prove an optimal local law at the cusp, and extend the fast relaxation to equilibrium of the Dyson Brow- nian motion to the cusp regime. In the third and final part we explore the entrywise linear statistics of Wigner ma- trices and identify the fluctuations for a large class of test functions with little regularity. This enables us to study the rectangular Young diagram obtained from the interlacing eigenvalues of the random matrix and its minor, and we find that, despite having the same limit, the fluctuations differ from those of the algebraic Young tableaux equipped with the Plancharel measure.}, author = {Schröder, Dominik J}, issn = {2663-337X}, pages = {375}, publisher = {Institute of Science and Technology Austria}, title = {{From Dyson to Pearcey: Universal statistics in random matrix theory}}, doi = {10.15479/AT:ISTA:th6179}, year = {2019}, } @article{6182, abstract = {We consider large random matrices with a general slowly decaying correlation among its entries. We prove universality of the local eigenvalue statistics and optimal local laws for the resolvent away from the spectral edges, generalizing the recent result of Ajanki et al. [‘Stability of the matrix Dyson equation and random matrices with correlations’, Probab. Theory Related Fields 173(1–2) (2019), 293–373] to allow slow correlation decay and arbitrary expectation. The main novel tool is a systematic diagrammatic control of a multivariate cumulant expansion.}, author = {Erdös, LĂĄszlĂł and KrĂŒger, Torben H and Schröder, Dominik J}, issn = {2050-5094}, journal = {Forum of Mathematics, Sigma}, publisher = {Cambridge University Press}, title = {{Random matrices with slow correlation decay}}, doi = {10.1017/fms.2019.2}, volume = {7}, year = {2019}, } @article{6186, abstract = {We prove that the local eigenvalue statistics of real symmetric Wigner-type matrices near the cusp points of the eigenvalue density are universal. Together with the companion paper [arXiv:1809.03971], which proves the same result for the complex Hermitian symmetry class, this completes the last remaining case of the Wigner-Dyson-Mehta universality conjecture after bulk and edge universalities have been established in the last years. We extend the recent Dyson Brownian motion analysis at the edge [arXiv:1712.03881] to the cusp regime using the optimal local law from [arXiv:1809.03971] and the accurate local shape analysis of the density from [arXiv:1506.05095, arXiv:1804.07752]. We also present a PDE-based method to improve the estimate on eigenvalue rigidity via the maximum principle of the heat flow related to the Dyson Brownian motion.}, author = {Cipolloni, Giorgio and Erdös, LĂĄszlĂł and KrĂŒger, Torben H and Schröder, Dominik J}, issn = {2578-5885}, journal = {Pure and Applied Analysis }, number = {4}, pages = {615–707}, publisher = {MSP}, title = {{Cusp universality for random matrices, II: The real symmetric case}}, doi = {10.2140/paa.2019.1.615}, volume = {1}, year = {2019}, } @inproceedings{7479, abstract = {Multi-exit architectures, in which a stack of processing layers is interleaved with early output layers, allow the processing of a test example to stop early and thus save computation time and/or energy. In this work, we propose a new training procedure for multi-exit architectures based on the principle of knowledge distillation. The method encourage searly exits to mimic later, more accurate exits, by matching their output probabilities. Experiments on CIFAR100 and ImageNet show that distillation-based training significantly improves the accuracy of early exits while maintaining state-of-the-art accuracy for late ones. The method is particularly beneficial when training data is limited and it allows a straightforward extension to semi-supervised learning,i.e. making use of unlabeled data at training time. Moreover, it takes only afew lines to implement and incurs almost no computational overhead at training time, and none at all at test time.}, author = {Bui Thi Mai, Phuong and Lampert, Christoph}, booktitle = {IEEE International Conference on Computer Vision}, isbn = {9781728148038}, issn = {1550-5499}, location = {Seoul, Korea}, pages = {1355--1364}, publisher = {IEEE}, title = {{Distillation-based training for multi-exit architectures}}, doi = {10.1109/ICCV.2019.00144}, volume = {2019-October}, year = {2019}, } @inproceedings{6677, abstract = {The Fiat-Shamir heuristic transforms a public-coin interactive proof into a non-interactive argument, by replacing the verifier with a cryptographic hash function that is applied to the protocol’s transcript. Constructing hash functions for which this transformation is sound is a central and long-standing open question in cryptography. We show that solving the END−OF−METERED−LINE problem is no easier than breaking the soundness of the Fiat-Shamir transformation when applied to the sumcheck protocol. In particular, if the transformed protocol is sound, then any hard problem in #P gives rise to a hard distribution in the class CLS, which is contained in PPAD. Our result opens up the possibility of sampling moderately-sized games for which it is hard to find a Nash equilibrium, by reducing the inversion of appropriately chosen one-way functions to #SAT. Our main technical contribution is a stateful incrementally verifiable procedure that, given a SAT instance over n variables, counts the number of satisfying assignments. This is accomplished via an exponential sequence of small steps, each computable in time poly(n). Incremental verifiability means that each intermediate state includes a sumcheck-based proof of its correctness, and the proof can be updated and verified in time poly(n).}, author = {Choudhuri, Arka Rai and Hubáček, Pavel and Kamath Hosdurg, Chethan and Pietrzak, Krzysztof Z and Rosen, Alon and Rothblum, Guy N.}, booktitle = {Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing - STOC 2019}, isbn = {9781450367059}, location = {Phoenix, AZ, United States}, pages = {1103--1114}, publisher = {ACM}, title = {{Finding a Nash equilibrium is no easier than breaking Fiat-Shamir}}, doi = {10.1145/3313276.3316400}, year = {2019}, } @article{10874, abstract = {In this article we prove an analogue of a theorem of Lachaud, Ritzenthaler, and Zykin, which allows us to connect invariants of binary octics to Siegel modular forms of genus 3. We use this connection to show that certain modular functions, when restricted to the hyperelliptic locus, assume values whose denominators are products of powers of primes of bad reduction for the associated hyperelliptic curves. We illustrate our theorem with explicit computations. This work is motivated by the study of the values of these modular functions at CM points of the Siegel upper half-space, which, if their denominators are known, can be used to effectively compute models of (hyperelliptic, in our case) curves with CM.}, author = {Ionica, Sorina and Kılıçer, Pınar and Lauter, Kristin and Lorenzo GarcĂ­a, Elisa and Manzateanu, Maria-Adelina and Massierer, Maike and Vincent, Christelle}, issn = {2363-9555}, journal = {Research in Number Theory}, keywords = {Algebra and Number Theory}, publisher = {Springer Nature}, title = {{Modular invariants for genus 3 hyperelliptic curves}}, doi = {10.1007/s40993-018-0146-6}, volume = {5}, year = {2019}, } @article{6310, abstract = {An asymptotic formula is established for the number of rational points of bounded anticanonical height which lie on a certain Zariskiopen subset of an arbitrary smooth biquadratic hypersurface in sufficiently many variables. The proof uses the Hardy–Littlewood circle method.}, author = {Browning, Timothy D and Hu, L.Q.}, issn = {1090-2082}, journal = {Advances in Mathematics}, pages = {920--940}, publisher = {Elsevier}, title = {{Counting rational points on biquadratic hypersurfaces}}, doi = {10.1016/j.aim.2019.04.031}, volume = {349}, year = {2019}, } @article{6835, abstract = {We derive the Hasse principle and weak approximation for fibrations of certain varieties in the spirit of work by Colliot-ThĂ©lĂšne–Sansuc and Harpaz–Skorobogatov–Wittenberg. Our varieties are defined through polynomials in many variables and part of our work is devoted to establishing Schinzel's hypothesis for polynomials of this kind. This last part is achieved by using arguments behind Birch's well-known result regarding the Hasse principle for complete intersections with the notable difference that we prove our result in 50% fewer variables than in the classical Birch setting. We also study the problem of square-free values of an integer polynomial with 66.6% fewer variables than in the Birch setting.}, author = {Destagnol, Kevin N and Sofos, Efthymios}, issn = {0007-4497}, journal = {Bulletin des Sciences Mathematiques}, number = {11}, publisher = {Elsevier}, title = {{Rational points and prime values of polynomials in moderately many variables}}, doi = {10.1016/j.bulsci.2019.102794}, volume = {156}, year = {2019}, } @article{175, abstract = {An upper bound sieve for rational points on suitable varieties isdeveloped, together with applications tocounting rational points in thin sets,to local solubility in families, and to the notion of “friable” rational pointswith respect to divisors. In the special case of quadrics, sharper estimates areobtained by developing a version of the Selberg sieve for rational points.}, author = {Browning, Timothy D and Loughran, Daniel}, issn = {1088-6850}, journal = {Transactions of the American Mathematical Society}, number = {8}, pages = {5757--5785}, publisher = {American Mathematical Society}, title = {{Sieving rational points on varieties}}, doi = {10.1090/tran/7514}, volume = {371}, year = {2019}, } @article{6620, abstract = {This paper establishes an asymptotic formula with a power-saving error term for the number of rational points of bounded height on the singular cubic surface of ℙ3ℚ given by the following equation đ‘„0(đ‘„21+đ‘„22)âˆ’đ‘„33=0 in agreement with the Manin-Peyre conjectures. }, author = {De La BretĂšche, RĂ©gis and Destagnol, Kevin N and Liu, Jianya and Wu, Jie and Zhao, Yongqiang}, issn = {1674-7283}, journal = {Science China Mathematics}, number = {12}, pages = {2435–2446}, publisher = {Springer}, title = {{On a certain non-split cubic surface}}, doi = {10.1007/s11425-018-9543-8}, volume = {62}, year = {2019}, } @article{10878, abstract = {Starting from a microscopic model for a system of neurons evolving in time which individually follow a stochastic integrate-and-fire type model, we study a mean-field limit of the system. Our model is described by a system of SDEs with discontinuous coefficients for the action potential of each neuron and takes into account the (random) spatial configuration of neurons allowing the interaction to depend on it. In the limit as the number of particles tends to infinity, we obtain a nonlinear Fokker-Planck type PDE in two variables, with derivatives only with respect to one variable and discontinuous coefficients. We also study strong well-posedness of the system of SDEs and prove the existence and uniqueness of a weak measure-valued solution to the PDE, obtained as the limit of the laws of the empirical measures for the system of particles.}, author = {Flandoli, Franco and Priola, Enrico and Zanco, Giovanni A}, issn = {1553-5231}, journal = {Discrete and Continuous Dynamical Systems}, keywords = {Applied Mathematics, Discrete Mathematics and Combinatorics, Analysis}, number = {6}, pages = {3037--3067}, publisher = {AIMS}, title = {{A mean-field model with discontinuous coefficients for neurons with spatial interaction}}, doi = {10.3934/dcds.2019126}, volume = {39}, year = {2019}, } @article{6554, abstract = {Due to the importance of zero-shot learning, i.e. classifying images where there is a lack of labeled training data, the number of proposed approaches has recently increased steadily. We argue that it is time to take a step back and to analyze the status quo of the area. The purpose of this paper is three-fold. First, given the fact that there is no agreed upon zero-shot learning benchmark, we first define a new benchmark by unifying both the evaluation protocols and data splits of publicly available datasets used for this task. This is an important contribution as published results are often not comparable and sometimes even flawed due to, e.g. pre-training on zero-shot test classes. Moreover, we propose a new zero-shot learning dataset, the Animals with Attributes 2 (AWA2) dataset which we make publicly available both in terms of image features and the images themselves. Second, we compare and analyze a significant number of the state-of-the-art methods in depth, both in the classic zero-shot setting but also in the more realistic generalized zero-shot setting. Finally, we discuss in detail the limitations of the current status of the area which can be taken as a basis for advancing it.}, author = {Xian, Yongqin and Lampert, Christoph and Schiele, Bernt and Akata, Zeynep}, issn = {1939-3539}, journal = {IEEE Transactions on Pattern Analysis and Machine Intelligence}, number = {9}, pages = {2251 -- 2265}, publisher = {IEEE}, title = {{Zero-shot learning - A comprehensive evaluation of the good, the bad and the ugly}}, doi = {10.1109/tpami.2018.2857768}, volume = {41}, year = {2019}, } @article{7165, abstract = {Cell division, movement and differentiation contribute to pattern formation in developing tissues. This is the case in the vertebrate neural tube, in which neurons differentiate in a characteristic pattern from a highly dynamic proliferating pseudostratified epithelium. To investigate how progenitor proliferation and differentiation affect cell arrangement and growth of the neural tube, we used experimental measurements to develop a mechanical model of the apical surface of the neuroepithelium that incorporates the effect of interkinetic nuclear movement and spatially varying rates of neuronal differentiation. Simulations predict that tissue growth and the shape of lineage-related clones of cells differ with the rate of differentiation. Growth is isotropic in regions of high differentiation, but dorsoventrally biased in regions of low differentiation. This is consistent with experimental observations. The absence of directional signalling in the simulations indicates that global mechanical constraints are sufficient to explain the observed differences in anisotropy. This provides insight into how the tissue growth rate affects cell dynamics and growth anisotropy and opens up possibilities to study the coupling between mechanics, pattern formation and growth in the neural tube.}, author = {Guerrero, Pilar and Perez-Carrasco, Ruben and ZagĂłrski, Marcin P and Page, David and Kicheva, Anna and Briscoe, James and Page, Karen M.}, issn = {1477-9129}, journal = {Development}, number = {23}, publisher = {Company of Biologists}, title = {{Neuronal differentiation influences progenitor arrangement in the vertebrate neuroepithelium}}, doi = {10.1242/dev.176297}, volume = {146}, year = {2019}, } @article{6897, abstract = {The apical hook is a transiently formed structure that plays a protective role when the germinating seedling penetrates through the soil towards the surface. Crucial for proper bending is the local auxin maxima, which defines the concave (inner) side of the hook curvature. As no sign of asymmetric auxin distribution has been reported in embryonic hypocotyls prior to hook formation, the question of how auxin asymmetry is established in the early phases of seedling germination remains largely unanswered. Here, we analyzed the auxin distribution and expression of PIN auxin efflux carriers from early phases of germination, and show that bending of the root in response to gravity is the crucial initial cue that governs the hypocotyl bending required for apical hook formation. Importantly, polar auxin transport machinery is established gradually after germination starts as a result of tight root-hypocotyl interaction and a proper balance between abscisic acid and gibberellins.}, author = {Zhu, Qiang and Gallemi, Marçal and PospĂ­ĆĄil, Jiƙí and ĆœĂĄdnĂ­kovĂĄ, Petra and Strnad, Miroslav and BenkovĂĄ, Eva}, issn = {1477-9129}, journal = {Development}, number = {17}, publisher = {Company of Biologists}, title = {{Root gravity response module guides differential growth determining both root bending and apical hook formation in Arabidopsis}}, doi = {10.1242/dev.175919}, volume = {146}, year = {2019}, }