@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},
pages = {31},
publisher = {Cold Spring Harbor Laboratory},
title = {{Cul3 regulates cytoskeleton protein homeostasis and cell migration during a critical window of brain development}},
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 = {Philadelphia, PA, United States},
publisher = {Association for Computing Machinery},
title = {{Graph sparsification for derandomizing massively parallel computation with low space}},
year = {2020},
}
@inproceedings{7803,
abstract = {We settle the complexity of the $(\Delta+1)$-coloring and $(\Delta+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 $(\Delta+1)$-list coloring algorithm due to Chang et al. (PODC'19), and significantly improves upon the state-of-the-art deterministic bounds of $O(\log \Delta)$ rounds for $(\Delta+1)$-coloring and $O(\log^3 \Delta)$ rounds for $(\Delta+1)$-list coloring.
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 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 $(\Delta+1)$-list coloring algorithm designed for sublinear-space MPC, which runs in $O(\log \Delta + \log\log n)$ rounds.},
author = {Czumaj, Artur and Davies, Peter and Parter, Merav},
booktitle = {Proceedings of the 2020 ACM Symposium on Principles of Distributed Computing (PODC 2020)},
location = {Salerno, Italy},
publisher = {Association for Computing Machinery},
title = {{Simple, deterministic, constant-round coloring in the congested clique}},
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},
}
@article{7814,
abstract = {Scientific research is to date largely restricted to wealthy laboratories in developed nations due to the necessity of complex and expensive equipment. This inequality limits the capacity of science to be used as a diplomatic channel. Maker movements use open-source technologies including additive manufacturing (3D printing) and laser cutting, together with low-cost computers for developing novel products. This movement is setting the groundwork for a revolution, allowing scientific equipment to be sourced at a fraction of the cost and has the potential to increase the availability of equipment for scientists around the world. Science education is increasingly recognized as another channel for science diplomacy. In this perspective, we introduce the idea that the Maker movement and open-source technologies have the potential to revolutionize science, technology, engineering and mathematics (STEM) education worldwide. We present an open-source STEM didactic tool called SCOPES (Sparking Curiosity through Open-source Platforms in Education and Science). SCOPES is self-contained, independent of local resources, and cost-effective. SCOPES can be adapted to communicate complex subjects from genetics to neurobiology, perform real-world biological experiments and explore digitized scientific samples. We envision such platforms will enhance science diplomacy by providing a means for scientists to share their findings with classrooms and for educators to incorporate didactic concepts into STEM lessons. By providing students the opportunity to design, perform, and share scientific experiments, students also experience firsthand the benefits of a multinational scientific community. We provide instructions on how to build and use SCOPES on our webpage: http://scopeseducation.org.},
author = {Beattie, Robert J and Hippenmeyer, Simon and Pauler, Florian},
issn = {2504-284X},
journal = {Frontiers in Education},
publisher = {Frontiers Media},
title = {{SCOPES: Sparking curiosity through Open-Source platforms in education and science}},
doi = {10.3389/feduc.2020.00048},
volume = {5},
year = {2020},
}