--- _id: '1607' abstract: - lang: eng text: We consider the core algorithmic problems related to verification of systems with respect to three classical quantitative properties, namely, the mean-payoff property, the ratio property, and the minimum initial credit for energy property. The algorithmic problem given a graph and a quantitative property asks to compute the optimal value (the infimum value over all traces) from every node of the graph. We consider graphs with constant treewidth, and it is well-known that the control-flow graphs of most programs have constant treewidth. Let n denote the number of nodes of a graph, m the number of edges (for constant treewidth graphs m=O(n)) and W the largest absolute value of the weights. Our main theoretical results are as follows. First, for constant treewidth graphs we present an algorithm that approximates the mean-payoff value within a multiplicative factor of ϵ in time O(n⋅log(n/ϵ)) and linear space, as compared to the classical algorithms that require quadratic time. Second, for the ratio property we present an algorithm that for constant treewidth graphs works in time O(n⋅log(|a⋅b|))=O(n⋅log(n⋅W)), when the output is ab, as compared to the previously best known algorithm with running time O(n2⋅log(n⋅W)). Third, for the minimum initial credit problem we show that (i) for general graphs the problem can be solved in O(n2⋅m) time and the associated decision problem can be solved in O(n⋅m) time, improving the previous known O(n3⋅m⋅log(n⋅W)) and O(n2⋅m) bounds, respectively; and (ii) for constant treewidth graphs we present an algorithm that requires O(n⋅logn) time, improving the previous known O(n4⋅log(n⋅W)) bound. We have implemented some of our algorithms and show that they present a significant speedup on standard benchmarks. acknowledgement: 'The research was partly supported by Austrian Science Fund (FWF) Grant No P23499- N23, FWF NFN Grant No S11407-N23 (RiSE/SHiNE), ERC Start grant (279307: Graph Games), and Microsoft faculty fellows award.' alternative_title: - LNCS author: - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Rasmus full_name: Ibsen-Jensen, Rasmus id: 3B699956-F248-11E8-B48F-1D18A9856A87 last_name: Ibsen-Jensen orcid: 0000-0003-4783-0389 - first_name: Andreas full_name: Pavlogiannis, Andreas id: 49704004-F248-11E8-B48F-1D18A9856A87 last_name: Pavlogiannis orcid: 0000-0002-8943-0722 citation: ama: 'Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. Faster algorithms for quantitative verification in constant treewidth graphs. In: Vol 9206. Springer; 2015:140-157. doi:10.1007/978-3-319-21690-4_9' apa: 'Chatterjee, K., Ibsen-Jensen, R., & Pavlogiannis, A. (2015). Faster algorithms for quantitative verification in constant treewidth graphs (Vol. 9206, pp. 140–157). Presented at the CAV: Computer Aided Verification, San Francisco, CA, USA: Springer. https://doi.org/10.1007/978-3-319-21690-4_9' chicago: Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Andreas Pavlogiannis. “Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs,” 9206:140–57. Springer, 2015. https://doi.org/10.1007/978-3-319-21690-4_9. ieee: 'K. Chatterjee, R. Ibsen-Jensen, and A. Pavlogiannis, “Faster algorithms for quantitative verification in constant treewidth graphs,” presented at the CAV: Computer Aided Verification, San Francisco, CA, USA, 2015, vol. 9206, pp. 140–157.' ista: 'Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. 2015. Faster algorithms for quantitative verification in constant treewidth graphs. CAV: Computer Aided Verification, LNCS, vol. 9206, 140–157.' mla: Chatterjee, Krishnendu, et al. Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs. Vol. 9206, Springer, 2015, pp. 140–57, doi:10.1007/978-3-319-21690-4_9. short: K. Chatterjee, R. Ibsen-Jensen, A. Pavlogiannis, in:, Springer, 2015, pp. 140–157. conference: end_date: 2015-07-24 location: San Francisco, CA, USA name: 'CAV: Computer Aided Verification' start_date: 2015-07-18 date_created: 2018-12-11T11:52:59Z date_published: 2015-07-16T00:00:00Z date_updated: 2023-09-07T12:01:59Z day: '16' department: - _id: KrCh doi: 10.1007/978-3-319-21690-4_9 ec_funded: 1 intvolume: ' 9206' language: - iso: eng main_file_link: - open_access: '1' url: http://arxiv.org/abs/1504.07384 month: '07' oa: 1 oa_version: Preprint page: 140 - 157 project: - _id: 2584A770-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: P 23499-N23 name: Modern Graph Algorithmic Techniques in Formal Verification - _id: 25832EC2-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: S 11407_N23 name: Rigorous Systems Engineering - _id: 2581B60A-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '279307' name: 'Quantitative Graph Games: Theory and Applications' - _id: 2587B514-B435-11E9-9278-68D0E5697425 name: Microsoft Research Faculty Fellowship publication_status: published publisher: Springer publist_id: '5560' quality_controlled: '1' related_material: record: - id: '5430' relation: earlier_version status: public - id: '5437' relation: earlier_version status: public - id: '821' relation: dissertation_contains status: public scopus_import: 1 status: public title: Faster algorithms for quantitative verification in constant treewidth graphs type: conference user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87 volume: 9206 year: '2015' ... --- _id: '1714' abstract: - lang: eng text: 'We present a flexible framework for the automated competitive analysis of on-line scheduling algorithms for firm-deadline real-time tasks based on multi-objective graphs: Given a task set and an on-line scheduling algorithm specified as a labeled transition system, along with some optional safety, liveness, and/or limit-average constraints for the adversary, we automatically compute the competitive ratio of the algorithm w.r.t. A clairvoyant scheduler. We demonstrate the flexibility and power of our approach by comparing the competitive ratio of several on-line algorithms, including Dover, that have been proposed in the past, for various task sets. Our experimental results reveal that none of these algorithms is universally optimal, in the sense that there are task sets where other schedulers provide better performance. Our framework is hence a very useful design tool for selecting optimal algorithms for a given application.' article_processing_charge: No author: - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Andreas full_name: Pavlogiannis, Andreas id: 49704004-F248-11E8-B48F-1D18A9856A87 last_name: Pavlogiannis orcid: 0000-0002-8943-0722 - first_name: Alexander full_name: Kößler, Alexander last_name: Kößler - first_name: Ulrich full_name: Schmid, Ulrich last_name: Schmid citation: ama: 'Chatterjee K, Pavlogiannis A, Kößler A, Schmid U. A framework for automated competitive analysis of on-line scheduling of firm-deadline tasks. In: Real-Time Systems Symposium. Vol 2015. IEEE; 2015:118-127. doi:10.1109/RTSS.2014.9' apa: 'Chatterjee, K., Pavlogiannis, A., Kößler, A., & Schmid, U. (2015). A framework for automated competitive analysis of on-line scheduling of firm-deadline tasks. In Real-Time Systems Symposium (Vol. 2015, pp. 118–127). Rome, Italy: IEEE. https://doi.org/10.1109/RTSS.2014.9' chicago: Chatterjee, Krishnendu, Andreas Pavlogiannis, Alexander Kößler, and Ulrich Schmid. “A Framework for Automated Competitive Analysis of On-Line Scheduling of Firm-Deadline Tasks.” In Real-Time Systems Symposium, 2015:118–27. IEEE, 2015. https://doi.org/10.1109/RTSS.2014.9. ieee: K. Chatterjee, A. Pavlogiannis, A. Kößler, and U. Schmid, “A framework for automated competitive analysis of on-line scheduling of firm-deadline tasks,” in Real-Time Systems Symposium, Rome, Italy, 2015, vol. 2015, no. January, pp. 118–127. ista: 'Chatterjee K, Pavlogiannis A, Kößler A, Schmid U. 2015. A framework for automated competitive analysis of on-line scheduling of firm-deadline tasks. Real-Time Systems Symposium. RTSS: Real-Time Systems Symposium vol. 2015, 118–127.' mla: Chatterjee, Krishnendu, et al. “A Framework for Automated Competitive Analysis of On-Line Scheduling of Firm-Deadline Tasks.” Real-Time Systems Symposium, vol. 2015, no. January, IEEE, 2015, pp. 118–27, doi:10.1109/RTSS.2014.9. short: K. Chatterjee, A. Pavlogiannis, A. Kößler, U. Schmid, in:, Real-Time Systems Symposium, IEEE, 2015, pp. 118–127. conference: end_date: 2014-12-05 location: Rome, Italy name: 'RTSS: Real-Time Systems Symposium' start_date: 2014-12-02 date_created: 2018-12-11T11:53:37Z date_published: 2015-01-15T00:00:00Z date_updated: 2023-09-07T12:01:59Z day: '15' department: - _id: KrCh doi: 10.1109/RTSS.2014.9 intvolume: ' 2015' issue: January language: - iso: eng month: '01' oa_version: None page: 118 - 127 publication: Real-Time Systems Symposium publication_status: published publisher: IEEE publist_id: '5417' quality_controlled: '1' related_material: record: - id: '5423' relation: earlier_version status: public - id: '821' relation: dissertation_contains status: public scopus_import: 1 status: public title: A framework for automated competitive analysis of on-line scheduling of firm-deadline tasks type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 2015 year: '2015' ... --- _id: '1633' abstract: - lang: eng text: "We present a method for simulating brittle fracture under the assumptions of quasi-static linear elastic fracture mechanics (LEFM). Using the boundary element method (BEM) and Lagrangian crack-fronts, we produce highly detailed fracture surfaces. The computational cost of the BEM is alleviated by using a low-resolution mesh and interpolating the resulting stress intensity factors when propagating the high-resolution crack-front.\r\n\r\nOur system produces physics-based fracture surfaces with high spatial and temporal resolution, taking spatial variation of material toughness and/or strength into account. It also allows for crack initiation to be handled separately from crack propagation, which is not only more reasonable from a physics perspective, but can also be used to control the simulation.\r\n\r\nSeparating the resolution of the crack-front from the resolution of the computational mesh increases the efficiency and therefore the amount of visual detail on the resulting fracture surfaces. The BEM also allows us to re-use previously computed blocks of the system matrix." article_number: '151' author: - first_name: David full_name: Hahn, David id: 357A6A66-F248-11E8-B48F-1D18A9856A87 last_name: Hahn - first_name: Christopher J full_name: Wojtan, Christopher J id: 3C61F1D2-F248-11E8-B48F-1D18A9856A87 last_name: Wojtan orcid: 0000-0001-6646-5546 citation: ama: 'Hahn D, Wojtan C. High-resolution brittle fracture simulation with boundary elements. In: Vol 34. ACM; 2015. doi:10.1145/2766896' apa: 'Hahn, D., & Wojtan, C. (2015). High-resolution brittle fracture simulation with boundary elements (Vol. 34). Presented at the SIGGRAPH: Special Interest Group on Computer Graphics and Interactive Techniques, Los Angeles, CA, United States: ACM. https://doi.org/10.1145/2766896' chicago: Hahn, David, and Chris Wojtan. “High-Resolution Brittle Fracture Simulation with Boundary Elements,” Vol. 34. ACM, 2015. https://doi.org/10.1145/2766896. ieee: 'D. Hahn and C. Wojtan, “High-resolution brittle fracture simulation with boundary elements,” presented at the SIGGRAPH: Special Interest Group on Computer Graphics and Interactive Techniques, Los Angeles, CA, United States, 2015, vol. 34, no. 4.' ista: 'Hahn D, Wojtan C. 2015. High-resolution brittle fracture simulation with boundary elements. SIGGRAPH: Special Interest Group on Computer Graphics and Interactive Techniques vol. 34, 151.' mla: Hahn, David, and Chris Wojtan. High-Resolution Brittle Fracture Simulation with Boundary Elements. Vol. 34, no. 4, 151, ACM, 2015, doi:10.1145/2766896. short: D. Hahn, C. Wojtan, in:, ACM, 2015. conference: end_date: 2015-08-13 location: Los Angeles, CA, United States name: 'SIGGRAPH: Special Interest Group on Computer Graphics and Interactive Techniques' start_date: 2015-08-09 date_created: 2018-12-11T11:53:09Z date_published: 2015-07-27T00:00:00Z date_updated: 2023-09-07T12:02:56Z day: '27' ddc: - '000' department: - _id: ChWo doi: 10.1145/2766896 ec_funded: 1 file: - access_level: open_access checksum: 955aee971983f6b6152bcc1c9b4a7c20 content_type: application/pdf creator: system date_created: 2018-12-12T10:15:13Z date_updated: 2020-07-14T12:45:07Z file_id: '5131' file_name: IST-2016-609-v1+1_FractureBEM.pdf file_size: 20154270 relation: main_file file_date_updated: 2020-07-14T12:45:07Z has_accepted_license: '1' intvolume: ' 34' issue: '4' language: - iso: eng month: '07' oa: 1 oa_version: Submitted Version project: - _id: 2533E772-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '638176' name: Efficient Simulation of Natural Phenomena at Extremely Large Scales publication_status: published publisher: ACM publist_id: '5522' pubrep_id: '609' quality_controlled: '1' related_material: record: - id: '839' relation: dissertation_contains status: public scopus_import: 1 status: public title: High-resolution brittle fracture simulation with boundary elements type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 34 year: '2015' ... --- _id: '1537' abstract: - lang: eng text: 3D amoeboid cell migration is central to many developmental and disease-related processes such as cancer metastasis. Here, we identify a unique prototypic amoeboid cell migration mode in early zebrafish embryos, termed stable-bleb migration. Stable-bleb cells display an invariant polarized balloon-like shape with exceptional migration speed and persistence. Progenitor cells can be reversibly transformed into stable-bleb cells irrespective of their primary fate and motile characteristics by increasing myosin II activity through biochemical or mechanical stimuli. Using a combination of theory and experiments, we show that, in stable-bleb cells, cortical contractility fluctuations trigger a stochastic switch into amoeboid motility, and a positive feedback between cortical flows and gradients in contractility maintains stable-bleb cell polarization. We further show that rearward cortical flows drive stable-bleb cell migration in various adhesive and non-adhesive environments, unraveling a highly versatile amoeboid migration phenotype. acknowledged_ssus: - _id: SSU acknowledgement: 'We would like to thank R. Hausschild and E. Papusheva for technical assistance and the service facilities at the IST Austria for continuous support. The caRhoA plasmid was a kind gift of T. Kudoh and A. Takesono. We thank M. Piel and E. Paluch for exchanging unpublished data. ' author: - first_name: Verena full_name: Ruprecht, Verena id: 4D71A03A-F248-11E8-B48F-1D18A9856A87 last_name: Ruprecht orcid: 0000-0003-4088-8633 - first_name: Stefan full_name: Wieser, Stefan id: 355AA5A0-F248-11E8-B48F-1D18A9856A87 last_name: Wieser orcid: 0000-0002-2670-2217 - first_name: Andrew full_name: Callan Jones, Andrew last_name: Callan Jones - first_name: Michael full_name: Smutny, Michael id: 3FE6E4E8-F248-11E8-B48F-1D18A9856A87 last_name: Smutny orcid: 0000-0002-5920-9090 - first_name: Hitoshi full_name: Morita, Hitoshi id: 4C6E54C6-F248-11E8-B48F-1D18A9856A87 last_name: Morita - first_name: Keisuke full_name: Sako, Keisuke id: 3BED66BE-F248-11E8-B48F-1D18A9856A87 last_name: Sako orcid: 0000-0002-6453-8075 - first_name: Vanessa full_name: Barone, Vanessa id: 419EECCC-F248-11E8-B48F-1D18A9856A87 last_name: Barone orcid: 0000-0003-2676-3367 - first_name: Monika full_name: Ritsch Marte, Monika last_name: Ritsch Marte - first_name: Michael K full_name: Sixt, Michael K id: 41E9FBEA-F248-11E8-B48F-1D18A9856A87 last_name: Sixt orcid: 0000-0002-6620-9179 - first_name: Raphaël full_name: Voituriez, Raphaël last_name: Voituriez - first_name: Carl-Philipp J full_name: Heisenberg, Carl-Philipp J id: 39427864-F248-11E8-B48F-1D18A9856A87 last_name: Heisenberg orcid: 0000-0002-0912-4566 citation: ama: Ruprecht V, Wieser S, Callan Jones A, et al. Cortical contractility triggers a stochastic switch to fast amoeboid cell motility. Cell. 2015;160(4):673-685. doi:10.1016/j.cell.2015.01.008 apa: Ruprecht, V., Wieser, S., Callan Jones, A., Smutny, M., Morita, H., Sako, K., … Heisenberg, C.-P. J. (2015). Cortical contractility triggers a stochastic switch to fast amoeboid cell motility. Cell. Cell Press. https://doi.org/10.1016/j.cell.2015.01.008 chicago: Ruprecht, Verena, Stefan Wieser, Andrew Callan Jones, Michael Smutny, Hitoshi Morita, Keisuke Sako, Vanessa Barone, et al. “Cortical Contractility Triggers a Stochastic Switch to Fast Amoeboid Cell Motility.” Cell. Cell Press, 2015. https://doi.org/10.1016/j.cell.2015.01.008. ieee: V. Ruprecht et al., “Cortical contractility triggers a stochastic switch to fast amoeboid cell motility,” Cell, vol. 160, no. 4. Cell Press, pp. 673–685, 2015. ista: Ruprecht V, Wieser S, Callan Jones A, Smutny M, Morita H, Sako K, Barone V, Ritsch Marte M, Sixt MK, Voituriez R, Heisenberg C-PJ. 2015. Cortical contractility triggers a stochastic switch to fast amoeboid cell motility. Cell. 160(4), 673–685. mla: Ruprecht, Verena, et al. “Cortical Contractility Triggers a Stochastic Switch to Fast Amoeboid Cell Motility.” Cell, vol. 160, no. 4, Cell Press, 2015, pp. 673–85, doi:10.1016/j.cell.2015.01.008. short: V. Ruprecht, S. Wieser, A. Callan Jones, M. Smutny, H. Morita, K. Sako, V. Barone, M. Ritsch Marte, M.K. Sixt, R. Voituriez, C.-P.J. Heisenberg, Cell 160 (2015) 673–685. date_created: 2018-12-11T11:52:35Z date_published: 2015-02-12T00:00:00Z date_updated: 2023-09-07T12:05:08Z day: '12' ddc: - '570' department: - _id: CaHe - _id: MiSi doi: 10.1016/j.cell.2015.01.008 file: - access_level: open_access checksum: 228d3edf40627d897b3875088a0ac51f content_type: application/pdf creator: system date_created: 2018-12-12T10:13:21Z date_updated: 2020-07-14T12:45:01Z file_id: '5003' file_name: IST-2016-484-v1+1_1-s2.0-S0092867415000094-main.pdf file_size: 4362653 relation: main_file file_date_updated: 2020-07-14T12:45:01Z has_accepted_license: '1' intvolume: ' 160' issue: '4' language: - iso: eng month: '02' oa: 1 oa_version: Published Version page: 673 - 685 project: - _id: 2529486C-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: T 560-B17 name: Cell- and Tissue Mechanics in Zebrafish Germ Layer Formation - _id: 2527D5CC-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: I 812-B12 name: Cell Cortex and Germ Layer Formation in Zebrafish Gastrulation publication: Cell publication_status: published publisher: Cell Press publist_id: '5634' pubrep_id: '484' quality_controlled: '1' related_material: record: - id: '961' relation: dissertation_contains status: public scopus_import: 1 status: public title: Cortical contractility triggers a stochastic switch to fast amoeboid cell motility tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: journal_article user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87 volume: 160 year: '2015' ... --- _id: '1591' abstract: - lang: eng text: Auxin participates in a multitude of developmental processes, as well as responses to environmental cues. Compared with other plant hormones, auxin exhibits a unique property, as it undergoes directional, cell-to-cell transport facilitated by plasma membrane-localized transport proteins. Among them, a prominent role has been ascribed to the PIN family of auxin efflux facilitators. PIN proteins direct polar auxin transport on account of their asymmetric subcellular localizations. In this review, we provide an overview of the multiple developmental roles of PIN proteins, including the atypical endoplasmic reticulum-localized members of the family, and look at the family from an evolutionary perspective. Next, we cover the cell biological and molecular aspects of PIN function, in particular the establishment of their polar subcellular localization. Hormonal and environmental inputs into the regulation of PIN action are summarized as well. author: - first_name: Maciek full_name: Adamowski, Maciek id: 45F536D2-F248-11E8-B48F-1D18A9856A87 last_name: Adamowski orcid: 0000-0001-6463-5257 - first_name: Jirí full_name: Friml, Jirí id: 4159519E-F248-11E8-B48F-1D18A9856A87 last_name: Friml orcid: 0000-0002-8302-7596 citation: ama: 'Adamowski M, Friml J. PIN-dependent auxin transport: Action, regulation, and evolution. Plant Cell. 2015;27(1):20-32. doi:10.1105/tpc.114.134874' apa: 'Adamowski, M., & Friml, J. (2015). PIN-dependent auxin transport: Action, regulation, and evolution. Plant Cell. American Society of Plant Biologists. https://doi.org/10.1105/tpc.114.134874' chicago: 'Adamowski, Maciek, and Jiří Friml. “PIN-Dependent Auxin Transport: Action, Regulation, and Evolution.” Plant Cell. American Society of Plant Biologists, 2015. https://doi.org/10.1105/tpc.114.134874.' ieee: 'M. Adamowski and J. Friml, “PIN-dependent auxin transport: Action, regulation, and evolution,” Plant Cell, vol. 27, no. 1. American Society of Plant Biologists, pp. 20–32, 2015.' ista: 'Adamowski M, Friml J. 2015. PIN-dependent auxin transport: Action, regulation, and evolution. Plant Cell. 27(1), 20–32.' mla: 'Adamowski, Maciek, and Jiří Friml. “PIN-Dependent Auxin Transport: Action, Regulation, and Evolution.” Plant Cell, vol. 27, no. 1, American Society of Plant Biologists, 2015, pp. 20–32, doi:10.1105/tpc.114.134874.' short: M. Adamowski, J. Friml, Plant Cell 27 (2015) 20–32. date_created: 2018-12-11T11:52:54Z date_published: 2015-01-20T00:00:00Z date_updated: 2023-09-07T12:06:09Z day: '20' department: - _id: JiFr doi: 10.1105/tpc.114.134874 external_id: pmid: - '25604445' intvolume: ' 27' issue: '1' language: - iso: eng main_file_link: - open_access: '1' url: http://www.ncbi.nlm.nih.gov/pmc/articles/PMC4330589/ month: '01' oa: 1 oa_version: Submitted Version page: 20 - 32 pmid: 1 publication: Plant Cell publication_status: published publisher: American Society of Plant Biologists publist_id: '5580' quality_controlled: '1' related_material: record: - id: '938' relation: dissertation_contains status: public scopus_import: 1 status: public title: 'PIN-dependent auxin transport: Action, regulation, and evolution' type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 27 year: '2015' ... --- _id: '1677' abstract: - lang: eng text: We consider real symmetric and complex Hermitian random matrices with the additional symmetry hxy = hN-y,N-x. The matrix elements are independent (up to the fourfold symmetry) and not necessarily identically distributed. This ensemble naturally arises as the Fourier transform of a Gaussian orthogonal ensemble. Italso occurs as the flip matrix model - an approximation of the two-dimensional Anderson model at small disorder. We show that the density of states converges to the Wigner semicircle law despite the new symmetry type. We also prove the local version of the semicircle law on the optimal scale. article_number: '103301' author: - first_name: Johannes full_name: Alt, Johannes id: 36D3D8B6-F248-11E8-B48F-1D18A9856A87 last_name: Alt citation: ama: Alt J. The local semicircle law for random matrices with a fourfold symmetry. Journal of Mathematical Physics. 2015;56(10). doi:10.1063/1.4932606 apa: Alt, J. (2015). The local semicircle law for random matrices with a fourfold symmetry. Journal of Mathematical Physics. American Institute of Physics. https://doi.org/10.1063/1.4932606 chicago: Alt, Johannes. “The Local Semicircle Law for Random Matrices with a Fourfold Symmetry.” Journal of Mathematical Physics. American Institute of Physics, 2015. https://doi.org/10.1063/1.4932606. ieee: J. Alt, “The local semicircle law for random matrices with a fourfold symmetry,” Journal of Mathematical Physics, vol. 56, no. 10. American Institute of Physics, 2015. ista: Alt J. 2015. The local semicircle law for random matrices with a fourfold symmetry. Journal of Mathematical Physics. 56(10), 103301. mla: Alt, Johannes. “The Local Semicircle Law for Random Matrices with a Fourfold Symmetry.” Journal of Mathematical Physics, vol. 56, no. 10, 103301, American Institute of Physics, 2015, doi:10.1063/1.4932606. short: J. Alt, Journal of Mathematical Physics 56 (2015). date_created: 2018-12-11T11:53:25Z date_published: 2015-10-09T00:00:00Z date_updated: 2023-09-07T12:38:08Z day: '09' department: - _id: LaEr doi: 10.1063/1.4932606 ec_funded: 1 intvolume: ' 56' issue: '10' language: - iso: eng main_file_link: - open_access: '1' url: http://arxiv.org/abs/1506.04683 month: '10' oa: 1 oa_version: Preprint project: - _id: 258DCDE6-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '338804' name: Random matrices, universality and disordered quantum systems publication: Journal of Mathematical Physics publication_status: published publisher: American Institute of Physics publist_id: '5472' quality_controlled: '1' related_material: record: - id: '149' relation: dissertation_contains status: public scopus_import: 1 status: public title: The local semicircle law for random matrices with a fourfold symmetry type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 56 year: '2015' ... --- _id: '1678' abstract: - lang: eng text: High-throughput live-cell screens are intricate elements of systems biology studies and drug discovery pipelines. Here, we demonstrate an optogenetics-assisted method that avoids the need for chemical activators and reporters, reduces the number of operational steps and increases information content in a cell-based small-molecule screen against human protein kinases, including an orphan receptor tyrosine kinase. This blueprint for all-optical screening can be adapted to many drug targets and cellular processes. acknowledgement: 'This work was supported by grants from the European Union Seventh Framework Programme (CIG-303564 to H.J. and ERC-StG-311166 to S.M.B.N.), the Human Frontier Science Program (RGY0084_2012 to H.J.) and the Herzfelder Foundation (to M.G.). A.I.-P. was supported by a Ramon Areces fellowship, and E.R. by the graduate program MolecularDrugTargets (Austrian Science Fund (FWF): W 1232) and a FemTech fellowship (3580812 Austrian Research Promotion Agency).' author: - first_name: Álvaro full_name: Inglés Prieto, Álvaro id: 2A9DB292-F248-11E8-B48F-1D18A9856A87 last_name: Inglés Prieto orcid: 0000-0002-5409-8571 - first_name: Eva full_name: Gschaider-Reichhart, Eva id: 3FEE232A-F248-11E8-B48F-1D18A9856A87 last_name: Gschaider-Reichhart orcid: 0000-0002-7218-7738 - first_name: Markus full_name: Muellner, Markus last_name: Muellner - first_name: Matthias full_name: Nowak, Matthias id: 30845DAA-F248-11E8-B48F-1D18A9856A87 last_name: Nowak - first_name: Sebastian full_name: Nijman, Sebastian last_name: Nijman - first_name: Michael full_name: Grusch, Michael last_name: Grusch - first_name: Harald L full_name: Janovjak, Harald L id: 33BA6C30-F248-11E8-B48F-1D18A9856A87 last_name: Janovjak orcid: 0000-0002-8023-9315 citation: ama: Inglés Prieto Á, Gschaider-Reichhart E, Muellner M, et al. Light-assisted small-molecule screening against protein kinases. Nature Chemical Biology. 2015;11(12):952-954. doi:10.1038/nchembio.1933 apa: Inglés Prieto, Á., Gschaider-Reichhart, E., Muellner, M., Nowak, M., Nijman, S., Grusch, M., & Janovjak, H. L. (2015). Light-assisted small-molecule screening against protein kinases. Nature Chemical Biology. Nature Publishing Group. https://doi.org/10.1038/nchembio.1933 chicago: Inglés Prieto, Álvaro, Eva Gschaider-Reichhart, Markus Muellner, Matthias Nowak, Sebastian Nijman, Michael Grusch, and Harald L Janovjak. “Light-Assisted Small-Molecule Screening against Protein Kinases.” Nature Chemical Biology. Nature Publishing Group, 2015. https://doi.org/10.1038/nchembio.1933. ieee: Á. Inglés Prieto et al., “Light-assisted small-molecule screening against protein kinases,” Nature Chemical Biology, vol. 11, no. 12. Nature Publishing Group, pp. 952–954, 2015. ista: Inglés Prieto Á, Gschaider-Reichhart E, Muellner M, Nowak M, Nijman S, Grusch M, Janovjak HL. 2015. Light-assisted small-molecule screening against protein kinases. Nature Chemical Biology. 11(12), 952–954. mla: Inglés Prieto, Álvaro, et al. “Light-Assisted Small-Molecule Screening against Protein Kinases.” Nature Chemical Biology, vol. 11, no. 12, Nature Publishing Group, 2015, pp. 952–54, doi:10.1038/nchembio.1933. short: Á. Inglés Prieto, E. Gschaider-Reichhart, M. Muellner, M. Nowak, S. Nijman, M. Grusch, H.L. Janovjak, Nature Chemical Biology 11 (2015) 952–954. date_created: 2018-12-11T11:53:25Z date_published: 2015-10-12T00:00:00Z date_updated: 2023-09-07T12:49:09Z day: '12' ddc: - '571' department: - _id: HaJa - _id: LifeSc doi: 10.1038/nchembio.1933 ec_funded: 1 file: - access_level: open_access checksum: e9fb251dfcb7cd209b83f17867e61321 content_type: application/pdf creator: system date_created: 2018-12-12T10:10:51Z date_updated: 2020-07-14T12:45:12Z file_id: '4842' file_name: IST-2017-837-v1+1_ingles-prieto.pdf file_size: 1308364 relation: main_file file_date_updated: 2020-07-14T12:45:12Z has_accepted_license: '1' intvolume: ' 11' issue: '12' language: - iso: eng month: '10' oa: 1 oa_version: Submitted Version page: 952 - 954 project: - _id: 25548C20-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '303564' name: Microbial Ion Channels for Synthetic Neurobiology - _id: 255BFFFA-B435-11E9-9278-68D0E5697425 grant_number: RGY0084/2012 name: In situ real-time imaging of neurotransmitter signaling using designer optical sensors (HFSP Young Investigator) - _id: 255A6082-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: W1232-B24 name: Molecular Drug Targets publication: Nature Chemical Biology publication_status: published publisher: Nature Publishing Group publist_id: '5471' pubrep_id: '837' quality_controlled: '1' related_material: record: - id: '418' relation: dissertation_contains status: public scopus_import: 1 status: public title: Light-assisted small-molecule screening against protein kinases type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 11 year: '2015' ... --- _id: '1576' abstract: - lang: eng text: 'Gene expression is controlled primarily by interactions between transcription factor proteins (TFs) and the regulatory DNA sequence, a process that can be captured well by thermodynamic models of regulation. These models, however, neglect regulatory crosstalk: the possibility that noncognate TFs could initiate transcription, with potentially disastrous effects for the cell. Here, we estimate the importance of crosstalk, suggest that its avoidance strongly constrains equilibrium models of TF binding, and propose an alternative nonequilibrium scheme that implements kinetic proofreading to suppress erroneous initiation. This proposal is consistent with the observed covalent modifications of the transcriptional apparatus and predicts increased noise in gene expression as a trade-off for improved specificity. Using information theory, we quantify this trade-off to find when optimal proofreading architectures are favored over their equilibrium counterparts. Such architectures exhibit significant super-Poisson noise at low expression in steady state.' article_number: '248101' author: - first_name: Sarah A full_name: Cepeda Humerez, Sarah A id: 3DEE19A4-F248-11E8-B48F-1D18A9856A87 last_name: Cepeda Humerez - first_name: Georg full_name: Rieckh, Georg id: 34DA8BD6-F248-11E8-B48F-1D18A9856A87 last_name: Rieckh - first_name: Gasper full_name: Tkacik, Gasper id: 3D494DCA-F248-11E8-B48F-1D18A9856A87 last_name: Tkacik orcid: 0000-0002-6699-1455 citation: ama: Cepeda Humerez SA, Rieckh G, Tkačik G. Stochastic proofreading mechanism alleviates crosstalk in transcriptional regulation. Physical Review Letters. 2015;115(24). doi:10.1103/PhysRevLett.115.248101 apa: Cepeda Humerez, S. A., Rieckh, G., & Tkačik, G. (2015). Stochastic proofreading mechanism alleviates crosstalk in transcriptional regulation. Physical Review Letters. American Physical Society. https://doi.org/10.1103/PhysRevLett.115.248101 chicago: Cepeda Humerez, Sarah A, Georg Rieckh, and Gašper Tkačik. “Stochastic Proofreading Mechanism Alleviates Crosstalk in Transcriptional Regulation.” Physical Review Letters. American Physical Society, 2015. https://doi.org/10.1103/PhysRevLett.115.248101. ieee: S. A. Cepeda Humerez, G. Rieckh, and G. Tkačik, “Stochastic proofreading mechanism alleviates crosstalk in transcriptional regulation,” Physical Review Letters, vol. 115, no. 24. American Physical Society, 2015. ista: Cepeda Humerez SA, Rieckh G, Tkačik G. 2015. Stochastic proofreading mechanism alleviates crosstalk in transcriptional regulation. Physical Review Letters. 115(24), 248101. mla: Cepeda Humerez, Sarah A., et al. “Stochastic Proofreading Mechanism Alleviates Crosstalk in Transcriptional Regulation.” Physical Review Letters, vol. 115, no. 24, 248101, American Physical Society, 2015, doi:10.1103/PhysRevLett.115.248101. short: S.A. Cepeda Humerez, G. Rieckh, G. Tkačik, Physical Review Letters 115 (2015). date_created: 2018-12-11T11:52:49Z date_published: 2015-12-08T00:00:00Z date_updated: 2023-09-07T12:55:21Z day: '08' department: - _id: GaTk doi: 10.1103/PhysRevLett.115.248101 ec_funded: 1 intvolume: ' 115' issue: '24' language: - iso: eng main_file_link: - open_access: '1' url: http://arxiv.org/abs/1504.05716 month: '12' oa: 1 oa_version: Preprint project: - _id: 25B07788-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '250152' name: Limits to selection in biology and in evolutionary computation publication: Physical Review Letters publication_status: published publisher: American Physical Society publist_id: '5595' quality_controlled: '1' related_material: record: - id: '6473' relation: part_of_dissertation status: public scopus_import: 1 status: public title: Stochastic proofreading mechanism alleviates crosstalk in transcriptional regulation type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 115 year: '2015' ... --- _id: '8183' abstract: - lang: eng text: "We study conditions under which a finite simplicial complex $K$ can be mapped to $\\mathbb R^d$ without higher-multiplicity intersections. An almost $r$-embedding is a map $f: K\\to \\mathbb R^d$ such that the images of any $r$\r\npairwise disjoint simplices of $K$ do not have a common point. We show that if $r$ is not a prime power and $d\\geq 2r+1$, then there is a counterexample to the topological Tverberg conjecture, i.e., there is an almost $r$-embedding of\r\nthe $(d+1)(r-1)$-simplex in $\\mathbb R^d$. This improves on previous constructions of counterexamples (for $d\\geq 3r$) based on a series of papers by M. \\\"Ozaydin, M. Gromov, P. Blagojevi\\'c, F. Frick, G. Ziegler, and the second and fourth present authors. The counterexamples are obtained by proving the following algebraic criterion in codimension 2: If $r\\ge3$ and if $K$ is a finite $2(r-1)$-complex then there exists an almost $r$-embedding $K\\to \\mathbb R^{2r}$ if and only if there exists a general position PL map $f:K\\to \\mathbb R^{2r}$ such that the algebraic intersection number of the $f$-images of any $r$ pairwise disjoint simplices of $K$ is zero. This result can be restated in terms of cohomological obstructions or equivariant maps, and extends an analogous codimension 3 criterion by the second and fourth authors. As another application we classify ornaments $f:S^3 \\sqcup S^3\\sqcup S^3\\to \\mathbb R^5$ up to ornament\r\nconcordance. It follows from work of M. Freedman, V. Krushkal and P. Teichner that the analogous criterion for $r=2$ is false. We prove a lemma on singular higher-dimensional Borromean rings, yielding an elementary proof of the counterexample." acknowledgement: We would like to thank A. Klyachko, V. Krushkal, S. Melikhov, M. Tancer, P. Teichner and anonymous referees for helpful discussions. article_number: '1511.03501' article_processing_charge: No author: - first_name: Sergey full_name: Avvakumov, Sergey id: 3827DAC8-F248-11E8-B48F-1D18A9856A87 last_name: Avvakumov - first_name: Isaac full_name: Mabillard, Isaac id: 32BF9DAA-F248-11E8-B48F-1D18A9856A87 last_name: Mabillard - first_name: A. full_name: Skopenkov, A. last_name: Skopenkov - first_name: Uli full_name: Wagner, Uli id: 36690CA2-F248-11E8-B48F-1D18A9856A87 last_name: Wagner orcid: 0000-0002-1494-0568 citation: ama: Avvakumov S, Mabillard I, Skopenkov A, Wagner U. Eliminating higher-multiplicity intersections, III. Codimension 2. arXiv. apa: Avvakumov, S., Mabillard, I., Skopenkov, A., & Wagner, U. (n.d.). Eliminating higher-multiplicity intersections, III. Codimension 2. arXiv. chicago: Avvakumov, Sergey, Isaac Mabillard, A. Skopenkov, and Uli Wagner. “Eliminating Higher-Multiplicity Intersections, III. Codimension 2.” ArXiv, n.d. ieee: S. Avvakumov, I. Mabillard, A. Skopenkov, and U. Wagner, “Eliminating higher-multiplicity intersections, III. Codimension 2,” arXiv. . ista: Avvakumov S, Mabillard I, Skopenkov A, Wagner U. Eliminating higher-multiplicity intersections, III. Codimension 2. arXiv, 1511.03501. mla: Avvakumov, Sergey, et al. “Eliminating Higher-Multiplicity Intersections, III. Codimension 2.” ArXiv, 1511.03501. short: S. Avvakumov, I. Mabillard, A. Skopenkov, U. Wagner, ArXiv (n.d.). date_created: 2020-07-30T10:45:19Z date_published: 2015-11-15T00:00:00Z date_updated: 2023-09-07T13:12:17Z day: '15' department: - _id: UlWa external_id: arxiv: - '1511.03501' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1511.03501 month: '11' oa: 1 oa_version: Preprint publication: arXiv publication_status: submitted related_material: record: - id: '9308' relation: later_version status: public - id: '10220' relation: later_version status: public - id: '8156' relation: dissertation_contains status: public status: public title: Eliminating higher-multiplicity intersections, III. Codimension 2 type: preprint user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2015' ... --- _id: '5441' abstract: - lang: eng text: We study algorithmic questions for concurrent systems where the transitions are labeled from a complete, closed semiring, and path properties are algebraic with semiring operations. The algebraic path properties can model dataflow analysis problems, the shortest path problem, and many other natural problems that arise in program analysis. We consider that each component of the concurrent system is a graph with constant treewidth, a property satisfied by the controlflow graphs of most programs. We allow for multiple possible queries, which arise naturally in demand driven dataflow analysis. The study of multiple queries allows us to consider the tradeoff between the resource usage of the one-time preprocessing and for each individual query. The traditional approach constructs the product graph of all components and applies the best-known graph algorithm on the product. In this approach, even the answer to a single query requires the transitive closure (i.e., the results of all possible queries), which provides no room for tradeoff between preprocessing and query time. Our main contributions are algorithms that significantly improve the worst-case running time of the traditional approach, and provide various tradeoffs depending on the number of queries. For example, in a concurrent system of two components, the traditional approach requires hexic time in the worst case for answering one query as well as computing the transitive closure, whereas we show that with one-time preprocessing in almost cubic time, each subsequent query can be answered in at most linear time, and even the transitive closure can be computed in almost quartic time. Furthermore, we establish conditional optimality results showing that the worst-case running time of our algorithms cannot be improved without achieving major breakthroughs in graph algorithms (i.e., improving the worst-case bound for the shortest path problem in general graphs). Preliminary experimental results show that our algorithms perform favorably on several benchmarks. alternative_title: - IST Austria Technical Report author: - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Rasmus full_name: Ibsen-Jensen, Rasmus id: 3B699956-F248-11E8-B48F-1D18A9856A87 last_name: Ibsen-Jensen orcid: 0000-0003-4783-0389 - first_name: Amir full_name: Goharshady, Amir id: 391365CE-F248-11E8-B48F-1D18A9856A87 last_name: Goharshady orcid: 0000-0003-1702-6584 - first_name: Andreas full_name: Pavlogiannis, Andreas id: 49704004-F248-11E8-B48F-1D18A9856A87 last_name: Pavlogiannis orcid: 0000-0002-8943-0722 citation: ama: Chatterjee K, Ibsen-Jensen R, Goharshady AK, Pavlogiannis A. Algorithms for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components. IST Austria; 2015. doi:10.15479/AT:IST-2015-340-v1-1 apa: Chatterjee, K., Ibsen-Jensen, R., Goharshady, A. K., & Pavlogiannis, A. (2015). Algorithms for algebraic path properties in concurrent systems of constant treewidth components. IST Austria. https://doi.org/10.15479/AT:IST-2015-340-v1-1 chicago: Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, Amir Kafshdar Goharshady, and Andreas Pavlogiannis. Algorithms for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components. IST Austria, 2015. https://doi.org/10.15479/AT:IST-2015-340-v1-1. ieee: K. Chatterjee, R. Ibsen-Jensen, A. K. Goharshady, and A. Pavlogiannis, Algorithms for algebraic path properties in concurrent systems of constant treewidth components. IST Austria, 2015. ista: Chatterjee K, Ibsen-Jensen R, Goharshady AK, Pavlogiannis A. 2015. Algorithms for algebraic path properties in concurrent systems of constant treewidth components, IST Austria, 24p. mla: Chatterjee, Krishnendu, et al. Algorithms for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components. IST Austria, 2015, doi:10.15479/AT:IST-2015-340-v1-1. short: K. Chatterjee, R. Ibsen-Jensen, A.K. Goharshady, A. Pavlogiannis, Algorithms for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components, IST Austria, 2015. date_created: 2018-12-12T11:39:21Z date_published: 2015-07-11T00:00:00Z date_updated: 2023-09-19T14:36:19Z day: '11' ddc: - '000' department: - _id: KrCh doi: 10.15479/AT:IST-2015-340-v1-1 file: - access_level: open_access checksum: df383dc62c94d7b2ea639aba088a76c6 content_type: application/pdf creator: system date_created: 2018-12-12T11:54:09Z date_updated: 2020-07-14T12:46:56Z file_id: '5531' file_name: IST-2015-340-v1+1_main.pdf file_size: 861396 relation: main_file file_date_updated: 2020-07-14T12:46:56Z has_accepted_license: '1' language: - iso: eng month: '07' oa: 1 oa_version: Published Version page: '24' publication_identifier: issn: - 2664-1690 publication_status: published publisher: IST Austria pubrep_id: '340' related_material: record: - id: '1437' relation: later_version status: public - id: '5442' relation: earlier_version status: public - id: '6009' relation: later_version status: public status: public title: Algorithms for algebraic path properties in concurrent systems of constant treewidth components type: technical_report user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2015' ...