@inproceedings{10672, abstract = {The family of feedback alignment (FA) algorithms aims to provide a more biologically motivated alternative to backpropagation (BP), by substituting the computations that are unrealistic to be implemented in physical brains. While FA algorithms have been shown to work well in practice, there is a lack of rigorous theory proofing their learning capabilities. Here we introduce the first feedback alignment algorithm with provable learning guarantees. In contrast to existing work, we do not require any assumption about the size or depth of the network except that it has a single output neuron, i.e., such as for binary classification tasks. We show that our FA algorithm can deliver its theoretical promises in practice, surpassing the learning performance of existing FA methods and matching backpropagation in binary classification tasks. Finally, we demonstrate the limits of our FA variant when the number of output neurons grows beyond a certain quantity.}, author = {Lechner, Mathias}, booktitle = {8th International Conference on Learning Representations}, location = {Virtual ; Addis Ababa, Ethiopia}, publisher = {ICLR}, title = {{Learning representations for binary-classification without backpropagation}}, year = {2020}, } @inproceedings{10673, abstract = {We propose a neural information processing system obtained by re-purposing the function of a biological neural circuit model to govern simulated and real-world control tasks. Inspired by the structure of the nervous system of the soil-worm, C. elegans, we introduce ordinary neural circuits (ONCs), defined as the model of biological neural circuits reparameterized for the control of alternative tasks. We first demonstrate that ONCs realize networks with higher maximum flow compared to arbitrary wired networks. We then learn instances of ONCs to control a series of robotic tasks, including the autonomous parking of a real-world rover robot. For reconfiguration of the purpose of the neural circuit, we adopt a search-based optimization algorithm. Ordinary neural circuits perform on par and, in some cases, significantly surpass the performance of contemporary deep learning models. ONC networks are compact, 77% sparser than their counterpart neural controllers, and their neural dynamics are fully interpretable at the cell-level.}, author = {Hasani, Ramin and Lechner, Mathias and Amini, Alexander and Rus, Daniela and Grosu, Radu}, booktitle = {Proceedings of the 37th International Conference on Machine Learning}, issn = {2640-3498}, location = {Virtual}, pages = {4082--4093}, title = {{A natural lottery ticket winner: Reinforcement learning with ordinary neural circuits}}, year = {2020}, } @article{10861, abstract = {We introduce in this paper AMT2.0, a tool for qualitative and quantitative analysis of hybrid continuous and Boolean signals that combine numerical values and discrete events. The evaluation of the signals is based on rich temporal specifications expressed in extended signal temporal logic, which integrates timed regular expressions within signal temporal logic. The tool features qualitative monitoring (property satisfaction checking), trace diagnostics for explaining and justifying property violations and specification-driven measurement of quantitative features of the signal. We demonstrate the tool functionality on several running examples and case studies, and evaluate its performance.}, author = {Nickovic, Dejan and Lebeltel, Olivier and Maler, Oded and Ferrere, Thomas and Ulus, Dogan}, issn = {1433-2787}, journal = {International Journal on Software Tools for Technology Transfer}, keywords = {Information Systems, Software}, number = {6}, pages = {741--758}, publisher = {Springer Nature}, title = {{AMT 2.0: Qualitative and quantitative trace analysis with extended signal temporal logic}}, doi = {10.1007/s10009-020-00582-z}, volume = {22}, year = {2020}, } @article{10862, abstract = {We consider the sum of two large Hermitian matrices A and B with a Haar unitary conjugation bringing them into a general relative position. We prove that the eigenvalue density on the scale slightly above the local eigenvalue spacing is asymptotically given by the free additive convolution of the laws of A and B as the dimension of the matrix increases. This implies optimal rigidity of the eigenvalues and optimal rate of convergence in Voiculescu's theorem. Our previous works [4], [5] established these results in the bulk spectrum, the current paper completely settles the problem at the spectral edges provided they have the typical square-root behavior. The key element of our proof is to compensate the deterioration of the stability of the subordination equations by sharp error estimates that properly account for the local density near the edge. Our results also hold if the Haar unitary matrix is replaced by the Haar orthogonal matrix.}, author = {Bao, Zhigang and Erdös, László and Schnelli, Kevin}, issn = {0022-1236}, journal = {Journal of Functional Analysis}, keywords = {Analysis}, number = {7}, publisher = {Elsevier}, title = {{Spectral rigidity for addition of random matrices at the regular edge}}, doi = {10.1016/j.jfa.2020.108639}, volume = {279}, year = {2020}, } @article{10866, abstract = {Recent discoveries have shown that, when two layers of van der Waals (vdW) materials are superimposed with a relative twist angle between them, the electronic properties of the coupled system can be dramatically altered. Here, we demonstrate that a similar concept can be extended to the optics realm, particularly to propagating phonon polaritons–hybrid light-matter interactions. To do this, we fabricate stacks composed of two twisted slabs of a vdW crystal (α-MoO3) supporting anisotropic phonon polaritons (PhPs), and image the propagation of the latter when launched by localized sources. Our images reveal that, under a critical angle, the PhPs isofrequency curve undergoes a topological transition, in which the propagation of PhPs is strongly guided (canalization regime) along predetermined directions without geometric spreading. These results demonstrate a new degree of freedom (twist angle) for controlling the propagation of polaritons at the nanoscale with potential for nanoimaging, (bio)-sensing, or heat management.}, author = {Duan, Jiahua and Capote-Robayna, Nathaniel and Taboada-Gutiérrez, Javier and Álvarez-Pérez, Gonzalo and Prieto Gonzalez, Ivan and Martín-Sánchez, Javier and Nikitin, Alexey Y. and Alonso-González, Pablo}, issn = {1530-6992}, journal = {Nano Letters}, keywords = {Mechanical Engineering, Condensed Matter Physics, General Materials Science, General Chemistry, Bioengineering}, number = {7}, pages = {5323--5329}, publisher = {American Chemical Society}, title = {{Twisted nano-optics: Manipulating light at the nanoscale with twisted phonon polaritonic slabs}}, doi = {10.1021/acs.nanolett.0c01673}, volume = {20}, year = {2020}, } @article{10867, abstract = {In this paper we find a tight estimate for Gromov’s waist of the balls in spaces of constant curvature, deduce the estimates for the balls in Riemannian manifolds with upper bounds on the curvature (CAT(ϰ)-spaces), and establish similar result for normed spaces.}, author = {Akopyan, Arseniy and Karasev, Roman}, issn = {1687-0247}, journal = {International Mathematics Research Notices}, keywords = {General Mathematics}, number = {3}, pages = {669--697}, publisher = {Oxford University Press}, title = {{Waist of balls in hyperbolic and spherical spaces}}, doi = {10.1093/imrn/rny037}, volume = {2020}, year = {2020}, } @article{7788, abstract = {Mutations in NDUFS4, which encodes an accessory subunit of mitochondrial oxidative phosphorylation (OXPHOS) complex I (CI), induce Leigh syndrome (LS). LS is a poorly understood pediatric disorder featuring brain-specific anomalies and early death. To study the LS pathomechanism, we here compared OXPHOS proteomes between various Ndufs4−/− mouse tissues. Ndufs4−/− animals displayed significantly lower CI subunit levels in brain/diaphragm relative to other tissues (liver/heart/kidney/skeletal muscle), whereas other OXPHOS subunit levels were not reduced. Absence of NDUFS4 induced near complete absence of the NDUFA12 accessory subunit, a 50% reduction in other CI subunit levels, and an increase in specific CI assembly factors. Among the latter, NDUFAF2 was most highly increased. Regarding NDUFS4, NDUFA12 and NDUFAF2, identical results were obtained in Ndufs4−/− mouse embryonic fibroblasts (MEFs) and NDUFS4-mutated LS patient cells. Ndufs4−/− MEFs contained active CI in situ but blue-native-PAGE highlighted that NDUFAF2 attached to an inactive CI subcomplex (CI-830) and inactive assemblies of higher MW. In NDUFA12-mutated LS patient cells, NDUFA12 absence did not reduce NDUFS4 levels but triggered NDUFAF2 association to active CI. BN-PAGE revealed no such association in LS patient fibroblasts with mutations in other CI subunit-encoding genes where NDUFAF2 was attached to CI-830 (NDUFS1, NDUFV1 mutation) or not detected (NDUFS7 mutation). Supported by enzymological and CI in silico structural analysis, we conclude that absence of NDUFS4 induces near complete absence of NDUFA12 but not vice versa, and that NDUFAF2 stabilizes active CI in Ndufs4−/− mice and LS patient cells, perhaps in concert with mitochondrial inner membrane lipids.}, author = {Adjobo-Hermans, Merel J.W. and De Haas, Ria and Willems, Peter H.G.M. and Wojtala, Aleksandra and Van Emst-De Vries, Sjenet E. and Wagenaars, Jori A. and Van Den Brand, Mariel and Rodenburg, Richard J. and Smeitink, Jan A.M. and Nijtmans, Leo G. and Sazanov, Leonid A and Wieckowski, Mariusz R. and Koopman, Werner J.H.}, issn = {18792650}, journal = {Biochimica et Biophysica Acta - Bioenergetics}, number = {8}, publisher = {Elsevier}, title = {{NDUFS4 deletion triggers loss of NDUFA12 in Ndufs4−/− mice and Leigh syndrome patients: A stabilizing role for NDUFAF2}}, doi = {10.1016/j.bbabio.2020.148213}, volume = {1861}, year = {2020}, } @article{7789, abstract = {During embryonic and postnatal development, organs and tissues grow steadily to achieve their final size at the end of puberty. However, little is known about the cellular dynamics that mediate postnatal growth. By combining in vivo clonal lineage tracing, proliferation kinetics, single-cell transcriptomics, andin vitro micro-pattern experiments, we resolved the cellular dynamics taking place during postnatal skin epidermis expansion. Our data revealed that harmonious growth is engineered by a single population of developmental progenitors presenting a fixed fate imbalance of self-renewing divisions with an ever-decreasing proliferation rate. Single-cell RNA sequencing revealed that epidermal developmental progenitors form a more uniform population compared with adult stem and progenitor cells. Finally, we found that the spatial pattern of cell division orientation is dictated locally by the underlying collagen fiber orientation. Our results uncover a simple design principle of organ growth where progenitors and differentiated cells expand in harmony with their surrounding tissues.}, author = {Dekoninck, Sophie and Hannezo, Edouard B and Sifrim, Alejandro and Miroshnikova, Yekaterina A. and Aragona, Mariaceleste and Malfait, Milan and Gargouri, Souhir and De Neunheuser, Charlotte and Dubois, Christine and Voet, Thierry and Wickström, Sara A. and Simons, Benjamin D. and Blanpain, Cédric}, issn = {10974172}, journal = {Cell}, number = {3}, pages = {604--620.e22}, publisher = {Elsevier}, title = {{Defining the design principles of skin epidermis postnatal growth}}, doi = {10.1016/j.cell.2020.03.015}, volume = {181}, year = {2020}, } @article{7790, abstract = {We prove a lower bound for the free energy (per unit volume) of the two-dimensional Bose gas in the thermodynamic limit. We show that the free energy at density 𝜌 and inverse temperature 𝛽 differs from the one of the noninteracting system by the correction term 𝜋𝜌𝜌𝛽𝛽 . Here, is the scattering length of the interaction potential, and 𝛽 is the inverse Berezinskii–Kosterlitz–Thouless critical temperature for superfluidity. The result is valid in the dilute limit 𝜌 and if 𝛽𝜌 .}, author = {Deuchert, Andreas and Mayer, Simon and Seiringer, Robert}, issn = {20505094}, journal = {Forum of Mathematics, Sigma}, publisher = {Cambridge University Press}, title = {{The free energy of the two-dimensional dilute Bose gas. I. Lower bound}}, doi = {10.1017/fms.2020.17}, volume = {8}, year = {2020}, } @article{7792, abstract = {Phonon polaritons—light coupled to lattice vibrations—in polar van der Waals crystals are promising candidates for controlling the flow of energy on the nanoscale due to their strong field confinement, anisotropic propagation and ultra-long lifetime in the picosecond range1,2,3,4,5. However, the lack of tunability of their narrow and material-specific spectral range—the Reststrahlen band—severely limits their technological implementation. Here, we demonstrate that intercalation of Na atoms in the van der Waals semiconductor α-V2O5 enables a broad spectral shift of Reststrahlen bands, and that the phonon polaritons excited show ultra-low losses (lifetime of 4 ± 1 ps), similar to phonon polaritons in a non-intercalated crystal (lifetime of 6 ± 1 ps). We expect our intercalation method to be applicable to other van der Waals crystals, opening the door for the use of phonon polaritons in broad spectral bands in the mid-infrared domain.}, author = {Taboada-Gutiérrez, Javier and Álvarez-Pérez, Gonzalo and Duan, Jiahua and Ma, Weiliang and Crowley, Kyle and Prieto Gonzalez, Ivan and Bylinkin, Andrei and Autore, Marta and Volkova, Halyna and Kimura, Kenta and Kimura, Tsuyoshi and Berger, M. H. and Li, Shaojuan and Bao, Qiaoliang and Gao, Xuan P.A. and Errea, Ion and Nikitin, Alexey Y. and Hillenbrand, Rainer and Martín-Sánchez, Javier and Alonso-González, Pablo}, issn = {14764660}, journal = {Nature Materials}, pages = {964–968}, publisher = {Springer Nature}, title = {{Broad spectral tuning of ultra-low-loss polaritons in a van der Waals crystal by intercalation}}, doi = {10.1038/s41563-020-0665-0}, volume = {19}, year = {2020}, } @article{7793, abstract = {Hormonal signalling in animals often involves direct transcription factor-hormone interactions that modulate gene expression. In contrast, plant hormone signalling is most commonly based on de-repression via the degradation of transcriptional repressors. Recently, we uncovered a non-canonical signalling mechanism for the plant hormone auxin whereby auxin directly affects the activity of the atypical auxin response factor (ARF), ETTIN towards target genes without the requirement for protein degradation. Here we show that ETTIN directly binds auxin, leading to dissociation from co-repressor proteins of the TOPLESS/TOPLESS-RELATED family followed by histone acetylation and induction of gene expression. This mechanism is reminiscent of animal hormone signalling as it affects the activity towards regulation of target genes and provides the first example of a DNA-bound hormone receptor in plants. Whilst auxin affects canonical ARFs indirectly by facilitating degradation of Aux/IAA repressors, direct ETTIN-auxin interactions allow switching between repressive and de-repressive chromatin states in an instantly-reversible manner.}, author = {Kuhn, André and Ramans Harborough, Sigurd and McLaughlin, Heather M and Natarajan, Bhavani and Verstraeten, Inge and Friml, Jiří and Kepinski, Stefan and Østergaard, Lars}, issn = {2050-084X}, journal = {eLife}, publisher = {eLife Sciences Publications}, title = {{Direct ETTIN-auxin interaction controls chromatin states in gynoecium development}}, doi = {10.7554/elife.51787}, volume = {9}, year = {2020}, } @unpublished{7800, abstract = {De novo loss of function mutations in the ubiquitin ligase-encoding gene Cullin3 (CUL3) lead to autism spectrum disorder (ASD). Here, we used Cul3 mouse models to evaluate the consequences of Cul3 mutations in vivo. Our results show that Cul3 haploinsufficient mice exhibit deficits in motor coordination as well as ASD-relevant social and cognitive impairments. Cul3 mutant brain displays cortical lamination abnormalities due to defective neuronal migration and reduced numbers of excitatory and inhibitory neurons. In line with the observed abnormal columnar organization, Cul3 haploinsufficiency is associated with decreased spontaneous excitatory and inhibitory activity in the cortex. At the molecular level, employing a quantitative proteomic approach, we show that Cul3 regulates cytoskeletal and adhesion protein abundance in mouse embryos. Abnormal regulation of cytoskeletal proteins in Cul3 mutant neuronal cells results in atypical organization of the actin mesh at the cell leading edge, likely causing the observed migration deficits. In contrast to these important functions early in development, Cul3 deficiency appears less relevant at adult stages. In fact, induction of Cul3 haploinsufficiency in adult mice does not result in the behavioral defects observed in constitutive Cul3 haploinsufficient animals. Taken together, our data indicate that Cul3 has a critical role in the regulation of cytoskeletal proteins and neuronal migration and that ASD-associated defects and behavioral abnormalities are primarily due to Cul3 functions at early developmental stages.}, author = {Morandell, Jasmin and Schwarz, Lena A and Basilico, Bernadette and Tasciyan, Saren and Nicolas, Armel and Sommer, Christoph M and Kreuzinger, Caroline and Knaus, Lisa and Dobler, Zoe and Cacci, Emanuele and Danzl, Johann G and Novarino, Gaia}, booktitle = {bioRxiv}, publisher = {Cold Spring Harbor Laboratory}, title = {{Cul3 regulates cytoskeleton protein homeostasis and cell migration during a critical window of brain development}}, doi = {10.1101/2020.01.10.902064 }, year = {2020}, } @inproceedings{7802, abstract = {The Massively Parallel Computation (MPC) model is an emerging model which distills core aspects of distributed and parallel computation. It has been developed as a tool to solve (typically graph) problems in systems where the input is distributed over many machines with limited space. Recent work has focused on the regime in which machines have sublinear (in $n$, the number of nodes in the input graph) space, with randomized algorithms presented for fundamental graph problems of Maximal Matching and Maximal Independent Set. However, there have been no prior corresponding deterministic algorithms. A major challenge underlying the sublinear space setting is that the local space of each machine might be too small to store all the edges incident to a single node. This poses a considerable obstacle compared to the classical models in which each node is assumed to know and have easy access to its incident edges. To overcome this barrier we introduce a new graph sparsification technique that deterministically computes a low-degree subgraph with additional desired properties. The degree of the nodes in this subgraph is small in the sense that the edges of each node can be now stored on a single machine. This low-degree subgraph also has the property that solving the problem on this subgraph provides \emph{significant} global progress, i.e., progress towards solving the problem for the original input graph. Using this framework to derandomize the well-known randomized algorithm of Luby [SICOMP'86], we obtain $O(\log \Delta+\log\log n)$-round deterministic MPC algorithms for solving the fundamental problems of Maximal Matching and Maximal Independent Set with $O(n^{\epsilon})$ space on each machine for any constant $\epsilon > 0$. Based on the recent work of Ghaffari et al. [FOCS'18], this additive $O(\log\log n)$ factor is conditionally essential. These algorithms can also be shown to run in $O(\log \Delta)$ rounds in the closely related model of CONGESTED CLIQUE, improving upon the state-of-the-art bound of $O(\log^2 \Delta)$ rounds by Censor-Hillel et al. [DISC'17].}, author = {Czumaj, Artur and Davies, Peter and Parter, Merav}, booktitle = {Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2020)}, location = {Virtual Event, United States}, number = {7}, pages = {175--185}, publisher = {Association for Computing Machinery}, title = {{Graph sparsification for derandomizing massively parallel computation with low space}}, doi = {10.1145/3350755.3400282}, year = {2020}, } @inproceedings{7803, abstract = {We settle the complexity of the (Δ+1)-coloring and (Δ+1)-list coloring problems in the CONGESTED CLIQUE model by presenting a simple deterministic algorithm for both problems running in a constant number of rounds. This matches the complexity of the recent breakthrough randomized constant-round (Δ+1)-list coloring algorithm due to Chang et al. (PODC'19), and significantly improves upon the state-of-the-art O(logΔ)-round deterministic (Δ+1)-coloring bound of Parter (ICALP'18). A remarkable property of our algorithm is its simplicity. Whereas the state-of-the-art randomized algorithms for this problem are based on the quite involved local coloring algorithm of Chang et al. (STOC'18), our algorithm can be described in just a few lines. At a high level, it applies a careful derandomization of a recursive procedure which partitions the nodes and their respective palettes into separate bins. We show that after O(1) recursion steps, the remaining uncolored subgraph within each bin has linear size, and thus can be solved locally by collecting it to a single node. This algorithm can also be implemented in the Massively Parallel Computation (MPC) model provided that each machine has linear (in n, the number of nodes in the input graph) space. We also show an extension of our algorithm to the MPC regime in which machines have sublinear space: we present the first deterministic (Δ+1)-list coloring algorithm designed for sublinear-space MPC, which runs in O(logΔ+loglogn) rounds.}, author = {Czumaj, Artur and Davies, Peter and Parter, Merav}, booktitle = {Proceedings of the 2020 ACM Symposium on Principles of Distributed Computing}, location = {Salerno, Italy}, pages = {309--318}, publisher = {Association for Computing Machinery}, title = {{Simple, deterministic, constant-round coloring in the congested clique}}, doi = {10.1145/3382734.3405751}, year = {2020}, } @article{7804, abstract = {Besides pro-inflammatory roles, the ancient cytokine interleukin-17 (IL-17) modulates neural circuit function. We investigate IL-17 signaling in neurons, and the extent it can alter organismal phenotypes. We combine immunoprecipitation and mass spectrometry to biochemically characterize endogenous signaling complexes that function downstream of IL-17 receptors in C. elegans neurons. We identify the paracaspase MALT-1 as a critical output of the pathway. MALT1 mediates signaling from many immune receptors in mammals, but was not previously implicated in IL-17 signaling or nervous system function. C. elegans MALT-1 forms a complex with homologs of Act1 and IRAK and appears to function both as a scaffold and a protease. MALT-1 is expressed broadly in the C. elegans nervous system, and neuronal IL-17–MALT-1 signaling regulates multiple phenotypes, including escape behavior, associative learning, immunity and longevity. Our data suggest MALT1 has an ancient role modulating neural circuit function downstream of IL-17 to remodel physiology and behavior.}, author = {Flynn, Sean M. and Chen, Changchun and Artan, Murat and Barratt, Stephen and Crisp, Alastair and Nelson, Geoffrey M. and Peak-Chew, Sew Yeu and Begum, Farida and Skehel, Mark and De Bono, Mario}, issn = {20411723}, journal = {Nature Communications}, publisher = {Springer Nature}, title = {{MALT-1 mediates IL-17 neural signaling to regulate C. elegans behavior, immunity and longevity}}, doi = {10.1038/s41467-020-15872-y}, volume = {11}, year = {2020}, } @article{7805, abstract = {Plants as non-mobile organisms constantly integrate varying environmental signals to flexibly adapt their growth and development. Local fluctuations in water and nutrient availability, sudden changes in temperature or other abiotic and biotic stresses can trigger changes in the growth of plant organs. Multiple mutually interconnected hormonal signaling cascades act as essential endogenous translators of these exogenous signals in the adaptive responses of plants. Although the molecular backbones of hormone transduction pathways have been identified, the mechanisms underlying their interactions are largely unknown. Here, using genome wide transcriptome profiling we identify an auxin and cytokinin cross-talk component; SYNERGISTIC ON AUXIN AND CYTOKININ 1 (SYAC1), whose expression in roots is strictly dependent on both of these hormonal pathways. We show that SYAC1 is a regulator of secretory pathway, whose enhanced activity interferes with deposition of cell wall components and can fine-tune organ growth and sensitivity to soil pathogens.}, author = {Hurny, Andrej and Cuesta, Candela and Cavallari, Nicola and Ötvös, Krisztina and Duclercq, Jerome and Dokládal, Ladislav and Montesinos López, Juan C and Gallemi, Marçal and Semeradova, Hana and Rauter, Thomas and Stenzel, Irene and Persiau, Geert and Benade, Freia and Bhalearo, Rishikesh and Sýkorová, Eva and Gorzsás, András and Sechet, Julien and Mouille, Gregory and Heilmann, Ingo and De Jaeger, Geert and Ludwig-Müller, Jutta and Benková, Eva}, issn = {20411723}, journal = {Nature Communications}, publisher = {Springer Nature}, title = {{Synergistic on Auxin and Cytokinin 1 positively regulates growth and attenuates soil pathogen resistance}}, doi = {10.1038/s41467-020-15895-5}, volume = {11}, year = {2020}, } @inproceedings{7806, abstract = {We consider the following decision problem EMBEDk→d in computational topology (where k ≤ d are fixed positive integers): Given a finite simplicial complex K of dimension k, does there exist a (piecewise-linear) embedding of K into ℝd? The special case EMBED1→2 is graph planarity, which is decidable in linear time, as shown by Hopcroft and Tarjan. In higher dimensions, EMBED2→3 and EMBED3→3 are known to be decidable (as well as NP-hard), and recent results of Čadek et al. in computational homotopy theory, in combination with the classical Haefliger–Weber theorem in geometric topology, imply that EMBEDk→d can be solved in polynomial time for any fixed pair (k, d) of dimensions in the so-called metastable range . Here, by contrast, we prove that EMBEDk→d is algorithmically undecidable for almost all pairs of dimensions outside the metastable range, namely for . This almost completely resolves the decidability vs. undecidability of EMBEDk→d in higher dimensions and establishes a sharp dichotomy between polynomial-time solvability and undecidability. Our result complements (and in a wide range of dimensions strengthens) earlier results of Matoušek, Tancer, and the second author, who showed that EMBEDk→d is undecidable for 4 ≤ k ϵ {d – 1, d}, and NP-hard for all remaining pairs (k, d) outside the metastable range and satisfying d ≥ 4.}, author = {Filakovský, Marek and Wagner, Uli and Zhechev, Stephan Y}, booktitle = {Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms}, isbn = {9781611975994}, location = {Salt Lake City, UT, United States}, pages = {767--785}, publisher = {SIAM}, title = {{Embeddability of simplicial complexes is undecidable}}, doi = {10.1137/1.9781611975994.47}, volume = {2020-January}, year = {2020}, } @inproceedings{7807, abstract = {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.}, author = {Wagner, Uli and Welzl, Emo}, booktitle = {Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms}, isbn = {9781611975994}, location = {Salt Lake City, UT, United States}, pages = {2823--2841}, publisher = {SIAM}, title = {{Connectivity of triangulation flip graphs in the plane (Part I: Edge flips)}}, doi = {10.1137/1.9781611975994.172}, volume = {2020-January}, year = {2020}, } @inproceedings{7808, abstract = {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.}, author = {Giacobbe, Mirco and Henzinger, Thomas A and Lechner, Mathias}, booktitle = {International Conference on Tools and Algorithms for the Construction and Analysis of Systems}, isbn = {9783030452360}, issn = {16113349}, location = {Dublin, Ireland}, pages = {79--97}, publisher = {Springer Nature}, title = {{How many bits does it take to quantize your neural network?}}, doi = {10.1007/978-3-030-45237-7_5}, volume = {12079}, year = {2020}, } @inproceedings{7810, abstract = {Interprocedural data-flow analyses form an expressive and useful paradigm of numerous static analysis applications, such as live variables analysis, alias analysis and null pointers analysis. The most widely-used framework for interprocedural data-flow analysis is IFDS, which encompasses distributive data-flow functions over a finite domain. On-demand data-flow analyses restrict the focus of the analysis on specific program locations and data facts. This setting provides a natural split between (i) an offline (or preprocessing) phase, where the program is partially analyzed and analysis summaries are created, and (ii) an online (or query) phase, where analysis queries arrive on demand and the summaries are used to speed up answering queries. In this work, we consider on-demand IFDS analyses where the queries concern program locations of the same procedure (aka same-context queries). We exploit the fact that flow graphs of programs have low treewidth to develop faster algorithms that are space and time optimal for many common data-flow analyses, in both the preprocessing and the query phase. We also use treewidth to develop query solutions that are embarrassingly parallelizable, i.e. the total work for answering each query is split to a number of threads such that each thread performs only a constant amount of work. Finally, we implement a static analyzer based on our algorithms, and perform a series of on-demand analysis experiments on standard benchmarks. Our experimental results show a drastic speed-up of the queries after only a lightweight preprocessing phase, which significantly outperforms existing techniques.}, author = {Chatterjee, Krishnendu and Goharshady, Amir Kafshdar and Ibsen-Jensen, Rasmus and Pavlogiannis, Andreas}, booktitle = {European Symposium on Programming}, isbn = {9783030449131}, issn = {16113349}, location = {Dublin, Ireland}, pages = {112--140}, publisher = {Springer Nature}, title = {{Optimal and perfectly parallel algorithms for on-demand data-flow analysis}}, doi = {10.1007/978-3-030-44914-8_5}, volume = {12075}, year = {2020}, }