TY - CONF AB - Quantization converts neural networks into low-bit fixed-point computations which can be carried out by efficient integer-only hardware, and is standard practice for the deployment of neural networks on real-time embedded devices. However, like their real-numbered counterpart, quantized networks are not immune to malicious misclassification caused by adversarial attacks. We investigate how quantization affects a network’s robustness to adversarial attacks, which is a formal verification question. We show that neither robustness nor non-robustness are monotonic with changing the number of bits for the representation and, also, neither are preserved by quantization from a real-numbered network. For this reason, we introduce a verification method for quantized neural networks which, using SMT solving over bit-vectors, accounts for their exact, bit-precise semantics. We built a tool and analyzed the effect of quantization on a classifier for the MNIST dataset. We demonstrate that, compared to our method, existing methods for the analysis of real-numbered networks often derive false conclusions about their quantizations, both when determining robustness and when detecting attacks, and that existing methods for quantized networks often miss attacks. Furthermore, we applied our method beyond robustness, showing how the number of bits in quantization enlarges the gender bias of a predictor for students’ grades. AU - Giacobbe, Mirco AU - Henzinger, Thomas A AU - Lechner, Mathias ID - 7808 SN - 03029743 T2 - International Conference on Tools and Algorithms for the Construction and Analysis of Systems TI - How many bits does it take to quantize your neural network? VL - 12079 ER - TY - CONF AB - Isomanifolds are the generalization of isosurfaces to arbitrary dimension and codimension, i.e. manifolds defined as the zero set of some multivariate vector-valued smooth function f: ℝ^d → ℝ^(d-n). A natural (and efficient) way to approximate an isomanifold is to consider its Piecewise-Linear (PL) approximation based on a triangulation 𝒯 of the ambient space ℝ^d. In this paper, we give conditions under which the PL-approximation of an isomanifold is topologically equivalent to the isomanifold. The conditions are easy to satisfy in the sense that they can always be met by taking a sufficiently fine triangulation 𝒯. This contrasts with previous results on the triangulation of manifolds where, in arbitrary dimensions, delicate perturbations are needed to guarantee topological correctness, which leads to strong limitations in practice. We further give a bound on the Fréchet distance between the original isomanifold and its PL-approximation. Finally we show analogous results for the PL-approximation of an isomanifold with boundary. AU - Boissonnat, Jean-Daniel AU - Wintraecken, Mathijs ID - 7952 SN - 1868-8969 T2 - 36th International Symposium on Computational Geometry TI - The topological correctness of PL-approximations of isomanifolds VL - 164 ER - TY - CONF AB - Given a finite point set P in general position in the plane, a full triangulation is a maximal straight-line embedded plane graph on P. A partial triangulation on P is a full triangulation of some subset P' of P containing all extreme points in P. A bistellar flip on a partial triangulation either flips an edge, removes a non-extreme point of degree 3, or adds a point in P ⧵ P' as vertex of degree 3. The bistellar flip graph has all partial triangulations as vertices, and a pair of partial triangulations is adjacent if they can be obtained from one another by a bistellar flip. The goal of this paper is to investigate the structure of this graph, with emphasis on its connectivity. For sets P of n points in general position, we show that the bistellar flip graph is (n-3)-connected, thereby answering, for sets in general position, an open questions raised in a book (by De Loera, Rambau, and Santos) and a survey (by Lee and Santos) on triangulations. This matches the situation for the subfamily of regular triangulations (i.e., partial triangulations obtained by lifting the points and projecting the lower convex hull), where (n-3)-connectivity has been known since the late 1980s through the secondary polytope (Gelfand, Kapranov, Zelevinsky) and Balinski’s Theorem. Our methods also yield the following results (see the full version [Wagner and Welzl, 2020]): (i) The bistellar flip graph can be covered by graphs of polytopes of dimension n-3 (products of secondary polytopes). (ii) A partial triangulation is regular, if it has distance n-3 in the Hasse diagram of the partial order of partial subdivisions from the trivial subdivision. (iii) All partial triangulations are regular iff the trivial subdivision has height n-3 in the partial order of partial subdivisions. (iv) There are arbitrarily large sets P with non-regular partial triangulations, while every proper subset has only regular triangulations, i.e., there are no small certificates for the existence of non-regular partial triangulations (answering a question by F. Santos in the unexpected direction). AU - Wagner, Uli AU - Welzl, Emo ID - 7990 SN - 18688969 T2 - 36th International Symposium on Computational Geometry TI - Connectivity of triangulation flip graphs in the plane (Part II: Bistellar flips) VL - 164 ER - TY - CONF AB - In a straight-line embedded triangulation of a point set P in the plane, removing an inner edge and—provided the resulting quadrilateral is convex—adding the other diagonal is called an edge flip. The (edge) flip graph has all triangulations as vertices, and a pair of triangulations is adjacent if they can be obtained from each other by an edge flip. The goal of this paper is to contribute to a better understanding of the flip graph, with an emphasis on its connectivity. For sets in general position, it is known that every triangulation allows at least edge flips (a tight bound) which gives the minimum degree of any flip graph for n points. We show that for every point set P in general position, the flip graph is at least -vertex connected. Somewhat more strongly, we show that the vertex connectivity equals the minimum degree occurring in the flip graph, i.e. the minimum number of flippable edges in any triangulation of P, provided P is large enough. Finally, we exhibit some of the geometry of the flip graph by showing that the flip graph can be covered by 1-skeletons of polytopes of dimension (products of associahedra). A corresponding result ((n – 3)-vertex connectedness) can be shown for the bistellar flip graph of partial triangulations, i.e. the set of all triangulations of subsets of P which contain all extreme points of P. This will be treated separately in a second part. AU - Wagner, Uli AU - Welzl, Emo ID - 7807 SN - 9781611975994 T2 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms TI - Connectivity of triangulation flip graphs in the plane (Part I: Edge flips) VL - 2020-January ER - TY - GEN AB - The Mytilus complex of marine mussel species forms a mosaic of hybrid zones, found across temperate regions of the globe. This allows us to study "replicated" instances of secondary contact between closely-related species. Previous work on this complex has shown that local introgression is both widespread and highly heterogeneous, and has identified SNPs that are outliers of differentiation between lineages. Here, we developed an ancestry-informative panel of such SNPs. We then compared their frequencies in newly-sampled populations, including samples from within the hybrid zones, and parental populations at different distances from the contact. Results show that close to the hybrid zones, some outlier loci are near to fixation for the heterospecific allele, suggesting enhanced local introgression, or the local sweep of a shared ancestral allele. Conversely, genomic cline analyses, treating local parental populations as the reference, reveal a globally high concordance among loci, albeit with a few signals of asymmetric introgression. Enhanced local introgression at specific loci is consistent with the early transfer of adaptive variants after contact, possibly including asymmetric bi-stable variants (Dobzhansky-Muller incompatibilities), or haplotypes loaded with fewer deleterious mutations. Having escaped one barrier, however, these variants can be trapped or delayed at the next barrier, confining the introgression locally. These results shed light on the decay of species barriers during phases of contact. AU - Simon, Alexis AU - Fraisse, Christelle AU - El Ayari, Tahani AU - Liautard-Haag, Cathy AU - Strelkov, Petr AU - Welch, John AU - Bierne, Nicolas ID - 13073 TI - How do species barriers decay? concordance and local introgression in mosaic hybrid zones of mussels ER - TY - GEN AB - Domestication is a human-induced selection process that imprints the genomes of domesticated populations over a short evolutionary time scale, and that occurs in a given demographic context. Reconstructing historical gene flow, effective population size changes and their timing is therefore of fundamental interest to understand how plant demography and human selection jointly shape genomic divergence during domestication. Yet, the comparison under a single statistical framework of independent domestication histories across different crop species has been little evaluated so far. Thus, it is unclear whether domestication leads to convergent demographic changes that similarly affect crop genomes. To address this question, we used existing and new transcriptome data on three crop species of Solanaceae (eggplant, pepper and tomato), together with their close wild relatives. We fitted twelve demographic models of increasing complexity on the unfolded joint allele frequency spectrum for each wild/crop pair, and we found evidence for both shared and species-specific demographic processes between species. A convergent history of domestication with gene-flow was inferred for all three species, along with evidence of strong reduction in the effective population size during the cultivation stage of tomato and pepper. The absence of any reduction in size of the crop in eggplant stands out from the classical view of the domestication process; as does the existence of a “protracted period” of management before cultivation. Our results also suggest divergent management strategies of modern cultivars among species as their current demography substantially differs. Finally, the timing of domestication is species-specific and supported by the few historical records available. AU - Arnoux, Stephanie AU - Fraisse, Christelle AU - Sauvage, Christopher ID - 13065 TI - VCF files of synonymous SNPs related to: Genomic inference of complex domestication histories in three Solanaceae species ER - TY - CONF AB - This work analyzes the latency of the simplified successive cancellation (SSC) decoding scheme for polar codes proposed by Alamdar-Yazdi and Kschischang. It is shown that, unlike conventional successive cancellation decoding, where latency is linear in the block length, the latency of SSC decoding is sublinear. More specifically, the latency of SSC decoding is O(N 1−1/µ ), where N is the block length and µ is the scaling exponent of the channel, which captures the speed of convergence of the rate to capacity. Numerical results demonstrate the tightness of the bound and show that most of the latency reduction arises from the parallel decoding of subcodes of rate 0 and 1. AU - Mondelli, Marco AU - Hashemi, Seyyed Ali AU - Cioffi, John AU - Goldsmith, Andrea ID - 8536 SN - 21578095 T2 - IEEE International Symposium on Information Theory - Proceedings TI - Simplified successive cancellation decoding of polar codes has sublinear latency VL - 2020-June ER - TY - JOUR AU - Avvakumov, Sergey AU - Wagner, Uli AU - Mabillard, Isaac AU - Skopenkov, A. B. ID - 9308 IS - 6 JF - Russian Mathematical Surveys SN - 0036-0279 TI - Eliminating higher-multiplicity intersections, III. Codimension 2 VL - 75 ER - TY - JOUR AB - We study dynamical optimal transport metrics between density matricesassociated to symmetric Dirichlet forms on finite-dimensional C∗-algebras. Our settingcovers arbitrary skew-derivations and it provides a unified framework that simultaneously generalizes recently constructed transport metrics for Markov chains, Lindblad equations, and the Fermi Ornstein–Uhlenbeck semigroup. We develop a non-nommutative differential calculus that allows us to obtain non-commutative Ricci curvature bounds, logarithmic Sobolev inequalities, transport-entropy inequalities, andspectral gap estimates. AU - Carlen, Eric A. AU - Maas, Jan ID - 6358 IS - 2 JF - Journal of Statistical Physics SN - 00224715 TI - Non-commutative calculus, optimal transport and functional inequalities in dissipative quantum systems VL - 178 ER - TY - CHAP AB - We study the Gromov waist in the sense of t-neighborhoods for measures in the Euclidean space, motivated by the famous theorem of Gromov about the waist of radially symmetric Gaussian measures. In particular, it turns our possible to extend Gromov’s original result to the case of not necessarily radially symmetric Gaussian measure. We also provide examples of measures having no t-neighborhood waist property, including a rather wide class of compactly supported radially symmetric measures and their maps into the Euclidean space of dimension at least 2. We use a simpler form of Gromov’s pancake argument to produce some estimates of t-neighborhoods of (weighted) volume-critical submanifolds in the spirit of the waist theorems, including neighborhoods of algebraic manifolds in the complex projective space. In the appendix of this paper we provide for reader’s convenience a more detailed explanation of the Caffarelli theorem that we use to handle not necessarily radially symmetric Gaussian measures. AU - Akopyan, Arseniy AU - Karasev, Roman ED - Klartag, Bo'az ED - Milman, Emanuel ID - 74 SN - 00758434 T2 - Geometric Aspects of Functional Analysis TI - Gromov's waist of non-radial Gaussian measures and radial non-Gaussian measures VL - 2256 ER -