[{"publication_identifier":{"issn":["2664-1690"]},"alternative_title":["IST Austria Technical Report"],"status":"public","date_created":"2018-12-12T11:39:19Z","month":"04","page":"27","pubrep_id":"333","date_published":"2015-04-27T00:00:00Z","file":[{"date_created":"2018-12-12T11:53:12Z","relation":"main_file","creator":"system","content_type":"application/pdf","file_size":1072137,"file_id":"5473","date_updated":"2020-07-14T12:46:54Z","access_level":"open_access","file_name":"IST-2015-330-v2+1_main.pdf","checksum":"f5917c20f84018b362d385c000a2e123"}],"publisher":"IST Austria","file_date_updated":"2020-07-14T12:46:54Z","related_material":{"record":[{"id":"1607","relation":"later_version","status":"public"},{"id":"5430","status":"public","relation":"earlier_version"}]},"language":[{"iso":"eng"}],"doi":"10.15479/AT:IST-2015-330-v2-1","oa":1,"ddc":["000"],"_id":"5437","department":[{"_id":"KrCh"}],"has_accepted_license":"1","title":"Faster algorithms for quantitative verification in constant treewidth graphs","publication_status":"published","abstract":[{"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. \r\nThe 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.\r\nOur main theoretical results are as follows.\r\nFirst, for constant treewidth graphs we present an algorithm that approximates the mean-payoff value within a multiplicative factor of $\\epsilon$ in time $O(n \\cdot \\log (n/\\epsilon))$ 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 \\cdot \\log (|a\\cdot b|))=O(n\\cdot\\log (n\\cdot W))$, when the output is $\\frac{a}{b}$, as compared to the previously best known algorithm with running time $O(n^2 \\cdot \\log (n\\cdot W))$. Third, for the minimum initial credit problem we show that (i)~for general graphs the problem can be solved in $O(n^2\\cdot m)$ time and the associated decision problem can be solved in $O(n\\cdot m)$ time, improving the previous known $O(n^3\\cdot m\\cdot \\log (n\\cdot W))$ and $O(n^2 \\cdot m)$ bounds, respectively; and (ii)~for constant treewidth graphs we present an algorithm that requires $O(n\\cdot \\log n)$ time, improving the previous known $O(n^4 \\cdot \\log (n \\cdot W))$ bound.\r\nWe have implemented some of our algorithms and show that they present a significant speedup on standard benchmarks. ","lang":"eng"}],"author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","last_name":"Chatterjee"},{"full_name":"Ibsen-Jensen, Rasmus","orcid":"0000-0003-4783-0389","id":"3B699956-F248-11E8-B48F-1D18A9856A87","first_name":"Rasmus","last_name":"Ibsen-Jensen"},{"last_name":"Pavlogiannis","first_name":"Andreas","orcid":"0000-0002-8943-0722","full_name":"Pavlogiannis, Andreas","id":"49704004-F248-11E8-B48F-1D18A9856A87"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"mla":"Chatterjee, Krishnendu, et al. <i>Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs</i>. IST Austria, 2015, doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-330-v2-1\">10.15479/AT:IST-2015-330-v2-1</a>.","apa":"Chatterjee, K., Ibsen-Jensen, R., &#38; Pavlogiannis, A. (2015). <i>Faster algorithms for quantitative verification in constant treewidth graphs</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2015-330-v2-1\">https://doi.org/10.15479/AT:IST-2015-330-v2-1</a>","ista":"Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. 2015. Faster algorithms for quantitative verification in constant treewidth graphs, IST Austria, 27p.","chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Andreas Pavlogiannis. <i>Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs</i>. IST Austria, 2015. <a href=\"https://doi.org/10.15479/AT:IST-2015-330-v2-1\">https://doi.org/10.15479/AT:IST-2015-330-v2-1</a>.","short":"K. Chatterjee, R. Ibsen-Jensen, A. Pavlogiannis, Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs, IST Austria, 2015.","ieee":"K. Chatterjee, R. Ibsen-Jensen, and A. Pavlogiannis, <i>Faster algorithms for quantitative verification in constant treewidth graphs</i>. IST Austria, 2015.","ama":"Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. <i>Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs</i>. IST Austria; 2015. doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-330-v2-1\">10.15479/AT:IST-2015-330-v2-1</a>"},"day":"27","year":"2015","type":"technical_report","date_updated":"2023-02-23T12:26:05Z","oa_version":"Published Version"},{"file_date_updated":"2020-07-14T12:46:55Z","publisher":"IST Austria","date_published":"2015-05-05T00:00:00Z","file":[{"relation":"main_file","date_created":"2018-12-12T11:53:56Z","creator":"system","content_type":"application/pdf","file_size":422573,"date_updated":"2020-07-14T12:46:55Z","file_id":"5518","file_name":"IST-2015-334-v1+1_report.pdf","checksum":"8a5f2d77560e552af87eb1982437a43b","access_level":"open_access"}],"page":"15","pubrep_id":"334","date_created":"2018-12-12T11:39:20Z","month":"05","status":"public","alternative_title":["IST Austria Technical Report"],"publication_identifier":{"issn":["2664-1690"]},"type":"technical_report","date_updated":"2023-02-23T12:20:08Z","oa_version":"Published Version","day":"05","year":"2015","citation":{"mla":"Chatterjee, Krishnendu, et al. <i>Edit Distance for Pushdown Automata</i>. IST Austria, 2015, doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-334-v1-1\">10.15479/AT:IST-2015-334-v1-1</a>.","apa":"Chatterjee, K., Henzinger, T. A., Ibsen-Jensen, R., &#38; Otop, J. (2015). <i>Edit distance for pushdown automata</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2015-334-v1-1\">https://doi.org/10.15479/AT:IST-2015-334-v1-1</a>","ama":"Chatterjee K, Henzinger TA, Ibsen-Jensen R, Otop J. <i>Edit Distance for Pushdown Automata</i>. IST Austria; 2015. doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-334-v1-1\">10.15479/AT:IST-2015-334-v1-1</a>","ieee":"K. Chatterjee, T. A. Henzinger, R. Ibsen-Jensen, and J. Otop, <i>Edit distance for pushdown automata</i>. IST Austria, 2015.","ista":"Chatterjee K, Henzinger TA, Ibsen-Jensen R, Otop J. 2015. Edit distance for pushdown automata, IST Austria, 15p.","short":"K. Chatterjee, T.A. Henzinger, R. Ibsen-Jensen, J. Otop, Edit Distance for Pushdown Automata, IST Austria, 2015.","chicago":"Chatterjee, Krishnendu, Thomas A Henzinger, Rasmus Ibsen-Jensen, and Jan Otop. <i>Edit Distance for Pushdown Automata</i>. IST Austria, 2015. <a href=\"https://doi.org/10.15479/AT:IST-2015-334-v1-1\">https://doi.org/10.15479/AT:IST-2015-334-v1-1</a>."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","last_name":"Chatterjee"},{"full_name":"Henzinger, Thomas A","orcid":"0000−0002−2985−7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","first_name":"Thomas A","last_name":"Henzinger"},{"last_name":"Ibsen-Jensen","first_name":"Rasmus","orcid":"0000-0003-4783-0389","full_name":"Ibsen-Jensen, Rasmus","id":"3B699956-F248-11E8-B48F-1D18A9856A87"},{"id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87","full_name":"Otop, Jan","last_name":"Otop","first_name":"Jan"}],"publication_status":"published","abstract":[{"text":"The edit distance between two words w1, w2 is the minimal number of word operations (letter insertions, deletions, and substitutions) necessary to transform w1 to w2. The edit distance generalizes to languages L1, L2, where the edit distance is the minimal number k such that for every word from L1 there exists a word in L2 with edit distance at most k. We study the edit distance computation problem between pushdown automata and their subclasses.\r\nThe problem of computing edit distance to a pushdown automaton is undecidable, and in practice, the interesting question is to compute the edit distance from a pushdown automaton (the implementation, a standard model for programs with recursion) to a regular language (the specification). In this work, we present a complete picture of decidability and complexity for deciding whether, for a given threshold k, the edit distance from a pushdown automaton to a finite automaton is at most k. ","lang":"eng"}],"title":"Edit distance for pushdown automata","doi":"10.15479/AT:IST-2015-334-v1-1","oa":1,"related_material":{"record":[{"relation":"later_version","status":"public","id":"1610"},{"id":"465","status":"public","relation":"later_version"}]},"language":[{"iso":"eng"}],"ddc":["004"],"_id":"5438","has_accepted_license":"1","department":[{"_id":"KrCh"}]},{"title":"The target discounted-sum problem","has_accepted_license":"1","_id":"5439","department":[{"_id":"ToHe"}],"doi":"10.15479/AT:IST-2015-335-v1-1","related_material":{"record":[{"status":"public","relation":"later_version","id":"1659"}]},"oa":1,"language":[{"iso":"eng"}],"ddc":["004","512","513"],"abstract":[{"text":"The target discounted-sum problem is the following: Given a rational discount factor 0 < λ < 1 and three rational values a, b, and t, does there exist a finite or an infinite sequence w ε(a, b)∗ or w ε(a, b)w, such that Σ|w| i=0 w(i)λi equals t? The problem turns out to relate to many fields of mathematics and computer science, and its decidability question is surprisingly hard to solve. We solve the finite version of the problem, and show the hardness of the infinite version, linking it to various areas and open problems in mathematics and computer science: β-expansions, discounted-sum automata, piecewise affine maps, and generalizations of the Cantor set. We provide some partial results to the infinite version, among which are solutions to its restriction to eventually-periodic sequences and to the cases that λ λ 1/2 or λ = 1/n, for every n ε N. We use our results for solving some open problems on discounted-sum automata, among which are the exact-value problem for nondeterministic automata over finite words and the universality and inclusion problems for functional automata. ","lang":"eng"}],"publication_status":"published","citation":{"mla":"Boker, Udi, et al. <i>The Target Discounted-Sum Problem</i>. IST Austria, 2015, doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-335-v1-1\">10.15479/AT:IST-2015-335-v1-1</a>.","apa":"Boker, U., Henzinger, T. A., &#38; Otop, J. (2015). <i>The target discounted-sum problem</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2015-335-v1-1\">https://doi.org/10.15479/AT:IST-2015-335-v1-1</a>","ama":"Boker U, Henzinger TA, Otop J. <i>The Target Discounted-Sum Problem</i>. IST Austria; 2015. doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-335-v1-1\">10.15479/AT:IST-2015-335-v1-1</a>","ieee":"U. Boker, T. A. Henzinger, and J. Otop, <i>The target discounted-sum problem</i>. IST Austria, 2015.","ista":"Boker U, Henzinger TA, Otop J. 2015. The target discounted-sum problem, IST Austria, 20p.","short":"U. Boker, T.A. Henzinger, J. Otop, The Target Discounted-Sum Problem, IST Austria, 2015.","chicago":"Boker, Udi, Thomas A Henzinger, and Jan Otop. <i>The Target Discounted-Sum Problem</i>. IST Austria, 2015. <a href=\"https://doi.org/10.15479/AT:IST-2015-335-v1-1\">https://doi.org/10.15479/AT:IST-2015-335-v1-1</a>."},"author":[{"first_name":"Udi","last_name":"Boker","id":"31E297B6-F248-11E8-B48F-1D18A9856A87","full_name":"Boker, Udi"},{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A","last_name":"Henzinger","first_name":"Thomas A"},{"full_name":"Otop, Jan","id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87","first_name":"Jan","last_name":"Otop"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Published Version","type":"technical_report","date_updated":"2023-02-23T10:08:48Z","year":"2015","day":"18","alternative_title":["IST Austria Technical Report"],"publication_identifier":{"issn":["2664-1690"]},"month":"05","date_created":"2018-12-12T11:39:20Z","status":"public","file":[{"access_level":"open_access","checksum":"40405907aa012acece1bc26cf0be554d","file_name":"IST-2015-335-v1+1_report.pdf","file_id":"5517","date_updated":"2020-07-14T12:46:55Z","creator":"system","content_type":"application/pdf","file_size":589619,"date_created":"2018-12-12T11:53:55Z","relation":"main_file"}],"date_published":"2015-05-18T00:00:00Z","pubrep_id":"335","page":"20","file_date_updated":"2020-07-14T12:46:55Z","publisher":"IST Austria"},{"title":"The complexity of evolutionary games on graphs","oa":1,"related_material":{"record":[{"id":"5421","relation":"earlier_version","status":"public"},{"id":"5432","status":"public","relation":"earlier_version"}]},"ddc":["005","576"],"doi":"10.15479/AT:IST-2015-323-v2-2","language":[{"iso":"eng"}],"department":[{"_id":"KrCh"}],"_id":"5440","has_accepted_license":"1","publication_status":"published","abstract":[{"text":"Evolution occurs in populations of reproducing individuals. The structure of the population affects the outcome of the evolutionary process. Evolutionary graph theory is a powerful approach to study this phenomenon. There are two graphs. The interaction graph specifies who interacts with whom for payoff in the context of evolution. The replacement graph specifies who competes with whom for reproduction. The vertices of the two graphs are the same, and each vertex corresponds to an individual of the population. The fitness (or the reproductive rate) is a non-negative number, and depends on the payoff. A key quantity is the fixation probability of a new mutant. It is defined as the probability that a newly introduced mutant (on a single vertex) generates a lineage of offspring which eventually takes over the entire population of resident individuals. The basic computational questions are as follows: (i) the qualitative question asks whether the fixation probability is positive; and (ii) the quantitative approximation question asks for an approximation of the fixation probability. Our main results are as follows: First, we consider a special case of the general problem, where the residents do not reproduce. We show that the qualitative question is NP-complete, and the quantitative approximation question is #P-complete, and the hardness results hold even in the special case where the interaction and the replacement graphs coincide. Second, we show that in general both the qualitative and the quantitative approximation questions are PSPACE-complete. The PSPACE-hardness result for quantitative approximation holds even when the fitness is always positive.","lang":"eng"}],"citation":{"mla":"Chatterjee, Krishnendu, et al. <i>The Complexity of Evolutionary Games on Graphs</i>. IST Austria, 2015, doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-323-v2-2\">10.15479/AT:IST-2015-323-v2-2</a>.","apa":"Chatterjee, K., Ibsen-Jensen, R., &#38; Nowak, M. (2015). <i>The complexity of evolutionary games on graphs</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2015-323-v2-2\">https://doi.org/10.15479/AT:IST-2015-323-v2-2</a>","ieee":"K. Chatterjee, R. Ibsen-Jensen, and M. Nowak, <i>The complexity of evolutionary games on graphs</i>. IST Austria, 2015.","ama":"Chatterjee K, Ibsen-Jensen R, Nowak M. <i>The Complexity of Evolutionary Games on Graphs</i>. IST Austria; 2015. doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-323-v2-2\">10.15479/AT:IST-2015-323-v2-2</a>","ista":"Chatterjee K, Ibsen-Jensen R, Nowak M. 2015. The complexity of evolutionary games on graphs, IST Austria, 18p.","chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Martin Nowak. <i>The Complexity of Evolutionary Games on Graphs</i>. IST Austria, 2015. <a href=\"https://doi.org/10.15479/AT:IST-2015-323-v2-2\">https://doi.org/10.15479/AT:IST-2015-323-v2-2</a>.","short":"K. Chatterjee, R. Ibsen-Jensen, M. Nowak, The Complexity of Evolutionary Games on Graphs, IST Austria, 2015."},"author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","first_name":"Krishnendu"},{"id":"3B699956-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-4783-0389","full_name":"Ibsen-Jensen, Rasmus","first_name":"Rasmus","last_name":"Ibsen-Jensen"},{"full_name":"Nowak, Martin","first_name":"Martin","last_name":"Nowak"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"technical_report","date_updated":"2023-02-23T12:26:10Z","oa_version":"Published Version","day":"16","year":"2015","alternative_title":["IST Austria Technical Report"],"publication_identifier":{"issn":["2664-1690"]},"date_created":"2018-12-12T11:39:21Z","month":"06","status":"public","date_published":"2015-06-16T00:00:00Z","file":[{"file_size":466161,"creator":"system","content_type":"application/pdf","relation":"main_file","date_created":"2018-12-12T11:53:23Z","checksum":"66aace7d367032af97c15e35c9be9636","file_name":"IST-2015-323-v2+2_main.pdf","access_level":"open_access","date_updated":"2020-07-14T12:46:56Z","file_id":"5484"}],"page":"18","pubrep_id":"338","file_date_updated":"2020-07-14T12:46:56Z","publisher":"IST Austria"},{"alternative_title":["IST Austria Technical Report"],"publication_identifier":{"issn":["2664-1690"]},"date_created":"2018-12-12T11:39:21Z","month":"07","status":"public","date_published":"2015-07-11T00:00:00Z","file":[{"file_size":861396,"content_type":"application/pdf","creator":"system","relation":"main_file","date_created":"2018-12-12T11:54:09Z","file_name":"IST-2015-340-v1+1_main.pdf","checksum":"df383dc62c94d7b2ea639aba088a76c6","access_level":"open_access","file_id":"5531","date_updated":"2020-07-14T12:46:56Z"}],"page":"24","pubrep_id":"340","file_date_updated":"2020-07-14T12:46:56Z","publisher":"IST Austria","title":"Algorithms for algebraic path properties in concurrent systems of constant treewidth components","ddc":["000"],"language":[{"iso":"eng"}],"oa":1,"doi":"10.15479/AT:IST-2015-340-v1-1","related_material":{"record":[{"status":"public","relation":"later_version","id":"1437"},{"id":"5442","status":"public","relation":"earlier_version"},{"id":"6009","status":"public","relation":"later_version"}]},"department":[{"_id":"KrCh"}],"_id":"5441","has_accepted_license":"1","publication_status":"published","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."}],"citation":{"mla":"Chatterjee, Krishnendu, et al. <i>Algorithms for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components</i>. IST Austria, 2015, doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-340-v1-1\">10.15479/AT:IST-2015-340-v1-1</a>.","apa":"Chatterjee, K., Ibsen-Jensen, R., Goharshady, A. K., &#38; Pavlogiannis, A. (2015). <i>Algorithms for algebraic path properties in concurrent systems of constant treewidth components</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2015-340-v1-1\">https://doi.org/10.15479/AT:IST-2015-340-v1-1</a>","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.","chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, Amir Kafshdar Goharshady, and Andreas Pavlogiannis. <i>Algorithms for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components</i>. IST Austria, 2015. <a href=\"https://doi.org/10.15479/AT:IST-2015-340-v1-1\">https://doi.org/10.15479/AT:IST-2015-340-v1-1</a>.","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.","ama":"Chatterjee K, Ibsen-Jensen R, Goharshady AK, Pavlogiannis A. <i>Algorithms for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components</i>. IST Austria; 2015. doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-340-v1-1\">10.15479/AT:IST-2015-340-v1-1</a>","ieee":"K. Chatterjee, R. Ibsen-Jensen, A. K. Goharshady, and A. Pavlogiannis, <i>Algorithms for algebraic path properties in concurrent systems of constant treewidth components</i>. IST Austria, 2015."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","first_name":"Krishnendu"},{"id":"3B699956-F248-11E8-B48F-1D18A9856A87","full_name":"Ibsen-Jensen, Rasmus","orcid":"0000-0003-4783-0389","last_name":"Ibsen-Jensen","first_name":"Rasmus"},{"first_name":"Amir","last_name":"Goharshady","orcid":"0000-0003-1702-6584","full_name":"Goharshady, Amir","id":"391365CE-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Andreas","last_name":"Pavlogiannis","full_name":"Pavlogiannis, Andreas","orcid":"0000-0002-8943-0722","id":"49704004-F248-11E8-B48F-1D18A9856A87"}],"date_updated":"2023-09-19T14:36:19Z","type":"technical_report","oa_version":"Published Version","day":"11","year":"2015"},{"publication_identifier":{"issn":["2664-1690"]},"scopus_import":1,"alternative_title":["IST Austria Technical Report"],"status":"public","date_created":"2018-12-12T11:39:21Z","month":"07","page":"22","pubrep_id":"344","date_published":"2015-07-14T00:00:00Z","file":[{"relation":"main_file","date_created":"2018-12-12T11:53:37Z","content_type":"application/pdf","creator":"system","file_size":658747,"date_updated":"2020-07-14T12:46:57Z","file_id":"5498","file_name":"IST-2015-343-v2+1_main.pdf","checksum":"98fd936102f3e057fc321ef6d316001d","access_level":"open_access"},{"file_id":"6316","date_updated":"2020-07-14T12:46:57Z","access_level":"closed","checksum":"b31d09b1241b59c75e1f42dadf09d258","file_name":"IST-2015-343-v2+2_anonymous.txt","date_created":"2019-04-16T12:36:08Z","relation":"main_file","file_size":139,"content_type":"text/plain","creator":"dernst"}],"publisher":"IST Austria","file_date_updated":"2020-07-14T12:46:57Z","language":[{"iso":"eng"}],"ddc":["000"],"related_material":{"record":[{"status":"public","relation":"later_version","id":"1437"},{"relation":"later_version","status":"public","id":"5441"},{"relation":"later_version","status":"public","id":"6009"}]},"oa":1,"has_accepted_license":"1","_id":"5442","title":"Algorithms for algebraic path properties in concurrent systems of constant treewidth components","publication_status":"published","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 properties that arise in program analysis.\r\nWe consider that each component of the concurrent system is a graph with constant treewidth, and it is known that the controlflow graphs of most programs have constant treewidth. We allow for multiple possible queries, which arise naturally in demand driven dataflow analysis problems (e.g., alias analysis). The study of multiple queries allows us to consider the tradeoff between the resource usage of the \\emph{one-time} preprocessing and for \\emph{each individual} query. The traditional approaches construct the product graph of all components and apply the best-known graph algorithm on the product. In the traditional approach, even the answer to a single query requires the transitive closure computation (i.e., the results of all possible queries), which provides no room for tradeoff between preprocessing and query time.\r\n\r\nOur 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, \r\neach 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 that show that the worst-case running times of our algorithms cannot be improved without achieving major breakthroughs in graph algorithms (such as improving \r\nthe worst-case bounds for the shortest path problem in general graphs whose current best-known bound has not been improved in five decades). Finally, we provide a prototype implementation of our algorithms which significantly outperforms the existing algorithmic methods on several benchmarks."}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"full_name":"Anonymous, 1","first_name":"1","last_name":"Anonymous"},{"full_name":"Anonymous, 2","last_name":"Anonymous","first_name":"2"},{"full_name":"Anonymous, 3","last_name":"Anonymous","first_name":"3"},{"last_name":"Anonymous","first_name":"4","full_name":"Anonymous, 4"}],"citation":{"apa":"Anonymous, 1, Anonymous, 2, Anonymous, 3, &#38; Anonymous, 4. (2015). <i>Algorithms for algebraic path properties in concurrent systems of constant treewidth components</i>. IST Austria.","mla":"Anonymous, 1, et al. <i>Algorithms for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components</i>. IST Austria, 2015.","short":"1 Anonymous, 2 Anonymous, 3 Anonymous, 4 Anonymous, Algorithms for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components, IST Austria, 2015.","chicago":"Anonymous, 1, 2 Anonymous, 3 Anonymous, and 4 Anonymous. <i>Algorithms for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components</i>. IST Austria, 2015.","ista":"Anonymous 1, Anonymous 2, Anonymous 3, Anonymous 4. 2015. Algorithms for algebraic path properties in concurrent systems of constant treewidth components, IST Austria, 22p.","ieee":"1 Anonymous, 2 Anonymous, 3 Anonymous, and 4 Anonymous, <i>Algorithms for algebraic path properties in concurrent systems of constant treewidth components</i>. IST Austria, 2015.","ama":"Anonymous 1, Anonymous 2, Anonymous 3, Anonymous 4. <i>Algorithms for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components</i>. IST Austria; 2015."},"day":"14","year":"2015","type":"technical_report","date_updated":"2023-09-19T14:36:19Z","oa_version":"Published Version"},{"alternative_title":["IST Austria Technical Report"],"publication_identifier":{"issn":["2664-1690"]},"date_created":"2018-12-12T11:39:22Z","month":"11","status":"public","date_published":"2015-11-06T00:00:00Z","file":[{"file_name":"IST-2015-325-v2+1_main.pdf","checksum":"f0fa31ad8161ed655137e94012123ef9","access_level":"open_access","file_id":"5466","date_updated":"2020-07-14T12:46:57Z","file_size":412379,"creator":"system","content_type":"application/pdf","relation":"main_file","date_created":"2018-12-12T11:53:05Z"}],"page":"23","pubrep_id":"362","file_date_updated":"2020-07-14T12:46:57Z","publisher":"IST Austria","title":"A symbolic SAT-based algorithm for almost-sure reachability with small strategies in POMDPs","language":[{"iso":"eng"}],"ddc":["000"],"doi":"10.15479/AT:IST-2015-325-v2-1","related_material":{"record":[{"id":"1166","status":"public","relation":"later_version"}]},"oa":1,"_id":"5443","department":[{"_id":"KrCh"}],"has_accepted_license":"1","publication_status":"published","abstract":[{"lang":"eng","text":"POMDPs are standard models for probabilistic planning problems, where an agent interacts with an uncertain environment. We study the problem of almost-sure reachability, where given a set of target states, the question is to decide whether there is a policy to ensure that the target set is reached with probability 1 (almost-surely). While in general the problem is EXPTIME-complete, in many practical cases policies with a small amount of memory suffice. Moreover, the existing solution to the problem is explicit, which first requires to construct explicitly an exponential reduction to a belief-support MDP. In this work, we first study the existence of observation-stationary strategies, which is NP-complete, and then small-memory strategies. We present a symbolic algorithm by an efficient encoding to SAT and using a SAT solver for the problem. We report experimental results demonstrating the scalability of our symbolic (SAT-based) approach."}],"citation":{"chicago":"Chatterjee, Krishnendu, Martin Chmelik, and Jessica Davies. <i>A Symbolic SAT-Based Algorithm for Almost-Sure Reachability with Small Strategies in POMDPs</i>. IST Austria, 2015. <a href=\"https://doi.org/10.15479/AT:IST-2015-325-v2-1\">https://doi.org/10.15479/AT:IST-2015-325-v2-1</a>.","short":"K. Chatterjee, M. Chmelik, J. Davies, A Symbolic SAT-Based Algorithm for Almost-Sure Reachability with Small Strategies in POMDPs, IST Austria, 2015.","ista":"Chatterjee K, Chmelik M, Davies J. 2015. A symbolic SAT-based algorithm for almost-sure reachability with small strategies in POMDPs, IST Austria, 23p.","ama":"Chatterjee K, Chmelik M, Davies J. <i>A Symbolic SAT-Based Algorithm for Almost-Sure Reachability with Small Strategies in POMDPs</i>. IST Austria; 2015. doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-325-v2-1\">10.15479/AT:IST-2015-325-v2-1</a>","ieee":"K. Chatterjee, M. Chmelik, and J. Davies, <i>A symbolic SAT-based algorithm for almost-sure reachability with small strategies in POMDPs</i>. IST Austria, 2015.","mla":"Chatterjee, Krishnendu, et al. <i>A Symbolic SAT-Based Algorithm for Almost-Sure Reachability with Small Strategies in POMDPs</i>. IST Austria, 2015, doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-325-v2-1\">10.15479/AT:IST-2015-325-v2-1</a>.","apa":"Chatterjee, K., Chmelik, M., &#38; Davies, J. (2015). <i>A symbolic SAT-based algorithm for almost-sure reachability with small strategies in POMDPs</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2015-325-v2-1\">https://doi.org/10.15479/AT:IST-2015-325-v2-1</a>"},"author":[{"last_name":"Chatterjee","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Chmelik, Martin","id":"3624234E-F248-11E8-B48F-1D18A9856A87","first_name":"Martin","last_name":"Chmelik"},{"id":"378E0060-F248-11E8-B48F-1D18A9856A87","full_name":"Davies, Jessica","last_name":"Davies","first_name":"Jessica"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"technical_report","date_updated":"2023-02-21T16:24:05Z","oa_version":"Published Version","day":"06","year":"2015"},{"publication_identifier":{"issn":["2664-1690"]},"alternative_title":["IST Austria Technical Report"],"status":"public","month":"12","date_created":"2018-12-12T11:39:22Z","pubrep_id":"399","page":"25","file":[{"date_created":"2018-12-12T11:53:24Z","relation":"main_file","creator":"system","content_type":"application/pdf","file_size":3533200,"file_id":"5485","date_updated":"2020-07-14T12:46:58Z","access_level":"open_access","file_name":"IST-2015-399-v1+1_treeomics.pdf","checksum":"c47d33bdda06181753c0af36f16e7b5d"}],"date_published":"2015-12-30T00:00:00Z","publisher":"IST Austria","file_date_updated":"2020-07-14T12:46:58Z","_id":"5444","has_accepted_license":"1","department":[{"_id":"KrCh"}],"language":[{"iso":"eng"}],"ddc":["000","576"],"oa":1,"doi":"10.15479/AT:IST-2015-399-v1-1","title":"Reconstructing robust phylogenies of metastatic cancers","abstract":[{"text":"A comprehensive understanding of the clonal evolution of cancer is critical for understanding neoplasia. Genome-wide sequencing data enables evolutionary studies at unprecedented depth. However, classical phylogenetic methods often struggle with noisy sequencing data of impure DNA samples and fail to detect subclones that have different evolutionary trajectories. We have developed a tool, called Treeomics, that allows us to reconstruct the phylogeny of a cancer with commonly available sequencing technologies. Using Bayesian inference and Integer Linear Programming, robust phylogenies consistent with the biological processes underlying cancer evolution were obtained for pancreatic, ovarian, and prostate cancers. Furthermore, Treeomics correctly identified sequencing artifacts such as those resulting from low statistical power; nearly 7% of variants were misclassified by conventional statistical methods. These artifacts can skew phylogenies by creating illusory tumor heterogeneity among distinct samples. Importantly, we show that the evolutionary trees generated with Treeomics are mathematically optimal.","lang":"eng"}],"publication_status":"published","author":[{"first_name":"Johannes","last_name":"Reiter","id":"4A918E98-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-0170-7353","full_name":"Reiter, Johannes"},{"full_name":"Makohon-Moore, Alvin","first_name":"Alvin","last_name":"Makohon-Moore"},{"first_name":"Jeffrey","last_name":"Gerold","full_name":"Gerold, Jeffrey"},{"last_name":"Bozic","first_name":"Ivana","full_name":"Bozic, Ivana"},{"first_name":"Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"full_name":"Iacobuzio-Donahue, Christine","last_name":"Iacobuzio-Donahue","first_name":"Christine"},{"last_name":"Vogelstein","first_name":"Bert","full_name":"Vogelstein, Bert"},{"full_name":"Nowak, Martin","first_name":"Martin","last_name":"Nowak"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"mla":"Reiter, Johannes, et al. <i>Reconstructing Robust Phylogenies of Metastatic Cancers</i>. IST Austria, 2015, doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-399-v1-1\">10.15479/AT:IST-2015-399-v1-1</a>.","apa":"Reiter, J., Makohon-Moore, A., Gerold, J., Bozic, I., Chatterjee, K., Iacobuzio-Donahue, C., … Nowak, M. (2015). <i>Reconstructing robust phylogenies of metastatic cancers</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2015-399-v1-1\">https://doi.org/10.15479/AT:IST-2015-399-v1-1</a>","short":"J. Reiter, A. Makohon-Moore, J. Gerold, I. Bozic, K. Chatterjee, C. Iacobuzio-Donahue, B. Vogelstein, M. Nowak, Reconstructing Robust Phylogenies of Metastatic Cancers, IST Austria, 2015.","chicago":"Reiter, Johannes, Alvin Makohon-Moore, Jeffrey Gerold, Ivana Bozic, Krishnendu Chatterjee, Christine Iacobuzio-Donahue, Bert Vogelstein, and Martin Nowak. <i>Reconstructing Robust Phylogenies of Metastatic Cancers</i>. IST Austria, 2015. <a href=\"https://doi.org/10.15479/AT:IST-2015-399-v1-1\">https://doi.org/10.15479/AT:IST-2015-399-v1-1</a>.","ista":"Reiter J, Makohon-Moore A, Gerold J, Bozic I, Chatterjee K, Iacobuzio-Donahue C, Vogelstein B, Nowak M. 2015. Reconstructing robust phylogenies of metastatic cancers, IST Austria, 25p.","ieee":"J. Reiter <i>et al.</i>, <i>Reconstructing robust phylogenies of metastatic cancers</i>. IST Austria, 2015.","ama":"Reiter J, Makohon-Moore A, Gerold J, et al. <i>Reconstructing Robust Phylogenies of Metastatic Cancers</i>. IST Austria; 2015. doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-399-v1-1\">10.15479/AT:IST-2015-399-v1-1</a>"},"year":"2015","day":"30","oa_version":"Published Version","date_updated":"2020-07-14T23:05:07Z","type":"technical_report"},{"date_published":"2015-08-13T00:00:00Z","keyword":["Markov Decision Process","Decision Tree","Probabilistic Verification","Counterexample Explanation"],"file":[{"file_size":49557109,"creator":"system","content_type":"application/zip","relation":"main_file","date_created":"2018-12-12T13:02:31Z","checksum":"b8bcb43c0893023cda66c1b69c16ac62","file_name":"IST-2015-28-v1+2_Fellner_DataRep.zip","access_level":"open_access","date_updated":"2020-07-14T12:47:00Z","file_id":"5597"}],"datarep_id":"28","doi":"10.15479/AT:ISTA:28","license":"https://creativecommons.org/publicdomain/zero/1.0/","has_accepted_license":"1","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"ec_funded":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","contributor":[{"last_name":"Kretinsky","first_name":"Jan","id":"44CEF464-F248-11E8-B48F-1D18A9856A87"}],"day":"13","date_updated":"2024-02-21T13:52:07Z","type":"research_data","oa_version":"Published Version","publist_id":"5564","status":"public","date_created":"2018-12-12T12:31:29Z","month":"08","publisher":"Institute of Science and Technology Austria","file_date_updated":"2020-07-14T12:47:00Z","oa":1,"related_material":{"record":[{"relation":"popular_science","status":"public","id":"1603"}]},"ddc":["004"],"_id":"5549","title":"Experimental part of CAV 2015 publication: Counterexample Explanation by Learning Small Strategies in Markov Decision Processes","abstract":[{"lang":"eng","text":"This repository contains the experimental part of the CAV 2015 publication Counterexample Explanation by Learning Small Strategies in Markov Decision Processes.\r\nWe extended the probabilistic model checker PRISM to represent strategies of Markov Decision Processes as Decision Trees.\r\nThe archive contains a java executable version of the extended tool (prism_dectree.jar) together with a few examples of the PRISM benchmark library.\r\nTo execute the program, please have a look at the README.txt, which provides instructions and further information on the archive.\r\nThe archive contains scripts that (if run often enough) reproduces the data presented in the publication."}],"project":[{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications"},{"call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425","name":"Rigorous Systems Engineering","grant_number":"S 11407_N23"}],"author":[{"full_name":"Fellner, Andreas","id":"42BABFB4-F248-11E8-B48F-1D18A9856A87","last_name":"Fellner","first_name":"Andreas"}],"citation":{"ama":"Fellner A. Experimental part of CAV 2015 publication: Counterexample Explanation by Learning Small Strategies in Markov Decision Processes. 2015. doi:<a href=\"https://doi.org/10.15479/AT:ISTA:28\">10.15479/AT:ISTA:28</a>","ieee":"A. Fellner, “Experimental part of CAV 2015 publication: Counterexample Explanation by Learning Small Strategies in Markov Decision Processes.” Institute of Science and Technology Austria, 2015.","ista":"Fellner A. 2015. Experimental part of CAV 2015 publication: Counterexample Explanation by Learning Small Strategies in Markov Decision Processes, Institute of Science and Technology Austria, <a href=\"https://doi.org/10.15479/AT:ISTA:28\">10.15479/AT:ISTA:28</a>.","chicago":"Fellner, Andreas. “Experimental Part of CAV 2015 Publication: Counterexample Explanation by Learning Small Strategies in Markov Decision Processes.” Institute of Science and Technology Austria, 2015. <a href=\"https://doi.org/10.15479/AT:ISTA:28\">https://doi.org/10.15479/AT:ISTA:28</a>.","short":"A. Fellner, (2015).","apa":"Fellner, A. (2015). Experimental part of CAV 2015 publication: Counterexample Explanation by Learning Small Strategies in Markov Decision Processes. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/AT:ISTA:28\">https://doi.org/10.15479/AT:ISTA:28</a>","mla":"Fellner, Andreas. <i>Experimental Part of CAV 2015 Publication: Counterexample Explanation by Learning Small Strategies in Markov Decision Processes</i>. Institute of Science and Technology Austria, 2015, doi:<a href=\"https://doi.org/10.15479/AT:ISTA:28\">10.15479/AT:ISTA:28</a>."},"year":"2015","tmp":{"short":"CC0 (1.0)","legal_code_url":"https://creativecommons.org/publicdomain/zero/1.0/legalcode","name":"Creative Commons Public Domain Dedication (CC0 1.0)","image":"/images/cc_0.png"}},{"citation":{"mla":"Biswas, Ranita, and Partha Bhowmick. “From Prima Quadraginta Octant to Lattice Sphere through Primitive Integer Operations.” <i>Theoretical Computer Science</i>, vol. 624, no. 4, Elsevier, 2015, pp. 56–72, doi:<a href=\"https://doi.org/10.1016/j.tcs.2015.11.018\">10.1016/j.tcs.2015.11.018</a>.","apa":"Biswas, R., &#38; Bhowmick, P. (2015). From prima quadraginta octant to lattice sphere through primitive integer operations. <i>Theoretical Computer Science</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.tcs.2015.11.018\">https://doi.org/10.1016/j.tcs.2015.11.018</a>","ieee":"R. Biswas and P. Bhowmick, “From prima quadraginta octant to lattice sphere through primitive integer operations,” <i>Theoretical Computer Science</i>, vol. 624, no. 4. Elsevier, pp. 56–72, 2015.","ama":"Biswas R, Bhowmick P. From prima quadraginta octant to lattice sphere through primitive integer operations. <i>Theoretical Computer Science</i>. 2015;624(4):56-72. doi:<a href=\"https://doi.org/10.1016/j.tcs.2015.11.018\">10.1016/j.tcs.2015.11.018</a>","ista":"Biswas R, Bhowmick P. 2015. From prima quadraginta octant to lattice sphere through primitive integer operations. Theoretical Computer Science. 624(4), 56–72.","short":"R. Biswas, P. Bhowmick, Theoretical Computer Science 624 (2015) 56–72.","chicago":"Biswas, Ranita, and Partha Bhowmick. “From Prima Quadraginta Octant to Lattice Sphere through Primitive Integer Operations.” <i>Theoretical Computer Science</i>. Elsevier, 2015. <a href=\"https://doi.org/10.1016/j.tcs.2015.11.018\">https://doi.org/10.1016/j.tcs.2015.11.018</a>."},"author":[{"last_name":"Biswas","first_name":"Ranita","orcid":"0000-0002-5372-7890","full_name":"Biswas, Ranita","id":"3C2B033E-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Partha","last_name":"Bhowmick","full_name":"Bhowmick, Partha"}],"quality_controlled":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","extern":"1","oa_version":"None","type":"journal_article","date_updated":"2021-01-12T08:03:36Z","year":"2015","day":"18","title":"From prima quadraginta octant to lattice sphere through primitive integer operations","publication":"Theoretical Computer Science","_id":"5804","doi":"10.1016/j.tcs.2015.11.018","language":[{"iso":"eng"}],"abstract":[{"lang":"eng","text":"We present here the first integer-based algorithm for constructing a well-defined lattice sphere specified by integer radius and integer center. The algorithm evolves from a unique correspondence between the lattice points comprising the sphere and the distribution of sum of three square numbers in integer intervals. We characterize these intervals to derive a useful set of recurrences, which, in turn, aids in efficient computation. Each point of the lattice sphere is determined by resorting to only a few primitive operations in the integer domain. The symmetry of its quadraginta octants provides an added advantage by confining the computation to its prima quadraginta octant. Detailed theoretical analysis and experimental results have been furnished to demonstrate its simplicity and elegance."}],"publication_status":"published","date_published":"2015-04-18T00:00:00Z","volume":624,"page":"56-72","issue":"4","publisher":"Elsevier","intvolume":"       624","publication_identifier":{"issn":["0304-3975"]},"month":"04","date_created":"2019-01-08T20:44:06Z","status":"public"},{"oa_version":"None","type":"journal_article","date_updated":"2021-01-12T08:03:37Z","year":"2015","day":"09","citation":{"apa":"Biswas, R., &#38; Bhowmick, P. (2015). On different topological classes of spherical geodesic paths and circles inZ3. <i>Theoretical Computer Science</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.tcs.2015.09.003\">https://doi.org/10.1016/j.tcs.2015.09.003</a>","mla":"Biswas, Ranita, and Partha Bhowmick. “On Different Topological Classes of Spherical Geodesic Paths and Circles InZ3.” <i>Theoretical Computer Science</i>, vol. 605, no. 11, Elsevier, 2015, pp. 146–63, doi:<a href=\"https://doi.org/10.1016/j.tcs.2015.09.003\">10.1016/j.tcs.2015.09.003</a>.","ama":"Biswas R, Bhowmick P. On different topological classes of spherical geodesic paths and circles inZ3. <i>Theoretical Computer Science</i>. 2015;605(11):146-163. doi:<a href=\"https://doi.org/10.1016/j.tcs.2015.09.003\">10.1016/j.tcs.2015.09.003</a>","ieee":"R. Biswas and P. Bhowmick, “On different topological classes of spherical geodesic paths and circles inZ3,” <i>Theoretical Computer Science</i>, vol. 605, no. 11. Elsevier, pp. 146–163, 2015.","ista":"Biswas R, Bhowmick P. 2015. On different topological classes of spherical geodesic paths and circles inZ3. Theoretical Computer Science. 605(11), 146–163.","chicago":"Biswas, Ranita, and Partha Bhowmick. “On Different Topological Classes of Spherical Geodesic Paths and Circles InZ3.” <i>Theoretical Computer Science</i>. Elsevier, 2015. <a href=\"https://doi.org/10.1016/j.tcs.2015.09.003\">https://doi.org/10.1016/j.tcs.2015.09.003</a>.","short":"R. Biswas, P. Bhowmick, Theoretical Computer Science 605 (2015) 146–163."},"quality_controlled":"1","author":[{"first_name":"Ranita","last_name":"Biswas","id":"3C2B033E-F248-11E8-B48F-1D18A9856A87","full_name":"Biswas, Ranita","orcid":"0000-0002-5372-7890"},{"full_name":"Bhowmick, Partha","last_name":"Bhowmick","first_name":"Partha"}],"extern":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_status":"published","publication":"Theoretical Computer Science","title":"On different topological classes of spherical geodesic paths and circles inZ3","_id":"5807","language":[{"iso":"eng"}],"doi":"10.1016/j.tcs.2015.09.003","publisher":"Elsevier","date_published":"2015-11-09T00:00:00Z","page":"146-163","issue":"11","volume":605,"month":"11","date_created":"2019-01-08T20:44:52Z","status":"public","intvolume":"       605","publication_identifier":{"issn":["0304-3975"]}},{"day":"08","year":"2015","date_updated":"2021-01-12T08:03:37Z","type":"journal_article","oa_version":"None","quality_controlled":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","extern":"1","author":[{"id":"3C2B033E-F248-11E8-B48F-1D18A9856A87","full_name":"Biswas, Ranita","orcid":"0000-0002-5372-7890","last_name":"Biswas","first_name":"Ranita"},{"full_name":"Bhowmick, Partha","first_name":"Partha","last_name":"Bhowmick"}],"citation":{"mla":"Biswas, Ranita, and Partha Bhowmick. “Layer the Sphere.” <i>The Visual Computer</i>, vol. 31, no. 6–8, Springer Nature, 2015, pp. 787–97, doi:<a href=\"https://doi.org/10.1007/s00371-015-1101-3\">10.1007/s00371-015-1101-3</a>.","apa":"Biswas, R., &#38; Bhowmick, P. (2015). Layer the sphere. <i>The Visual Computer</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00371-015-1101-3\">https://doi.org/10.1007/s00371-015-1101-3</a>","chicago":"Biswas, Ranita, and Partha Bhowmick. “Layer the Sphere.” <i>The Visual Computer</i>. Springer Nature, 2015. <a href=\"https://doi.org/10.1007/s00371-015-1101-3\">https://doi.org/10.1007/s00371-015-1101-3</a>.","short":"R. Biswas, P. Bhowmick, The Visual Computer 31 (2015) 787–797.","ista":"Biswas R, Bhowmick P. 2015. Layer the sphere. The Visual Computer. 31(6–8), 787–797.","ama":"Biswas R, Bhowmick P. Layer the sphere. <i>The Visual Computer</i>. 2015;31(6-8):787-797. doi:<a href=\"https://doi.org/10.1007/s00371-015-1101-3\">10.1007/s00371-015-1101-3</a>","ieee":"R. Biswas and P. Bhowmick, “Layer the sphere,” <i>The Visual Computer</i>, vol. 31, no. 6–8. Springer Nature, pp. 787–797, 2015."},"publication_status":"published","language":[{"iso":"eng"}],"doi":"10.1007/s00371-015-1101-3","_id":"5808","title":"Layer the sphere","publication":"The Visual Computer","publisher":"Springer Nature","page":"787-797","volume":31,"issue":"6-8","date_published":"2015-05-08T00:00:00Z","status":"public","date_created":"2019-01-08T20:45:05Z","month":"05","publication_identifier":{"issn":["0178-2789","1432-2315"]},"intvolume":"        31"},{"status":"public","month":"03","date_created":"2018-12-11T11:47:23Z","publist_id":"7206","intvolume":"        16","publisher":"Nature Publishing Group","volume":16,"issue":"3","page":"129 - 143","date_published":"2015-03-26T00:00:00Z","abstract":[{"lang":"eng","text":"Transcription of eukaryotic protein-coding genes commences with the assembly of a conserved initiation complex, which consists of RNA polymerase II (Pol II) and the general transcription factors, at promoter DNA. After two decades of research, the structural basis of transcription initiation is emerging. Crystal structures of many components of the initiation complex have been resolved, and structural information on Pol II complexes with general transcription factors has recently been obtained. Although mechanistic details await elucidation, available data outline how Pol II cooperates with the general transcription factors to bind to and open promoter DNA, and how Pol II directs RNA synthesis and escapes from the promoter."}],"publication_status":"published","_id":"594","language":[{"iso":"eng"}],"doi":"10.1038/nrm3952","publication":"Nature Reviews Molecular Cell Biology","title":"Structural basis of transcription initiation by RNA polymerase II","year":"2015","day":"26","oa_version":"None","date_updated":"2021-01-12T08:05:16Z","type":"journal_article","author":[{"full_name":"Sainsbury, Sarah","first_name":"Sarah","last_name":"Sainsbury"},{"first_name":"Carrie A","last_name":"Bernecky","id":"2CB9DFE2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-0893-7036","full_name":"Bernecky, Carrie A"},{"full_name":"Cramer, Patrick","first_name":"Patrick","last_name":"Cramer"}],"article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","extern":"1","citation":{"apa":"Sainsbury, S., Bernecky, C., &#38; Cramer, P. (2015). Structural basis of transcription initiation by RNA polymerase II. <i>Nature Reviews Molecular Cell Biology</i>. Nature Publishing Group. <a href=\"https://doi.org/10.1038/nrm3952\">https://doi.org/10.1038/nrm3952</a>","mla":"Sainsbury, Sarah, et al. “Structural Basis of Transcription Initiation by RNA Polymerase II.” <i>Nature Reviews Molecular Cell Biology</i>, vol. 16, no. 3, Nature Publishing Group, 2015, pp. 129–43, doi:<a href=\"https://doi.org/10.1038/nrm3952\">10.1038/nrm3952</a>.","ista":"Sainsbury S, Bernecky C, Cramer P. 2015. Structural basis of transcription initiation by RNA polymerase II. Nature Reviews Molecular Cell Biology. 16(3), 129–143.","short":"S. Sainsbury, C. Bernecky, P. Cramer, Nature Reviews Molecular Cell Biology 16 (2015) 129–143.","chicago":"Sainsbury, Sarah, Carrie Bernecky, and Patrick Cramer. “Structural Basis of Transcription Initiation by RNA Polymerase II.” <i>Nature Reviews Molecular Cell Biology</i>. Nature Publishing Group, 2015. <a href=\"https://doi.org/10.1038/nrm3952\">https://doi.org/10.1038/nrm3952</a>.","ama":"Sainsbury S, Bernecky C, Cramer P. Structural basis of transcription initiation by RNA polymerase II. <i>Nature Reviews Molecular Cell Biology</i>. 2015;16(3):129-143. doi:<a href=\"https://doi.org/10.1038/nrm3952\">10.1038/nrm3952</a>","ieee":"S. Sainsbury, C. Bernecky, and P. Cramer, “Structural basis of transcription initiation by RNA polymerase II,” <i>Nature Reviews Molecular Cell Biology</i>, vol. 16, no. 3. Nature Publishing Group, pp. 129–143, 2015."}},{"language":[{"iso":"eng"}],"doi":"10.1073/pnas.1423808112","has_accepted_license":"1","type":"journal_article","date_updated":"2021-01-12T08:06:12Z","oa_version":"Published Version","day":"07","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","publication_identifier":{"issn":["0027-8424","1091-6490"]},"date_published":"2015-07-07T00:00:00Z","external_id":{"pmid":["26100886"]},"file":[{"file_size":2822681,"content_type":"application/pdf","creator":"kschuh","date_created":"2019-03-19T14:21:07Z","relation":"main_file","access_level":"open_access","checksum":"3d2da5af8d72467e382a565abc2e003d","file_name":"2015_PNAS_Fenk.pdf","file_id":"6119","date_updated":"2020-07-14T12:47:20Z"}],"page":"E3525-E3534","publication_status":"published","abstract":[{"text":"Carbon dioxide (CO2) gradients are ubiquitous and provide animals with information about their environment, such as the potential presence of prey or predators. The nematode Caenorhabditis elegans avoids elevated CO2, and previous work identified three neuron pairs called “BAG,” “AFD,” and “ASE” that respond to CO2 stimuli. Using in vivo Ca2+ imaging and behavioral analysis, we show that C. elegans can detect CO2 independently of these sensory pathways. Many of the C. elegans sensory neurons we examined, including the AWC olfactory neurons, the ASJ and ASK gustatory neurons, and the ASH and ADL nociceptors, respond to a rise in CO2 with a rise in Ca2+. In contrast, glial sheath cells harboring the sensory endings of C. elegans’ major chemosensory neurons exhibit strong and sustained decreases in Ca2+ in response to high CO2. Some of these CO2 responses appear to be cell intrinsic. Worms therefore may couple detection of CO2 to that of other cues at the earliest stages of sensory processing. We show that C. elegans persistently suppresses oviposition at high CO2. Hermaphrodite-specific neurons (HSNs), the executive neurons driving egg-laying, are tonically inhibited when CO2 is elevated. CO2 modulates the egg-laying system partly through the AWC olfactory neurons: High CO2 tonically activates AWC by a cGMP-dependent mechanism, and AWC output inhibits the HSNs. Our work shows that CO2 is a more complex sensory cue for C. elegans than previously thought, both in terms of behavior and neural circuitry.","lang":"eng"}],"title":"Environmental CO2 inhibits Caenorhabditis elegans egg-laying by modulating olfactory neurons and evokes widespread changes in neural activity","publication":"Proceedings of the National Academy of Sciences","pmid":1,"oa":1,"ddc":["570"],"_id":"6118","year":"2015","citation":{"short":"L.A. Fenk, M. de Bono, Proceedings of the National Academy of Sciences 112 (2015) E3525–E3534.","chicago":"Fenk, Lorenz A., and Mario de Bono. “Environmental CO2 Inhibits Caenorhabditis Elegans Egg-Laying by Modulating Olfactory Neurons and Evokes Widespread Changes in Neural Activity.” <i>Proceedings of the National Academy of Sciences</i>. National Academy of Sciences, 2015. <a href=\"https://doi.org/10.1073/pnas.1423808112\">https://doi.org/10.1073/pnas.1423808112</a>.","ista":"Fenk LA, de Bono M. 2015. Environmental CO2 inhibits Caenorhabditis elegans egg-laying by modulating olfactory neurons and evokes widespread changes in neural activity. Proceedings of the National Academy of Sciences. 112(27), E3525–E3534.","ieee":"L. A. Fenk and M. de Bono, “Environmental CO2 inhibits Caenorhabditis elegans egg-laying by modulating olfactory neurons and evokes widespread changes in neural activity,” <i>Proceedings of the National Academy of Sciences</i>, vol. 112, no. 27. National Academy of Sciences, pp. E3525–E3534, 2015.","ama":"Fenk LA, de Bono M. Environmental CO2 inhibits Caenorhabditis elegans egg-laying by modulating olfactory neurons and evokes widespread changes in neural activity. <i>Proceedings of the National Academy of Sciences</i>. 2015;112(27):E3525-E3534. doi:<a href=\"https://doi.org/10.1073/pnas.1423808112\">10.1073/pnas.1423808112</a>","apa":"Fenk, L. A., &#38; de Bono, M. (2015). Environmental CO2 inhibits Caenorhabditis elegans egg-laying by modulating olfactory neurons and evokes widespread changes in neural activity. <i>Proceedings of the National Academy of Sciences</i>. National Academy of Sciences. <a href=\"https://doi.org/10.1073/pnas.1423808112\">https://doi.org/10.1073/pnas.1423808112</a>","mla":"Fenk, Lorenz A., and Mario de Bono. “Environmental CO2 Inhibits Caenorhabditis Elegans Egg-Laying by Modulating Olfactory Neurons and Evokes Widespread Changes in Neural Activity.” <i>Proceedings of the National Academy of Sciences</i>, vol. 112, no. 27, National Academy of Sciences, 2015, pp. E3525–34, doi:<a href=\"https://doi.org/10.1073/pnas.1423808112\">10.1073/pnas.1423808112</a>."},"quality_controlled":"1","author":[{"full_name":"Fenk, Lorenz A.","last_name":"Fenk","first_name":"Lorenz A."},{"first_name":"Mario","last_name":"de Bono","full_name":"de Bono, Mario","orcid":"0000-0001-8347-0443","id":"4E3FF80E-F248-11E8-B48F-1D18A9856A87"}],"extern":"1","date_created":"2019-03-19T14:15:50Z","month":"07","status":"public","intvolume":"       112","file_date_updated":"2020-07-14T12:47:20Z","publisher":"National Academy of Sciences","volume":112,"issue":"27"},{"oa_version":"Published Version","type":"journal_article","date_updated":"2021-01-12T08:06:13Z","day":"11","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","has_accepted_license":"1","doi":"10.7554/elife.04241","language":[{"iso":"eng"}],"external_id":{"pmid":["25760081"]},"file":[{"date_updated":"2020-07-14T12:47:20Z","file_id":"6121","file_name":"2015_elife_Laurent.pdf","checksum":"cf641b7a363aecd0a101755d23dee7e0","access_level":"open_access","relation":"main_file","date_created":"2019-03-19T14:29:43Z","file_size":6723528,"content_type":"application/pdf","creator":"kschuh"}],"date_published":"2015-03-11T00:00:00Z","publication_identifier":{"issn":["2050-084X"]},"tmp":{"image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"year":"2015","citation":{"apa":"Laurent, P., Soltesz, Z., Nelson, G. M., Chen, C., Arellano-Carbajal, F., Levy, E., &#38; de Bono, M. (2015). Decoding a neural circuit controlling global animal state in C. elegans. <i>ELife</i>. eLife Sciences Publications. <a href=\"https://doi.org/10.7554/elife.04241\">https://doi.org/10.7554/elife.04241</a>","mla":"Laurent, Patrick, et al. “Decoding a Neural Circuit Controlling Global Animal State in C. Elegans.” <i>ELife</i>, vol. 4, e04241, eLife Sciences Publications, 2015, doi:<a href=\"https://doi.org/10.7554/elife.04241\">10.7554/elife.04241</a>.","chicago":"Laurent, Patrick, Zoltan Soltesz, Geoffrey M Nelson, Changchun Chen, Fausto Arellano-Carbajal, Emmanuel Levy, and Mario de Bono. “Decoding a Neural Circuit Controlling Global Animal State in C. Elegans.” <i>ELife</i>. eLife Sciences Publications, 2015. <a href=\"https://doi.org/10.7554/elife.04241\">https://doi.org/10.7554/elife.04241</a>.","short":"P. Laurent, Z. Soltesz, G.M. Nelson, C. Chen, F. Arellano-Carbajal, E. Levy, M. de Bono, ELife 4 (2015).","ista":"Laurent P, Soltesz Z, Nelson GM, Chen C, Arellano-Carbajal F, Levy E, de Bono M. 2015. Decoding a neural circuit controlling global animal state in C. elegans. eLife. 4, e04241.","ama":"Laurent P, Soltesz Z, Nelson GM, et al. Decoding a neural circuit controlling global animal state in C. elegans. <i>eLife</i>. 2015;4. doi:<a href=\"https://doi.org/10.7554/elife.04241\">10.7554/elife.04241</a>","ieee":"P. Laurent <i>et al.</i>, “Decoding a neural circuit controlling global animal state in C. elegans,” <i>eLife</i>, vol. 4. eLife Sciences Publications, 2015."},"author":[{"full_name":"Laurent, Patrick","first_name":"Patrick","last_name":"Laurent"},{"full_name":"Soltesz, Zoltan","first_name":"Zoltan","last_name":"Soltesz"},{"first_name":"Geoffrey M","last_name":"Nelson","full_name":"Nelson, Geoffrey M"},{"last_name":"Chen","first_name":"Changchun","full_name":"Chen, Changchun"},{"first_name":"Fausto","last_name":"Arellano-Carbajal","full_name":"Arellano-Carbajal, Fausto"},{"full_name":"Levy, Emmanuel","first_name":"Emmanuel","last_name":"Levy"},{"last_name":"de Bono","first_name":"Mario","orcid":"0000-0001-8347-0443","full_name":"de Bono, Mario","id":"4E3FF80E-F248-11E8-B48F-1D18A9856A87"}],"quality_controlled":"1","extern":"1","abstract":[{"text":"Brains organize behavior and physiology to optimize the response to threats or opportunities. We dissect how 21% O2, an indicator of surface exposure, reprograms C. elegans' global state, inducing sustained locomotory arousal and altering expression of neuropeptides, metabolic enzymes, and other non-neural genes. The URX O2-sensing neurons drive arousal at 21% O2 by tonically activating the RMG interneurons. Stimulating RMG is sufficient to switch behavioral state. Ablating the ASH, ADL, or ASK sensory neurons connected to RMG by gap junctions does not disrupt arousal. However, disrupting cation currents in these neurons curtails RMG neurosecretion and arousal. RMG signals high O2 by peptidergic secretion. Neuropeptide reporters reveal neural circuit state, as neurosecretion stimulates neuropeptide expression. Neural imaging in unrestrained animals shows that URX and RMG encode O2 concentration rather than behavior, while the activity of downstream interneurons such as AVB and AIY reflect both O2 levels and the behavior being executed.","lang":"eng"}],"publication_status":"published","pmid":1,"publication":"eLife","title":"Decoding a neural circuit controlling global animal state in C. elegans","_id":"6120","ddc":["570"],"oa":1,"file_date_updated":"2020-07-14T12:47:20Z","publisher":"eLife Sciences Publications","volume":4,"month":"03","date_created":"2019-03-19T14:23:51Z","status":"public","article_number":"e04241","intvolume":"         4"},{"publication_identifier":{"issn":["0006-4971","1528-0020"]},"intvolume":"       127","status":"public","date_created":"2019-05-31T09:38:50Z","month":"11","volume":127,"page":"529-537","issue":"5","date_published":"2015-11-02T00:00:00Z","external_id":{"pmid":["26552697"]},"publisher":"American Society of Hematology","doi":"10.1182/blood-2015-08-667055","language":[{"iso":"eng"}],"_id":"6507","title":"Structural basis for collagen recognition by the immune receptor OSCAR","publication":"Blood","pmid":1,"publication_status":"published","abstract":[{"lang":"eng","text":"The osteoclast-associated receptor (OSCAR) is a collagen-binding immune receptor with important roles in dendritic cell maturation and activation of inflammatory monocytes as well as in osteoclastogenesis. The crystal structure of the OSCAR ectodomain is presented, both free and in complex with a consensus triple-helical peptide (THP). The structures revealed a collagen-binding site in each immunoglobulin-like domain (D1 and D2). The THP binds near a predicted collagen-binding groove in D1, but a more extensive interaction with D2 is facilitated by the unusually wide D1-D2 interdomain angle in OSCAR. Direct binding assays, combined with site-directed mutagenesis, confirm that the primary collagen-binding site in OSCAR resides in D2, in marked contrast to the related collagen receptors, glycoprotein VI (GPVI) and leukocyte-associated immunoglobulin-like receptor-1 (LAIR-1). Monomeric OSCAR D1D2 binds to the consensus THP with a KD of 28 µM measured in solution, but shows a higher affinity (KD 1.5 μM) when binding to a solid-phase THP, most likely due to an avidity effect. These data suggest a 2-stage model for the interaction of OSCAR with a collagen fibril, with transient, low-affinity interactions initiated by the membrane-distal D1, followed by firm adhesion to the primary binding site in D2."}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","extern":"1","author":[{"orcid":"0000-0002-1864-8951","full_name":"Zhou, Long","id":"3E751364-F248-11E8-B48F-1D18A9856A87","first_name":"Long","last_name":"Zhou"},{"first_name":"J. M.","last_name":"Hinerman","full_name":"Hinerman, J. M."},{"last_name":"Blaszczyk","first_name":"M.","full_name":"Blaszczyk, M."},{"full_name":"Miller, J. L. C.","last_name":"Miller","first_name":"J. L. C."},{"full_name":"Conrady, D. G.","first_name":"D. G.","last_name":"Conrady"},{"full_name":"Barrow, A. D.","last_name":"Barrow","first_name":"A. D."},{"full_name":"Chirgadze, D. Y.","last_name":"Chirgadze","first_name":"D. Y."},{"last_name":"Bihan","first_name":"D.","full_name":"Bihan, D."},{"full_name":"Farndale, R. W.","last_name":"Farndale","first_name":"R. W."},{"first_name":"A. B.","last_name":"Herr","full_name":"Herr, A. B."}],"citation":{"apa":"Zhou, L., Hinerman, J. M., Blaszczyk, M., Miller, J. L. C., Conrady, D. G., Barrow, A. D., … Herr, A. B. (2015). Structural basis for collagen recognition by the immune receptor OSCAR. <i>Blood</i>. American Society of Hematology. <a href=\"https://doi.org/10.1182/blood-2015-08-667055\">https://doi.org/10.1182/blood-2015-08-667055</a>","mla":"Zhou, Long, et al. “Structural Basis for Collagen Recognition by the Immune Receptor OSCAR.” <i>Blood</i>, vol. 127, no. 5, American Society of Hematology, 2015, pp. 529–37, doi:<a href=\"https://doi.org/10.1182/blood-2015-08-667055\">10.1182/blood-2015-08-667055</a>.","chicago":"Zhou, Long, J. M. Hinerman, M. Blaszczyk, J. L. C. Miller, D. G. Conrady, A. D. Barrow, D. Y. Chirgadze, D. Bihan, R. W. Farndale, and A. B. Herr. “Structural Basis for Collagen Recognition by the Immune Receptor OSCAR.” <i>Blood</i>. American Society of Hematology, 2015. <a href=\"https://doi.org/10.1182/blood-2015-08-667055\">https://doi.org/10.1182/blood-2015-08-667055</a>.","short":"L. Zhou, J.M. Hinerman, M. Blaszczyk, J.L.C. Miller, D.G. Conrady, A.D. Barrow, D.Y. Chirgadze, D. Bihan, R.W. Farndale, A.B. Herr, Blood 127 (2015) 529–537.","ista":"Zhou L, Hinerman JM, Blaszczyk M, Miller JLC, Conrady DG, Barrow AD, Chirgadze DY, Bihan D, Farndale RW, Herr AB. 2015. Structural basis for collagen recognition by the immune receptor OSCAR. Blood. 127(5), 529–537.","ieee":"L. Zhou <i>et al.</i>, “Structural basis for collagen recognition by the immune receptor OSCAR,” <i>Blood</i>, vol. 127, no. 5. American Society of Hematology, pp. 529–537, 2015.","ama":"Zhou L, Hinerman JM, Blaszczyk M, et al. Structural basis for collagen recognition by the immune receptor OSCAR. <i>Blood</i>. 2015;127(5):529-537. doi:<a href=\"https://doi.org/10.1182/blood-2015-08-667055\">10.1182/blood-2015-08-667055</a>"},"day":"02","year":"2015","type":"journal_article","date_updated":"2021-01-12T08:07:47Z","oa_version":"None"},{"page":"4838-4851","volume":61,"issue":"9","date_published":"2015-09-01T00:00:00Z","external_id":{"arxiv":["1304.5220"]},"publisher":"IEEE","intvolume":"        61","status":"public","date_created":"2019-07-31T06:50:34Z","arxiv":1,"month":"09","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","author":[{"last_name":"Mondelli","first_name":"Marco","orcid":"0000-0002-3242-7020","full_name":"Mondelli, Marco","id":"27EB676C-8706-11E9-9510-7717E6697425"},{"first_name":"Hamed","last_name":"Hassani","full_name":"Hassani, Hamed"},{"full_name":"Urbanke, Rudiger","first_name":"Rudiger","last_name":"Urbanke"}],"extern":"1","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1304.5220"}],"citation":{"ama":"Mondelli M, Hassani H, Urbanke R. Scaling exponent of list decoders with applications to polar codes. <i>IEEE Transactions on Information Theory</i>. 2015;61(9):4838-4851. doi:<a href=\"https://doi.org/10.1109/tit.2015.2453315\">10.1109/tit.2015.2453315</a>","ieee":"M. Mondelli, H. Hassani, and R. Urbanke, “Scaling exponent of list decoders with applications to polar codes,” <i>IEEE Transactions on Information Theory</i>, vol. 61, no. 9. IEEE, pp. 4838–4851, 2015.","short":"M. Mondelli, H. Hassani, R. Urbanke, IEEE Transactions on Information Theory 61 (2015) 4838–4851.","chicago":"Mondelli, Marco, Hamed Hassani, and Rudiger Urbanke. “Scaling Exponent of List Decoders with Applications to Polar Codes.” <i>IEEE Transactions on Information Theory</i>. IEEE, 2015. <a href=\"https://doi.org/10.1109/tit.2015.2453315\">https://doi.org/10.1109/tit.2015.2453315</a>.","ista":"Mondelli M, Hassani H, Urbanke R. 2015. Scaling exponent of list decoders with applications to polar codes. IEEE Transactions on Information Theory. 61(9), 4838–4851.","mla":"Mondelli, Marco, et al. “Scaling Exponent of List Decoders with Applications to Polar Codes.” <i>IEEE Transactions on Information Theory</i>, vol. 61, no. 9, IEEE, 2015, pp. 4838–51, doi:<a href=\"https://doi.org/10.1109/tit.2015.2453315\">10.1109/tit.2015.2453315</a>.","apa":"Mondelli, M., Hassani, H., &#38; Urbanke, R. (2015). Scaling exponent of list decoders with applications to polar codes. <i>IEEE Transactions on Information Theory</i>. IEEE. <a href=\"https://doi.org/10.1109/tit.2015.2453315\">https://doi.org/10.1109/tit.2015.2453315</a>"},"day":"01","year":"2015","date_updated":"2021-01-12T08:08:45Z","type":"journal_article","oa_version":"Preprint","oa":1,"language":[{"iso":"eng"}],"doi":"10.1109/tit.2015.2453315","_id":"6736","title":"Scaling exponent of list decoders with applications to polar codes","publication":"IEEE Transactions on Information Theory","publication_status":"published","abstract":[{"lang":"eng","text":"Motivated by the significant performance gains which polar codes experience under successive cancellation list decoding, their scaling exponent is studied as a function of the list size. In particular, the error probability is fixed, and the tradeoff between the block length and back-off from capacity is analyzed. A lower bound is provided on the error probability under MAP decoding with list size L for any binary-input memoryless output-symmetric channel and for any class of linear codes such that their minimum distance is unbounded as the block length grows large. Then, it is shown that under MAP decoding, although the introduction of a list can significantly improve the involved constants, the scaling exponent itself, i.e., the speed at which capacity is approached, stays unaffected for any finite list size. In particular, this result applies to polar codes, since their minimum distance tends to infinity as the block length increases. A similar result is proved for genie-aided successive cancellation decoding when transmission takes place over the binary erasure channel, namely, the scaling exponent remains constant for any fixed number of helps from the genie. Note that since genie-aided successive cancellation decoding might be strictly worse than successive cancellation list decoding, the problem of establishing the scaling exponent of the latter remains open."}]},{"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1401.6060"}],"citation":{"apa":"Mondelli, M., Hassani, H., Sason, I., &#38; Urbanke, R. (2015). Achieving Marton’s region for broadcast channels using polar codes. <i>IEEE Transactions on Information Theory</i>. IEEE. <a href=\"https://doi.org/10.1109/tit.2014.2368555\">https://doi.org/10.1109/tit.2014.2368555</a>","mla":"Mondelli, Marco, et al. “Achieving Marton’s Region for Broadcast Channels Using Polar Codes.” <i>IEEE Transactions on Information Theory</i>, vol. 61, no. 2, IEEE, 2015, pp. 783–800, doi:<a href=\"https://doi.org/10.1109/tit.2014.2368555\">10.1109/tit.2014.2368555</a>.","ista":"Mondelli M, Hassani H, Sason I, Urbanke R. 2015. Achieving Marton’s region for broadcast channels using polar codes. IEEE Transactions on Information Theory. 61(2), 783–800.","chicago":"Mondelli, Marco, Hamed Hassani, Igal Sason, and Rudiger Urbanke. “Achieving Marton’s Region for Broadcast Channels Using Polar Codes.” <i>IEEE Transactions on Information Theory</i>. IEEE, 2015. <a href=\"https://doi.org/10.1109/tit.2014.2368555\">https://doi.org/10.1109/tit.2014.2368555</a>.","short":"M. Mondelli, H. Hassani, I. Sason, R. Urbanke, IEEE Transactions on Information Theory 61 (2015) 783–800.","ieee":"M. Mondelli, H. Hassani, I. Sason, and R. Urbanke, “Achieving Marton’s region for broadcast channels using polar codes,” <i>IEEE Transactions on Information Theory</i>, vol. 61, no. 2. IEEE, pp. 783–800, 2015.","ama":"Mondelli M, Hassani H, Sason I, Urbanke R. Achieving Marton’s region for broadcast channels using polar codes. <i>IEEE Transactions on Information Theory</i>. 2015;61(2):783-800. doi:<a href=\"https://doi.org/10.1109/tit.2014.2368555\">10.1109/tit.2014.2368555</a>"},"extern":"1","author":[{"last_name":"Mondelli","first_name":"Marco","id":"27EB676C-8706-11E9-9510-7717E6697425","full_name":"Mondelli, Marco","orcid":"0000-0002-3242-7020"},{"first_name":"Hamed","last_name":"Hassani","full_name":"Hassani, Hamed"},{"full_name":"Sason, Igal","first_name":"Igal","last_name":"Sason"},{"first_name":"Rudiger","last_name":"Urbanke","full_name":"Urbanke, Rudiger"}],"quality_controlled":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2021-01-12T08:08:46Z","type":"journal_article","oa_version":"Preprint","day":"01","year":"2015","title":"Achieving Marton’s region for broadcast channels using polar codes","publication":"IEEE Transactions on Information Theory","language":[{"iso":"eng"}],"oa":1,"doi":"10.1109/tit.2014.2368555","_id":"6737","publication_status":"published","abstract":[{"text":"This paper presents polar coding schemes for the two-user discrete memoryless broadcast channel (DM-BC) which achieve Marton's region with both common and private messages. This is the best achievable rate region known to date, and it is tight for all classes of two-user DM-BCs whose capacity regions are known. To accomplish this task, we first construct polar codes for both the superposition as well as binning strategy. By combining these two schemes, we obtain Marton's region with private messages only. Finally, we show how to handle the case of common information. The proposed coding schemes possess the usual advantages of polar codes, i.e., they have low encoding and decoding complexity and a superpolynomial decay rate of the error probability. We follow the lead of Goela, Abbe, and Gastpar, who recently introduced polar codes emulating the superposition and binning schemes. To align the polar indices, for both schemes, their solution involves some degradedness constraints that are assumed to hold between the auxiliary random variables and channel outputs. To remove these constraints, we consider the transmission of k blocks and employ a chaining construction that guarantees the proper alignment of the polarized indices. The techniques described in this paper are quite general, and they can be adopted to many other multiterminal scenarios whenever there polar indices need to be aligned.","lang":"eng"}],"date_published":"2015-02-01T00:00:00Z","external_id":{"arxiv":["1401.6060"]},"volume":61,"page":"783-800","issue":"2","publisher":"IEEE","intvolume":"        61","date_created":"2019-07-31T07:03:38Z","arxiv":1,"month":"02","status":"public"},{"date_published":"2015-03-01T00:00:00Z","publication_identifier":{"issn":["0003-0503"]},"alternative_title":["Bulletin of the American Physical Society"],"user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","article_processing_charge":"No","day":"01","type":"conference","date_updated":"2022-02-08T10:42:53Z","oa_version":"Published Version","language":[{"iso":"eng"}],"volume":60,"issue":"1","publisher":"American Physical Society","intvolume":"        60","article_number":"G16.00009","status":"public","date_created":"2022-02-08T10:17:09Z","month":"03","conference":{"end_date":"2015-03-06","name":"APS: American Physical Society","location":"San Antonio, TX, United States","start_date":"2015-03-02"},"extern":"1","author":[{"first_name":"Hryhoriy","last_name":"Polshyn","id":"edfc7cb1-526e-11ec-b05a-e6ecc27e4e48","orcid":"0000-0001-8223-8896","full_name":"Polshyn, Hryhoriy"},{"full_name":"Zhang, Can","first_name":"Can","last_name":"Zhang"},{"first_name":"Tyler","last_name":"Naibert","full_name":"Naibert, Tyler"},{"full_name":"Eckstein, James","first_name":"James","last_name":"Eckstein"},{"full_name":"Budakian, Raffi","first_name":"Raffi","last_name":"Budakian"}],"quality_controlled":"1","citation":{"mla":"Polshyn, Hryhoriy, et al. “Study of Fe (Se, Te) Micron-Sized Rings by Magnetic Force Microscopy.” <i>APS March Meeting 2015</i>, vol. 60, no. 1, G16.00009, American Physical Society, 2015.","apa":"Polshyn, H., Zhang, C., Naibert, T., Eckstein, J., &#38; Budakian, R. (2015). Study of Fe (Se, Te) micron-sized rings by magnetic force microscopy. In <i>APS March Meeting 2015</i> (Vol. 60). San Antonio, TX, United States: American Physical Society.","chicago":"Polshyn, Hryhoriy, Can Zhang, Tyler Naibert, James Eckstein, and Raffi Budakian. “Study of Fe (Se, Te) Micron-Sized Rings by Magnetic Force Microscopy.” In <i>APS March Meeting 2015</i>, Vol. 60. American Physical Society, 2015.","short":"H. Polshyn, C. Zhang, T. Naibert, J. Eckstein, R. Budakian, in:, APS March Meeting 2015, American Physical Society, 2015.","ista":"Polshyn H, Zhang C, Naibert T, Eckstein J, Budakian R. 2015. Study of Fe (Se, Te) micron-sized rings by magnetic force microscopy. APS March Meeting 2015. APS: American Physical Society, Bulletin of the American Physical Society, vol. 60, G16.00009.","ama":"Polshyn H, Zhang C, Naibert T, Eckstein J, Budakian R. Study of Fe (Se, Te) micron-sized rings by magnetic force microscopy. In: <i>APS March Meeting 2015</i>. Vol 60. American Physical Society; 2015.","ieee":"H. Polshyn, C. Zhang, T. Naibert, J. Eckstein, and R. Budakian, “Study of Fe (Se, Te) micron-sized rings by magnetic force microscopy,” in <i>APS March Meeting 2015</i>, San Antonio, TX, United States, 2015, vol. 60, no. 1."},"main_file_link":[{"open_access":"1","url":"https://meetings.aps.org/Meeting/MAR15/Event/238442"}],"year":"2015","oa":1,"_id":"10748","title":"Study of Fe (Se, Te) micron-sized rings by magnetic force microscopy","publication":"APS March Meeting 2015","publication_status":"published","abstract":[{"lang":"eng","text":"The study of fluxoid states and fluxoid dynamics in mesoscopic iron-based superconducting rings is valuable for characterizing the basic properties of the superconductor, and may also provide important insight into the superconducting paring symmetry. We report the fabrications of micron-sized rings and disks from thin films of Fe(Se, Te) grown by molecular beam epitaxy. In order to study fluxoid states in rings we developed a custom-tailored version of magnetic force microscopy (MFM). This technique has a number of qualitative advantages for working with mesoscopic superconducting samples in comparison to the conventional MFM and other imaging techniques. We observed metastable fluxoid states in rings of different sizes. Thermally activated fluxoid dynamics of these states was studied and modeled. In addition, we found different regimes of interaction between Fe(Se, Te) ring and MFM tip which are explained. Possibilities of the existence of exotic vortex states and proposals for experiments to test the symmetry of the superconducting order parameter in iron based superconductors are analyzed."}]},{"year":"2015","tmp":{"image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"quality_controlled":"1","author":[{"full_name":"Parise, Francesca","last_name":"Parise","first_name":"Francesca"},{"last_name":"Lygeros","first_name":"John","full_name":"Lygeros, John"},{"first_name":"Jakob","last_name":"Ruess","id":"4A245D00-F248-11E8-B48F-1D18A9856A87","full_name":"Ruess, Jakob","orcid":"0000-0003-1615-3282"}],"citation":{"mla":"Parise, Francesca, et al. “Bayesian Inference for Stochastic Individual-Based Models of Ecological Systems: A Pest Control Simulation Study.” <i>Frontiers in Environmental Science</i>, vol. 3, 42, Frontiers, 2015, doi:<a href=\"https://doi.org/10.3389/fenvs.2015.00042\">10.3389/fenvs.2015.00042</a>.","apa":"Parise, F., Lygeros, J., &#38; Ruess, J. (2015). Bayesian inference for stochastic individual-based models of ecological systems: a pest control simulation study. <i>Frontiers in Environmental Science</i>. Frontiers. <a href=\"https://doi.org/10.3389/fenvs.2015.00042\">https://doi.org/10.3389/fenvs.2015.00042</a>","ama":"Parise F, Lygeros J, Ruess J. Bayesian inference for stochastic individual-based models of ecological systems: a pest control simulation study. <i>Frontiers in Environmental Science</i>. 2015;3. doi:<a href=\"https://doi.org/10.3389/fenvs.2015.00042\">10.3389/fenvs.2015.00042</a>","ieee":"F. Parise, J. Lygeros, and J. Ruess, “Bayesian inference for stochastic individual-based models of ecological systems: a pest control simulation study,” <i>Frontiers in Environmental Science</i>, vol. 3. Frontiers, 2015.","ista":"Parise F, Lygeros J, Ruess J. 2015. Bayesian inference for stochastic individual-based models of ecological systems: a pest control simulation study. Frontiers in Environmental Science. 3, 42.","chicago":"Parise, Francesca, John Lygeros, and Jakob Ruess. “Bayesian Inference for Stochastic Individual-Based Models of Ecological Systems: A Pest Control Simulation Study.” <i>Frontiers in Environmental Science</i>. Frontiers, 2015. <a href=\"https://doi.org/10.3389/fenvs.2015.00042\">https://doi.org/10.3389/fenvs.2015.00042</a>.","short":"F. Parise, J. Lygeros, J. Ruess, Frontiers in Environmental Science 3 (2015)."},"publication_status":"published","abstract":[{"text":"Mathematical models are of fundamental importance in the understanding of complex population dynamics. For instance, they can be used to predict the population evolution starting from different initial conditions or to test how a system responds to external perturbations. For this analysis to be meaningful in real applications, however, it is of paramount importance to choose an appropriate model structure and to infer the model parameters from measured data. While many parameter inference methods are available for models based on deterministic ordinary differential equations, the same does not hold for more detailed individual-based models. Here we consider, in particular, stochastic models in which the time evolution of the species abundances is described by a continuous-time Markov chain. These models are governed by a master equation that is typically difficult to solve. Consequently, traditional inference methods that rely on iterative evaluation of parameter likelihoods are computationally intractable. The aim of this paper is to present recent advances in parameter inference for continuous-time Markov chain models, based on a moment closure approximation of the parameter likelihood, and to investigate how these results can help in understanding, and ultimately controlling, complex systems in ecology. Specifically, we illustrate through an agricultural pest case study how parameters of a stochastic individual-based model can be identified from measured data and how the resulting model can be used to solve an optimal control problem in a stochastic setting. In particular, we show how the matter of determining the optimal combination of two different pest control methods can be formulated as a chance constrained optimization problem where the control action is modeled as a state reset, leading to a hybrid system formulation.","lang":"eng"}],"project":[{"call_identifier":"FP7","_id":"25681D80-B435-11E9-9278-68D0E5697425","name":"International IST Postdoc Fellowship Programme","grant_number":"291734"}],"oa":1,"ddc":["000","570"],"_id":"10794","title":"Bayesian inference for stochastic individual-based models of ecological systems: a pest control simulation study","publication":"Frontiers in Environmental Science","publisher":"Frontiers","article_type":"original","file_date_updated":"2022-02-25T11:55:26Z","volume":3,"status":"public","article_number":"42","date_created":"2022-02-25T11:42:25Z","month":"06","intvolume":"         3","day":"10","type":"journal_article","date_updated":"2022-02-25T11:59:23Z","oa_version":"Published Version","article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","acknowledgement":"The authors would like to acknowledge contributions from Baptiste Mottet who performed preliminary analysis regarding parameter inference for the considered case study in a student project (Mottet, 2014/2015).\r\nThe research leading to these results has received funding from the People Programme (Marie Curie Actions) of the European Union's Seventh Framework Programme (FP7/2007-2013) under REA grant agreement No. [291734] and from SystemsX under the project SignalX.","language":[{"iso":"eng"}],"doi":"10.3389/fenvs.2015.00042","department":[{"_id":"ToHe"},{"_id":"GaTk"}],"has_accepted_license":"1","ec_funded":1,"date_published":"2015-06-10T00:00:00Z","file":[{"relation":"main_file","date_created":"2022-02-25T11:55:26Z","file_size":1371201,"content_type":"application/pdf","creator":"dernst","success":1,"date_updated":"2022-02-25T11:55:26Z","file_id":"10795","checksum":"26c222487564e1be02a11d688d6f769d","file_name":"2015_FrontiersEnvironmScience_Parise.pdf","access_level":"open_access"}],"keyword":["General Environmental Science"],"publication_identifier":{"issn":["2296-665X"]},"scopus_import":"1"}]