@inproceedings{297, abstract = {Graph games played by two players over finite-state graphs are central in many problems in computer science. In particular, graph games with ω -regular winning conditions, specified as parity objectives, which can express properties such as safety, liveness, fairness, are the basic framework for verification and synthesis of reactive systems. The decisions for a player at various states of the graph game are represented as strategies. While the algorithmic problem for solving graph games with parity objectives has been widely studied, the most prominent data-structure for strategy representation in graph games has been binary decision diagrams (BDDs). However, due to the bit-level representation, BDDs do not retain the inherent flavor of the decisions of strategies, and are notoriously hard to minimize to obtain succinct representation. In this work we propose decision trees for strategy representation in graph games. Decision trees retain the flavor of decisions of strategies and allow entropy-based minimization to obtain succinct trees. However, decision trees work in settings (e.g., probabilistic models) where errors are allowed, and overfitting of data is typically avoided. In contrast, for strategies in graph games no error is allowed, and the decision tree must represent the entire strategy. We develop new techniques to extend decision trees to overcome the above obstacles, while retaining the entropy-based techniques to obtain succinct trees. We have implemented our techniques to extend the existing decision tree solvers. We present experimental results for problems in reactive synthesis to show that decision trees provide a much more efficient data-structure for strategy representation as compared to BDDs.}, author = {Brázdil, Tomáš and Chatterjee, Krishnendu and Kretinsky, Jan and Toman, Viktor}, location = {Thessaloniki, Greece}, pages = {385 -- 407}, publisher = {Springer}, title = {{Strategy representation by decision trees in reactive synthesis}}, doi = {10.1007/978-3-319-89960-2_21}, volume = {10805}, year = {2018}, } @inproceedings{141, abstract = {Given a model and a specification, the fundamental model-checking problem asks for algorithmic verification of whether the model satisfies the specification. We consider graphs and Markov decision processes (MDPs), which are fundamental models for reactive systems. One of the very basic specifications that arise in verification of reactive systems is the strong fairness (aka Streett) objective. Given different types of requests and corresponding grants, the objective requires that for each type, if the request event happens infinitely often, then the corresponding grant event must also happen infinitely often. All ω -regular objectives can be expressed as Streett objectives and hence they are canonical in verification. To handle the state-space explosion, symbolic algorithms are required that operate on a succinct implicit representation of the system rather than explicitly accessing the system. While explicit algorithms for graphs and MDPs with Streett objectives have been widely studied, there has been no improvement of the basic symbolic algorithms. The worst-case numbers of symbolic steps required for the basic symbolic algorithms are as follows: quadratic for graphs and cubic for MDPs. In this work we present the first sub-quadratic symbolic algorithm for graphs with Streett objectives, and our algorithm is sub-quadratic even for MDPs. Based on our algorithmic insights we present an implementation of the new symbolic approach and show that it improves the existing approach on several academic benchmark examples.}, author = {Chatterjee, Krishnendu and Henzinger, Monika H and Loitzenbauer, Veronika and Oraee, Simin and Toman, Viktor}, location = {Oxford, United Kingdom}, pages = {178--197}, publisher = {Springer}, title = {{Symbolic algorithms for graphs and Markov decision processes with fairness objectives}}, doi = {10.1007/978-3-319-96142-2_13}, volume = {10982}, year = {2018}, } @inproceedings{298, abstract = {Memory-hard functions (MHF) are functions whose evaluation cost is dominated by memory cost. MHFs are egalitarian, in the sense that evaluating them on dedicated hardware (like FPGAs or ASICs) is not much cheaper than on off-the-shelf hardware (like x86 CPUs). MHFs have interesting cryptographic applications, most notably to password hashing and securing blockchains. Alwen and Serbinenko [STOC’15] define the cumulative memory complexity (cmc) of a function as the sum (over all time-steps) of the amount of memory required to compute the function. They advocate that a good MHF must have high cmc. Unlike previous notions, cmc takes into account that dedicated hardware might exploit amortization and parallelism. Still, cmc has been critizised as insufficient, as it fails to capture possible time-memory trade-offs; as memory cost doesn’t scale linearly, functions with the same cmc could still have very different actual hardware cost. In this work we address this problem, and introduce the notion of sustained-memory complexity, which requires that any algorithm evaluating the function must use a large amount of memory for many steps. We construct functions (in the parallel random oracle model) whose sustained-memory complexity is almost optimal: our function can be evaluated using n steps and O(n/log(n)) memory, in each step making one query to the (fixed-input length) random oracle, while any algorithm that can make arbitrary many parallel queries to the random oracle, still needs Ω(n/log(n)) memory for Ω(n) steps. As has been done for various notions (including cmc) before, we reduce the task of constructing an MHFs with high sustained-memory complexity to proving pebbling lower bounds on DAGs. Our main technical contribution is the construction is a family of DAGs on n nodes with constant indegree with high “sustained-space complexity”, meaning that any parallel black-pebbling strategy requires Ω(n/log(n)) pebbles for at least Ω(n) steps. Along the way we construct a family of maximally “depth-robust” DAGs with maximum indegree O(logn) , improving upon the construction of Mahmoody et al. [ITCS’13] which had maximum indegree O(log2n⋅}, author = {Alwen, Joel F and Blocki, Jeremiah and Pietrzak, Krzysztof Z}, location = {Tel Aviv, Israel}, pages = {99 -- 130}, publisher = {Springer}, title = {{Sustained space complexity}}, doi = {10.1007/978-3-319-78375-8_4}, volume = {10821}, year = {2018}, } @article{36, abstract = {Wheat (Triticum ssp.) is one of the most important human food sources. However, this crop is very sensitive to temperature changes. Specifically, processes during wheat leaf, flower, and seed development and photosynthesis, which all contribute to the yield of this crop, are affected by high temperature. While this has to some extent been investigated on physiological, developmental, and molecular levels, very little is known about early signalling events associated with an increase in temperature. Phosphorylation-mediated signalling mechanisms, which are quick and dynamic, are associated with plant growth and development, also under abiotic stress conditions. Therefore, we probed the impact of a short-term and mild increase in temperature on the wheat leaf and spikelet phosphoproteome. In total, 3822 (containing 5178 phosphosites) and 5581 phosphopeptides (containing 7023 phosphosites) were identified in leaf and spikelet samples, respectively. Following statistical analysis, the resulting data set provides the scientific community with a first large-scale plant phosphoproteome under the control of higher ambient temperature. This community resource on the high temperature-mediated wheat phosphoproteome will be valuable for future studies. Our analyses also revealed a core set of common proteins between leaf and spikelet, suggesting some level of conserved regulatory mechanisms. Furthermore, we observed temperature-regulated interconversion of phosphoforms, which probably impacts protein activity.}, author = {Vu, Lam and Zhu, Tingting and Verstraeten, Inge and Van De Cotte, Brigitte and Gevaert, Kris and De Smet, Ive}, journal = {Journal of Experimental Botany}, number = {19}, pages = {4609 -- 4624}, publisher = {Oxford University Press}, title = {{Temperature-induced changes in the wheat phosphoproteome reveal temperature-regulated interconversion of phosphoforms}}, doi = {10.1093/jxb/ery204}, volume = {69}, year = {2018}, } @article{326, abstract = {Three-dimensional (3D) super-resolution microscopy technique structured illumination microscopy (SIM) imaging of dendritic spines along the dendrite has not been previously performed in fixed tissues, mainly due to deterioration of the stripe pattern of the excitation laser induced by light scattering and optical aberrations. To address this issue and solve these optical problems, we applied a novel clearing reagent, LUCID, to fixed brains. In SIM imaging, the penetration depth and the spatial resolution were improved in LUCID-treated slices, and 160-nm spatial resolution was obtained in a large portion of the imaging volume on a single apical dendrite. Furthermore, in a morphological analysis of spine heads of layer V pyramidal neurons (L5PNs) in the medial prefrontal cortex (mPFC) of chronic dexamethasone (Dex)-treated mice, SIM imaging revealed an altered distribution of spine forms that could not be detected by high-NA confocal imaging. Thus, super-resolution SIM imaging represents a promising high-throughput method for revealing spine morphologies in single dendrites.}, author = {Sawada, Kazuaki and Kawakami, Ryosuke and Shigemoto, Ryuichi and Nemoto, Tomomi}, journal = {European Journal of Neuroscience}, number = {9}, pages = {1033 -- 1042}, publisher = {Wiley}, title = {{Super resolution structural analysis of dendritic spines using three-dimensional structured illumination microscopy in cleared mouse brain slices}}, doi = {10.1111/ejn.13901}, volume = {47}, year = {2018}, } @article{5770, abstract = {Retroviruses assemble and bud from infected cells in an immature form and require proteolytic maturation for infectivity. The CA (capsid) domains of the Gag polyproteins assemble a protein lattice as a truncated sphere in the immature virion. Proteolytic cleavage of Gag induces dramatic structural rearrangements; a subset of cleaved CA subsequently assembles into the mature core, whose architecture varies among retroviruses. Murine leukemia virus (MLV) is the prototypical γ-retrovirus and serves as the basis of retroviral vectors, but the structure of the MLV CA layer is unknown. Here we have combined X-ray crystallography with cryoelectron tomography to determine the structures of immature and mature MLV CA layers within authentic viral particles. This reveals the structural changes associated with maturation, and, by comparison with HIV-1, uncovers conserved and variable features. In contrast to HIV-1, most MLV CA is used for assembly of the mature core, which adopts variable, multilayered morphologies and does not form a closed structure. Unlike in HIV-1, there is similarity between protein–protein interfaces in the immature MLV CA layer and those in the mature CA layer, and structural maturation of MLV could be achieved through domain rotations that largely maintain hexameric interactions. Nevertheless, the dramatic architectural change on maturation indicates that extensive disassembly and reassembly are required for mature core growth. The core morphology suggests that wrapping of the genome in CA sheets may be sufficient to protect the MLV ribonucleoprotein during cell entry.}, author = {Qu, Kun and Glass, Bärbel and Doležal, Michal and Schur, Florian and Murciano, Brice and Rein, Alan and Rumlová, Michaela and Ruml, Tomáš and Kräusslich, Hans-Georg and Briggs, John A. G.}, issn = {00278424}, journal = {Proceedings of the National Academy of Sciences}, number = {50}, pages = {E11751--E11760}, publisher = {Proceedings of the National Academy of Sciences}, title = {{Structure and architecture of immature and mature murine leukemia virus capsids}}, doi = {10.1073/pnas.1811580115}, volume = {115}, year = {2018}, } @article{608, abstract = {Synthesis is the automated construction of a system from its specification. In real life, hardware and software systems are rarely constructed from scratch. Rather, a system is typically constructed from a library of components. Lustig and Vardi formalized this intuition and studied LTL synthesis from component libraries. In real life, designers seek optimal systems. In this paper we add optimality considerations to the setting. We distinguish between quality considerations (for example, size - the smaller a system is, the better it is), and pricing (for example, the payment to the company who manufactured the component). We study the problem of designing systems with minimal quality-cost and price. A key point is that while the quality cost is individual - the choices of a designer are independent of choices made by other designers that use the same library, pricing gives rise to a resource-allocation game - designers that use the same component share its price, with the share being proportional to the number of uses (a component can be used several times in a design). We study both closed and open settings, and in both we solve the problem of finding an optimal design. In a setting with multiple designers, we also study the game-theoretic problems of the induced resource-allocation game.}, author = {Avni, Guy and Kupferman, Orna}, journal = {Theoretical Computer Science}, pages = {50 -- 72}, publisher = {Elsevier}, title = {{Synthesis from component libraries with costs}}, doi = {10.1016/j.tcs.2017.11.001}, volume = {712}, 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}, } @article{403, abstract = {The ability to adapt growth and development to temperature variations is crucial to generate plant varieties resilient to predicted temperature changes. However, the mechanisms underlying plant response to progressive increases in temperature have just started to be elucidated. Here, we report that the Cyclin-dependent Kinase G1 (CDKG1) is a central element in a thermo-sensitive mRNA splicing cascade that transduces changes in ambient temperature into differential expression of the fundamental spliceosome component, ATU2AF65A. CDKG1 is alternatively spliced in a temperature-dependent manner. We found that this process is partly dependent on both the Cyclin-dependent Kinase G2 (CDKG2) and the interacting co-factor CYCLIN L1 resulting in two distinct messenger RNAs. Relative abundance of both CDKG1 transcripts correlates with ambient temperature and possibly with different expression levels of the associated protein isoforms. Both CDKG1 alternative transcripts are necessary to fully complement the expression of ATU2AF65A across the temperature range. Our data support a previously unidentified temperature-dependent mechanism based on the alternative splicing of CDKG1 and regulated by CDKG2 and CYCLIN L1. We propose that changes in ambient temperature affect the relative abundance of CDKG1 transcripts and this in turn translates into differential CDKG1 protein expression coordinating the alternative splicing of ATU2AF65A. This article is protected by copyright. All rights reserved.}, author = {Cavallari, Nicola and Nibau, Candida and Fuchs, Armin and Dadarou, Despoina and Barta, Andrea and Doonan, John}, journal = {The Plant Journal}, number = {6}, pages = {1010 -- 1022}, publisher = {Wiley}, title = {{The cyclin‐dependent kinase G group defines a thermo‐sensitive alternative splicing circuit modulating the expression of Arabidopsis ATU 2AF 65A}}, doi = {10.1111/tpj.13914}, volume = {94}, year = {2018}, } @inproceedings{156, abstract = {Imprecision in timing can sometimes be beneficial: Metric interval temporal logic (MITL), disabling the expression of punctuality constraints, was shown to translate to timed automata, yielding an elementary decision procedure. We show how this principle extends to other forms of dense-time specification using regular expressions. By providing a clean, automaton-based formal framework for non-punctual languages, we are able to recover and extend several results in timed systems. Metric interval regular expressions (MIRE) are introduced, providing regular expressions with non-singular duration constraints. We obtain that MIRE are expressively complete relative to a class of one-clock timed automata, which can be determinized using additional clocks. Metric interval dynamic logic (MIDL) is then defined using MIRE as temporal modalities. We show that MIDL generalizes known extensions of MITL, while translating to timed automata at comparable cost.}, author = {Ferrere, Thomas}, location = {Oxford, UK}, pages = {147 -- 164}, publisher = {Springer}, title = {{The compound interest in relaxing punctuality}}, doi = {10.1007/978-3-319-95582-7_9}, volume = {10951}, year = {2018}, }