@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}, }