[{"ddc":["005"],"page":"433 - 444","quality_controlled":"1","publisher":"ACM","doi":"10.1145/2676726.2677008","type":"conference","_id":"1992","date_updated":"2021-01-12T06:54:33Z","status":"public","date_published":"2015-01-15T00:00:00Z","conference":{"name":"POPL: Principles of Programming Languages","end_date":"2015-01-17","start_date":"2015-01-15","location":"Mumbai, India"},"year":"2015","publist_id":"5091","abstract":[{"text":"We present a method and a tool for generating succinct representations of sets of concurrent traces. We focus on trace sets that contain all correct or all incorrect permutations of events from a given trace. We represent trace sets as HB-Formulas that are Boolean combinations of happens-before constraints between events. To generate a representation of incorrect interleavings, our method iteratively explores interleavings that violate the specification and gathers generalizations of the discovered interleavings into an HB-Formula; its complement yields a representation of correct interleavings.\r\n\r\nWe claim that our trace set representations can drive diverse verification, fault localization, repair, and synthesis techniques for concurrent programs. We demonstrate this by using our tool in three case studies involving synchronization synthesis, bug summarization, and abstraction refinement based verification. In each case study, our initial experimental results have been promising.\r\n\r\nIn the first case study, we present an algorithm for inferring missing synchronization from an HB-Formula representing correct interleavings of a given trace. The algorithm applies rules to rewrite specific patterns in the HB-Formula into locks, barriers, and wait-notify constructs. In the second case study, we use an HB-Formula representing incorrect interleavings for bug summarization. While the HB-Formula itself is a concise counterexample summary, we present additional inference rules to help identify specific concurrency bugs such as data races, define-use order violations, and two-stage access bugs. In the final case study, we present a novel predicate learning procedure that uses HB-Formulas representing abstract counterexamples to accelerate counterexample-guided abstraction refinement (CEGAR). In each iteration of the CEGAR loop, the procedure refines the abstraction to eliminate multiple spurious abstract counterexamples drawn from the HB-Formula.","lang":"eng"}],"has_accepted_license":"1","file_date_updated":"2020-07-14T12:45:22Z","publication_status":"published","publication_identifier":{"isbn":["978-1-4503-3300-9"]},"title":"Succinct representation of concurrent trace sets","oa_version":"Submitted Version","day":"15","scopus_import":1,"author":[{"last_name":"Gupta","id":"335E5684-F248-11E8-B48F-1D18A9856A87","full_name":"Gupta, Ashutosh","first_name":"Ashutosh"},{"last_name":"Henzinger","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","full_name":"Henzinger, Thomas A","orcid":"0000−0002−2985−7724","first_name":"Thomas A"},{"id":"3B51CAC4-F248-11E8-B48F-1D18A9856A87","full_name":"Radhakrishna, Arjun","last_name":"Radhakrishna","first_name":"Arjun"},{"first_name":"Roopsha","id":"3D2AAC08-F248-11E8-B48F-1D18A9856A87","full_name":"Samanta, Roopsha","last_name":"Samanta"},{"orcid":"0000-0003-4409-8487","first_name":"Thorsten","id":"3D6E8F2C-F248-11E8-B48F-1D18A9856A87","full_name":"Tarrach, Thorsten","last_name":"Tarrach"}],"date_created":"2018-12-11T11:55:05Z","pubrep_id":"317","language":[{"iso":"eng"}],"oa":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"short":"A. Gupta, T.A. Henzinger, A. Radhakrishna, R. Samanta, T. Tarrach, in:, ACM, 2015, pp. 433–444.","ieee":"A. Gupta, T. A. Henzinger, A. Radhakrishna, R. Samanta, and T. Tarrach, “Succinct representation of concurrent trace sets,” presented at the POPL: Principles of Programming Languages, Mumbai, India, 2015, pp. 433–444.","ama":"Gupta A, Henzinger TA, Radhakrishna A, Samanta R, Tarrach T. Succinct representation of concurrent trace sets. In: ACM; 2015:433-444. doi:<a href=\"https://doi.org/10.1145/2676726.2677008\">10.1145/2676726.2677008</a>","mla":"Gupta, Ashutosh, et al. <i>Succinct Representation of Concurrent Trace Sets</i>. ACM, 2015, pp. 433–44, doi:<a href=\"https://doi.org/10.1145/2676726.2677008\">10.1145/2676726.2677008</a>.","apa":"Gupta, A., Henzinger, T. A., Radhakrishna, A., Samanta, R., &#38; Tarrach, T. (2015). Succinct representation of concurrent trace sets (pp. 433–444). Presented at the POPL: Principles of Programming Languages, Mumbai, India: ACM. <a href=\"https://doi.org/10.1145/2676726.2677008\">https://doi.org/10.1145/2676726.2677008</a>","chicago":"Gupta, Ashutosh, Thomas A Henzinger, Arjun Radhakrishna, Roopsha Samanta, and Thorsten Tarrach. “Succinct Representation of Concurrent Trace Sets,” 433–44. ACM, 2015. <a href=\"https://doi.org/10.1145/2676726.2677008\">https://doi.org/10.1145/2676726.2677008</a>.","ista":"Gupta A, Henzinger TA, Radhakrishna A, Samanta R, Tarrach T. 2015. Succinct representation of concurrent trace sets. POPL: Principles of Programming Languages, 433–444."},"month":"01","file":[{"creator":"system","date_updated":"2020-07-14T12:45:22Z","date_created":"2018-12-12T10:17:56Z","file_size":399462,"file_id":"5314","content_type":"application/pdf","access_level":"open_access","file_name":"IST-2015-317-v1+1_author_version.pdf","checksum":"f0d4395b600f410a191256ac0b73af32","relation":"main_file"}],"department":[{"_id":"ToHe"}]},{"quality_controlled":"1","main_file_link":[{"open_access":"1","url":"http://www.ncbi.nlm.nih.gov/pmc/articles/PMC4286035/"}],"publisher":"The Royal Society","article_processing_charge":"No","doi":"10.1098/rspb.2014.1976","type":"journal_article","_id":"1993","date_updated":"2023-02-23T14:06:41Z","status":"public","publication":"Proceedings of the Royal Society of London Series B Biological Sciences","project":[{"_id":"25DC711C-B435-11E9-9278-68D0E5697425","name":"Social Vaccination in Ant Colonies: from Individual Mechanisms to Society Effects","grant_number":"243071","call_identifier":"FP7"},{"_id":"25DAF0B2-B435-11E9-9278-68D0E5697425","name":"Host-Parasite Coevolution","grant_number":"CR-118/3-1"}],"acknowledgement":"Funding was obtained by the German Research Foundation (CR 118–2) and an ERC StG (243071) by the European Research Council (both to S.C.).\r\nWe thank Line V. Ugelvig for help with ant collection and statistical discussion, Xavier Espadaler for detailed information on the ant collection site, Birgit Lautenschläger for the electron microscopy images and Eva Sixt for ant drawings. We further thank Jørgen Eilenberg for the fungal strain, Meghan L. Vyleta for genetic strain characterization and immune gene primer development, Paul Schmid-Hempel for discussion, and Line V. Ugelvig, Xavier Espadaler and Christopher D. Pull for comments on the manuscript. S.C., M.K. and S.T. conceived the study; M.K. and A.V.G. performed the experiments; M.K. performed the statistical analysis; S.C. and M.K. wrote the manuscript with intense contributions of A.V.G. and S.T.; all authors approved the manuscript.","date_published":"2015-01-22T00:00:00Z","ec_funded":1,"pmid":1,"related_material":{"record":[{"status":"public","relation":"research_data","id":"9740"}]},"external_id":{"pmid":["25473011"]},"year":"2015","publist_id":"5090","acknowledged_ssus":[{"_id":"EM-Fac"}],"intvolume":"       282","abstract":[{"text":"The fitness effects of symbionts on their hosts can be context-dependent, with usually benign symbionts causing detrimental effects when their hosts are stressed, or typically parasitic symbionts providing protection towards their hosts (e.g. against pathogen infection). Here, we studied the novel association between the invasive garden ant Lasius neglectus and its fungal ectosymbiont Laboulbenia formicarum for potential costs and benefits. We tested ants with different Laboulbenia levels for their survival and immunity under resource limitation and exposure to the obligate killing entomopathogen Metarhizium brunneum. While survival of L. neglectus workers under starvation was significantly decreased with increasing Laboulbenia levels, host survival under Metarhizium exposure increased with higher levels of the ectosymbiont, suggesting a symbiont-mediated anti-pathogen protection, which seems to be driven mechanistically by both improved sanitary behaviours and an upregulated immune system. Ants with high Laboulbenia levels showed significantly longer self-grooming and elevated expression of immune genes relevant for wound repair and antifungal responses (β-1,3-glucan binding protein, Prophenoloxidase), compared with ants carrying low Laboulbenia levels. This suggests that the ectosymbiont Laboulbenia formicarum weakens its ant host by either direct resource exploitation or the costs of an upregulated behavioural and immunological response, which, however, provides a prophylactic protection upon later exposure to pathogens. ","lang":"eng"}],"publication_status":"published","publication_identifier":{"issn":["0962-8452"],"eissn":["1471-2954"]},"oa_version":"Submitted Version","title":"Anti-pathogen protection versus survival costs mediated by an ectosymbiont in an ant host","day":"22","scopus_import":"1","author":[{"full_name":"Konrad, Matthias","id":"46528076-F248-11E8-B48F-1D18A9856A87","last_name":"Konrad","first_name":"Matthias"},{"first_name":"Anna V","last_name":"Grasse","id":"406F989C-F248-11E8-B48F-1D18A9856A87","full_name":"Grasse, Anna V"},{"first_name":"Simon","id":"35A7A418-F248-11E8-B48F-1D18A9856A87","full_name":"Tragust, Simon","last_name":"Tragust"},{"orcid":"0000-0002-2193-3868","first_name":"Sylvia","last_name":"Cremer","id":"2F64EC8C-F248-11E8-B48F-1D18A9856A87","full_name":"Cremer, Sylvia"}],"date_created":"2018-12-11T11:55:06Z","article_type":"original","volume":282,"language":[{"iso":"eng"}],"oa":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"ama":"Konrad M, Grasse AV, Tragust S, Cremer S. Anti-pathogen protection versus survival costs mediated by an ectosymbiont in an ant host. <i>Proceedings of the Royal Society of London Series B Biological Sciences</i>. 2015;282(1799). doi:<a href=\"https://doi.org/10.1098/rspb.2014.1976\">10.1098/rspb.2014.1976</a>","ieee":"M. Konrad, A. V. Grasse, S. Tragust, and S. Cremer, “Anti-pathogen protection versus survival costs mediated by an ectosymbiont in an ant host,” <i>Proceedings of the Royal Society of London Series B Biological Sciences</i>, vol. 282, no. 1799. The Royal Society, 2015.","short":"M. Konrad, A.V. Grasse, S. Tragust, S. Cremer, Proceedings of the Royal Society of London Series B Biological Sciences 282 (2015).","chicago":"Konrad, Matthias, Anna V Grasse, Simon Tragust, and Sylvia Cremer. “Anti-Pathogen Protection versus Survival Costs Mediated by an Ectosymbiont in an Ant Host.” <i>Proceedings of the Royal Society of London Series B Biological Sciences</i>. The Royal Society, 2015. <a href=\"https://doi.org/10.1098/rspb.2014.1976\">https://doi.org/10.1098/rspb.2014.1976</a>.","ista":"Konrad M, Grasse AV, Tragust S, Cremer S. 2015. Anti-pathogen protection versus survival costs mediated by an ectosymbiont in an ant host. Proceedings of the Royal Society of London Series B Biological Sciences. 282(1799), 20141976.","apa":"Konrad, M., Grasse, A. V., Tragust, S., &#38; Cremer, S. (2015). Anti-pathogen protection versus survival costs mediated by an ectosymbiont in an ant host. <i>Proceedings of the Royal Society of London Series B Biological Sciences</i>. The Royal Society. <a href=\"https://doi.org/10.1098/rspb.2014.1976\">https://doi.org/10.1098/rspb.2014.1976</a>","mla":"Konrad, Matthias, et al. “Anti-Pathogen Protection versus Survival Costs Mediated by an Ectosymbiont in an Ant Host.” <i>Proceedings of the Royal Society of London Series B Biological Sciences</i>, vol. 282, no. 1799, 20141976, The Royal Society, 2015, doi:<a href=\"https://doi.org/10.1098/rspb.2014.1976\">10.1098/rspb.2014.1976</a>."},"issue":"1799","month":"01","article_number":"20141976","department":[{"_id":"SyCr"}]},{"main_file_link":[{"url":"http://arxiv.org/abs/1207.0077","open_access":"1"}],"publication_status":"published","quality_controlled":"1","page":"285 - 296","abstract":[{"text":"We prove that the three-state toric homogeneous Markov chain model has Markov degree two. In algebraic terminology this means, that a certain class of toric ideals is generated by quadratic binomials. This was conjectured by Haws, Martin del Campo, Takemura and Yoshida, who proved that they are generated by degree six binomials.","lang":"eng"}],"date_updated":"2021-01-12T06:54:35Z","_id":"1997","volume":"68/Part 2","type":"journal_article","date_created":"2018-12-11T11:55:07Z","author":[{"first_name":"Patrik","last_name":"Noren","full_name":"Noren, Patrik","id":"46870C74-F248-11E8-B48F-1D18A9856A87"}],"doi":"10.1016/j.jsc.2014.09.014","scopus_import":1,"day":"01","oa_version":"Preprint","title":"The three-state toric homogeneous Markov chain model has Markov degree two","publisher":"Elsevier","issue":"May-June","citation":{"short":"P. Noren, Journal of Symbolic Computation 68/Part 2 (2015) 285–296.","ieee":"P. Noren, “The three-state toric homogeneous Markov chain model has Markov degree two,” <i>Journal of Symbolic Computation</i>, vol. 68/Part 2, no. May-June. Elsevier, pp. 285–296, 2015.","ama":"Noren P. The three-state toric homogeneous Markov chain model has Markov degree two. <i>Journal of Symbolic Computation</i>. 2015;68/Part 2(May-June):285-296. doi:<a href=\"https://doi.org/10.1016/j.jsc.2014.09.014\">10.1016/j.jsc.2014.09.014</a>","mla":"Noren, Patrik. “The Three-State Toric Homogeneous Markov Chain Model Has Markov Degree Two.” <i>Journal of Symbolic Computation</i>, vol. 68/Part 2, no. May-June, Elsevier, 2015, pp. 285–96, doi:<a href=\"https://doi.org/10.1016/j.jsc.2014.09.014\">10.1016/j.jsc.2014.09.014</a>.","apa":"Noren, P. (2015). The three-state toric homogeneous Markov chain model has Markov degree two. <i>Journal of Symbolic Computation</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.jsc.2014.09.014\">https://doi.org/10.1016/j.jsc.2014.09.014</a>","chicago":"Noren, Patrik. “The Three-State Toric Homogeneous Markov Chain Model Has Markov Degree Two.” <i>Journal of Symbolic Computation</i>. Elsevier, 2015. <a href=\"https://doi.org/10.1016/j.jsc.2014.09.014\">https://doi.org/10.1016/j.jsc.2014.09.014</a>.","ista":"Noren P. 2015. The three-state toric homogeneous Markov chain model has Markov degree two. Journal of Symbolic Computation. 68/Part 2(May-June), 285–296."},"date_published":"2015-05-01T00:00:00Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"publication":"Journal of Symbolic Computation","status":"public","language":[{"iso":"eng"}],"department":[{"_id":"CaUh"}],"publist_id":"5082","year":"2015","month":"05"},{"type":"journal_article","date_updated":"2021-01-12T06:54:40Z","_id":"2006","publisher":"Taylor & Francis","doi":"10.1080/10586458.2014.980044","article_processing_charge":"No","quality_controlled":"1","main_file_link":[{"url":"http://arxiv.org/abs/1109.3436","open_access":"1"}],"page":"261 - 269","publist_id":"5070","year":"2015","date_published":"2015-06-23T00:00:00Z","publication":"Experimental Mathematics","status":"public","date_created":"2018-12-11T11:55:10Z","volume":24,"title":"The monotone secant conjecture in the real Schubert calculus","oa_version":"Preprint","author":[{"last_name":"Hein","full_name":"Hein, Nicolas","first_name":"Nicolas"},{"first_name":"Christopher","full_name":"Hillar, Christopher","last_name":"Hillar"},{"first_name":"Abraham","last_name":"Martin Del Campo Sanchez","id":"4CF47F6A-F248-11E8-B48F-1D18A9856A87","full_name":"Martin Del Campo Sanchez, Abraham"},{"full_name":"Sottile, Frank","last_name":"Sottile","first_name":"Frank"},{"last_name":"Teitler","full_name":"Teitler, Zach","first_name":"Zach"}],"day":"23","scopus_import":1,"publication_status":"published","abstract":[{"text":"The monotone secant conjecture posits a rich class of polynomial systems, all of whose solutions are real. These systems come from the Schubert calculus on flag manifolds, and the monotone secant conjecture is a compelling generalization of the Shapiro conjecture for Grassmannians (Theorem of Mukhin, Tarasov, and Varchenko). We present some theoretical evidence for this conjecture, as well as computational evidence obtained by 1.9 teraHertz-years of computing, and we discuss some of the phenomena we observed in our data. ","lang":"eng"}],"intvolume":"        24","department":[{"_id":"CaUh"}],"month":"06","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","issue":"3","citation":{"short":"N. Hein, C. Hillar, A. Martin del Campo Sanchez, F. Sottile, Z. Teitler, Experimental Mathematics 24 (2015) 261–269.","ieee":"N. Hein, C. Hillar, A. Martin del Campo Sanchez, F. Sottile, and Z. Teitler, “The monotone secant conjecture in the real Schubert calculus,” <i>Experimental Mathematics</i>, vol. 24, no. 3. Taylor &#38; Francis, pp. 261–269, 2015.","ama":"Hein N, Hillar C, Martin del Campo Sanchez A, Sottile F, Teitler Z. The monotone secant conjecture in the real Schubert calculus. <i>Experimental Mathematics</i>. 2015;24(3):261-269. doi:<a href=\"https://doi.org/10.1080/10586458.2014.980044\">10.1080/10586458.2014.980044</a>","mla":"Hein, Nicolas, et al. “The Monotone Secant Conjecture in the Real Schubert Calculus.” <i>Experimental Mathematics</i>, vol. 24, no. 3, Taylor &#38; Francis, 2015, pp. 261–69, doi:<a href=\"https://doi.org/10.1080/10586458.2014.980044\">10.1080/10586458.2014.980044</a>.","apa":"Hein, N., Hillar, C., Martin del Campo Sanchez, A., Sottile, F., &#38; Teitler, Z. (2015). The monotone secant conjecture in the real Schubert calculus. <i>Experimental Mathematics</i>. Taylor &#38; Francis. <a href=\"https://doi.org/10.1080/10586458.2014.980044\">https://doi.org/10.1080/10586458.2014.980044</a>","chicago":"Hein, Nicolas, Christopher Hillar, Abraham Martin del Campo Sanchez, Frank Sottile, and Zach Teitler. “The Monotone Secant Conjecture in the Real Schubert Calculus.” <i>Experimental Mathematics</i>. Taylor &#38; Francis, 2015. <a href=\"https://doi.org/10.1080/10586458.2014.980044\">https://doi.org/10.1080/10586458.2014.980044</a>.","ista":"Hein N, Hillar C, Martin del Campo Sanchez A, Sottile F, Teitler Z. 2015. The monotone secant conjecture in the real Schubert calculus. Experimental Mathematics. 24(3), 261–269."},"language":[{"iso":"eng"}],"oa":1},{"year":"2015","publist_id":"5068","publication":"Scandinavian Journal of Statistics","status":"public","date_published":"2015-09-01T00:00:00Z","acknowledgement":"Part of the material presented here was contained in the PhD thesis of the first author to which the second author and Thomas Richardson were advisers. The authors wish to thank him for several comments and suggestions. We also thank the reviewers and the Associate Editor for helpful comments. The proof of Proposition 1 uses the idea of Olga Klimova, to whom the authors are also indebted. The second author was supported in part by Grant K-106154 from the Hungarian National Scientific Research Fund (OTKA).","publisher":"Wiley","doi":"10.1111/sjos.12139","type":"journal_article","_id":"2008","date_updated":"2021-01-12T06:54:41Z","page":"832 - 847","quality_controlled":"1","main_file_link":[{"url":"http://arxiv.org/abs/1307.3282","open_access":"1"}],"month":"09","department":[{"_id":"CaUh"}],"language":[{"iso":"eng"}],"oa":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"ama":"Klimova A, Rudas T. Iterative scaling in curved exponential families. <i>Scandinavian Journal of Statistics</i>. 2015;42(3):832-847. doi:<a href=\"https://doi.org/10.1111/sjos.12139\">10.1111/sjos.12139</a>","short":"A. Klimova, T. Rudas, Scandinavian Journal of Statistics 42 (2015) 832–847.","ieee":"A. Klimova and T. Rudas, “Iterative scaling in curved exponential families,” <i>Scandinavian Journal of Statistics</i>, vol. 42, no. 3. Wiley, pp. 832–847, 2015.","ista":"Klimova A, Rudas T. 2015. Iterative scaling in curved exponential families. Scandinavian Journal of Statistics. 42(3), 832–847.","chicago":"Klimova, Anna, and Tamás Rudas. “Iterative Scaling in Curved Exponential Families.” <i>Scandinavian Journal of Statistics</i>. Wiley, 2015. <a href=\"https://doi.org/10.1111/sjos.12139\">https://doi.org/10.1111/sjos.12139</a>.","mla":"Klimova, Anna, and Tamás Rudas. “Iterative Scaling in Curved Exponential Families.” <i>Scandinavian Journal of Statistics</i>, vol. 42, no. 3, Wiley, 2015, pp. 832–47, doi:<a href=\"https://doi.org/10.1111/sjos.12139\">10.1111/sjos.12139</a>.","apa":"Klimova, A., &#38; Rudas, T. (2015). Iterative scaling in curved exponential families. <i>Scandinavian Journal of Statistics</i>. Wiley. <a href=\"https://doi.org/10.1111/sjos.12139\">https://doi.org/10.1111/sjos.12139</a>"},"issue":"3","oa_version":"Preprint","title":"Iterative scaling in curved exponential families","scopus_import":1,"day":"01","author":[{"first_name":"Anna","id":"31934120-F248-11E8-B48F-1D18A9856A87","full_name":"Klimova, Anna","last_name":"Klimova"},{"first_name":"Tamás","full_name":"Rudas, Tamás","last_name":"Rudas"}],"date_created":"2018-12-11T11:55:11Z","volume":42,"intvolume":"        42","abstract":[{"text":"The paper describes a generalized iterative proportional fitting procedure that can be used for maximum likelihood estimation in a special class of the general log-linear model. The models in this class, called relational, apply to multivariate discrete sample spaces that do not necessarily have a Cartesian product structure and may not contain an overall effect. When applied to the cell probabilities, the models without the overall effect are curved exponential families and the values of the sufficient statistics are reproduced by the MLE only up to a constant of proportionality. The paper shows that Iterative Proportional Fitting, Generalized Iterative Scaling, and Improved Iterative Scaling fail to work for such models. The algorithm proposed here is based on iterated Bregman projections. As a by-product, estimates of the multiplicative parameters are also obtained. An implementation of the algorithm is available as an R-package.","lang":"eng"}],"publication_status":"published"},{"doi":"10.1016/j.csda.2015.01.017","author":[{"first_name":"Anna","id":"31934120-F248-11E8-B48F-1D18A9856A87","full_name":"Klimova, Anna","last_name":"Klimova"},{"last_name":"Uhler","full_name":"Uhler, Caroline","id":"49ADD78E-F248-11E8-B48F-1D18A9856A87","first_name":"Caroline","orcid":"0000-0002-7008-0216"},{"first_name":"Tamás","full_name":"Rudas, Tamás","last_name":"Rudas"}],"day":"01","scopus_import":1,"publisher":"Elsevier","oa_version":"Preprint","title":"Faithfulness and learning hypergraphs from discrete distributions","date_updated":"2021-01-12T06:54:43Z","_id":"2014","volume":87,"type":"journal_article","date_created":"2018-12-11T11:55:13Z","page":"57 - 72","abstract":[{"text":"The concepts of faithfulness and strong-faithfulness are important for statistical learning of graphical models. Graphs are not sufficient for describing the association structure of a discrete distribution. Hypergraphs representing hierarchical log-linear models are considered instead, and the concept of parametric (strong-) faithfulness with respect to a hypergraph is introduced. Strong-faithfulness ensures the existence of uniformly consistent parameter estimators and enables building uniformly consistent procedures for a hypergraph search. The strength of association in a discrete distribution can be quantified with various measures, leading to different concepts of strong-faithfulness. Lower and upper bounds for the proportions of distributions that do not satisfy strong-faithfulness are computed for different parameterizations and measures of association.","lang":"eng"}],"intvolume":"        87","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1404.6617"}],"publication_status":"published","quality_controlled":"1","year":"2015","month":"07","department":[{"_id":"CaUh"}],"publist_id":"5062","oa":1,"status":"public","publication":"Computational Statistics & Data Analysis","language":[{"iso":"eng"}],"issue":"7","citation":{"mla":"Klimova, Anna, et al. “Faithfulness and Learning Hypergraphs from Discrete Distributions.” <i>Computational Statistics &#38; Data Analysis</i>, vol. 87, no. 7, Elsevier, 2015, pp. 57–72, doi:<a href=\"https://doi.org/10.1016/j.csda.2015.01.017\">10.1016/j.csda.2015.01.017</a>.","apa":"Klimova, A., Uhler, C., &#38; Rudas, T. (2015). Faithfulness and learning hypergraphs from discrete distributions. <i>Computational Statistics &#38; Data Analysis</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.csda.2015.01.017\">https://doi.org/10.1016/j.csda.2015.01.017</a>","chicago":"Klimova, Anna, Caroline Uhler, and Tamás Rudas. “Faithfulness and Learning Hypergraphs from Discrete Distributions.” <i>Computational Statistics &#38; Data Analysis</i>. Elsevier, 2015. <a href=\"https://doi.org/10.1016/j.csda.2015.01.017\">https://doi.org/10.1016/j.csda.2015.01.017</a>.","ista":"Klimova A, Uhler C, Rudas T. 2015. Faithfulness and learning hypergraphs from discrete distributions. Computational Statistics &#38; Data Analysis. 87(7), 57–72.","short":"A. Klimova, C. Uhler, T. Rudas, Computational Statistics &#38; Data Analysis 87 (2015) 57–72.","ieee":"A. Klimova, C. Uhler, and T. Rudas, “Faithfulness and learning hypergraphs from discrete distributions,” <i>Computational Statistics &#38; Data Analysis</i>, vol. 87, no. 7. Elsevier, pp. 57–72, 2015.","ama":"Klimova A, Uhler C, Rudas T. Faithfulness and learning hypergraphs from discrete distributions. <i>Computational Statistics &#38; Data Analysis</i>. 2015;87(7):57-72. doi:<a href=\"https://doi.org/10.1016/j.csda.2015.01.017\">10.1016/j.csda.2015.01.017</a>"},"date_published":"2015-07-01T00:00:00Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87"},{"doi":"10.1016/j.bbamcr.2014.10.009","publisher":"Elsevier","date_updated":"2021-01-12T06:54:48Z","_id":"2025","type":"journal_article","page":"144 - 156","ddc":["570"],"quality_controlled":"1","year":"2015","publist_id":"5047","publication":"Biochimica et Biophysica Acta - Molecular Cell Research","status":"public","date_published":"2015-01-01T00:00:00Z","author":[{"first_name":"Daiki","last_name":"Kawada","full_name":"Kawada, Daiki"},{"first_name":"Hiromu","last_name":"Kobayashi","full_name":"Kobayashi, Hiromu"},{"first_name":"Tsuyoshi","full_name":"Tomita, Tsuyoshi","last_name":"Tomita"},{"last_name":"Nakata","full_name":"Nakata, Eisuke","first_name":"Eisuke"},{"first_name":"Makoto","full_name":"Nagano, Makoto","last_name":"Nagano"},{"first_name":"Daria E","orcid":"0000-0001-8323-8353","last_name":"Siekhaus","full_name":"Siekhaus, Daria E","id":"3D224B9E-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Toshima","full_name":"Toshima, Junko","first_name":"Junko"},{"first_name":"Jiro","last_name":"Toshimaa","full_name":"Toshimaa, Jiro"}],"scopus_import":1,"day":"01","oa_version":"Submitted Version","title":"The yeast Arf-GAP Glo3p is required for the endocytic recycling of cell surface proteins","volume":1853,"date_created":"2018-12-11T11:55:17Z","has_accepted_license":"1","license":"https://creativecommons.org/licenses/by-nc-nd/4.0/","abstract":[{"text":"Small GTP-binding proteins of the Ras superfamily play diverse roles in intracellular trafficking. Among them, the Rab, Arf, and Rho families function in successive steps of vesicle transport, in forming vesicles from donor membranes, directing vesicle trafficking toward target membranes and docking vesicles onto target membranes. These proteins act as molecular switches that are controlled by a cycle of GTP binding and hydrolysis regulated by guanine nucleotide exchange factors (GEFs) and GTPase-activating proteins (GAPs). In this study we explored the role of GAPs in the regulation of the endocytic pathway using fluorescently labeled yeast mating pheromone α-factor. Among 25 non-essential GAP mutants, we found that deletion of the GLO3 gene, encoding Arf-GAP protein, caused defective internalization of fluorescently labeled α-factor. Quantitative analysis revealed that glo3Δ cells show defective α-factor binding to the cell surface. Interestingly, Ste2p, the α-factor receptor, was mis-localized from the plasma membrane to the vacuole in glo3Δ cells. Domain deletion mutants of Glo3p revealed that a GAP-independent function, as well as the GAP activity, of Glo3p is important for both α-factor binding and Ste2p localization at the cell surface. Additionally, we found that deletion of the GLO3 gene affects the size and number of Arf1p-residing Golgi compartments and causes a defect in transport from the TGN to the plasma membrane. Furthermore, we demonstrated that glo3Δ cells were defective in the late endosome-to-TGN transport pathway, but not in the early endosome-to-TGN transport pathway. These findings suggest novel roles for Arf-GAP Glo3p in endocytic recycling of cell surface proteins.","lang":"eng"}],"tmp":{"image":"/images/cc_by_nc_nd.png","name":"Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0)","legal_code_url":"https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode","short":"CC BY-NC-ND (4.0)"},"intvolume":"      1853","publication_status":"published","file_date_updated":"2020-07-14T12:45:25Z","month":"01","department":[{"_id":"DaSi"}],"file":[{"file_id":"4936","file_size":926685,"date_created":"2018-12-12T10:12:18Z","creator":"system","date_updated":"2020-07-14T12:45:25Z","relation":"main_file","checksum":"5bb328edebb6a91337cadd7d63f961b7","file_name":"IST-2016-615-v1+1_BBAMCR.pdf","content_type":"application/pdf","access_level":"open_access"}],"oa":1,"pubrep_id":"615","language":[{"iso":"eng"}],"issue":"1","citation":{"ama":"Kawada D, Kobayashi H, Tomita T, et al. The yeast Arf-GAP Glo3p is required for the endocytic recycling of cell surface proteins. <i>Biochimica et Biophysica Acta - Molecular Cell Research</i>. 2015;1853(1):144-156. doi:<a href=\"https://doi.org/10.1016/j.bbamcr.2014.10.009\">10.1016/j.bbamcr.2014.10.009</a>","short":"D. Kawada, H. Kobayashi, T. Tomita, E. Nakata, M. Nagano, D.E. Siekhaus, J. Toshima, J. Toshimaa, Biochimica et Biophysica Acta - Molecular Cell Research 1853 (2015) 144–156.","ieee":"D. Kawada <i>et al.</i>, “The yeast Arf-GAP Glo3p is required for the endocytic recycling of cell surface proteins,” <i>Biochimica et Biophysica Acta - Molecular Cell Research</i>, vol. 1853, no. 1. Elsevier, pp. 144–156, 2015.","ista":"Kawada D, Kobayashi H, Tomita T, Nakata E, Nagano M, Siekhaus DE, Toshima J, Toshimaa J. 2015. The yeast Arf-GAP Glo3p is required for the endocytic recycling of cell surface proteins. Biochimica et Biophysica Acta - Molecular Cell Research. 1853(1), 144–156.","chicago":"Kawada, Daiki, Hiromu Kobayashi, Tsuyoshi Tomita, Eisuke Nakata, Makoto Nagano, Daria E Siekhaus, Junko Toshima, and Jiro Toshimaa. “The Yeast Arf-GAP Glo3p Is Required for the Endocytic Recycling of Cell Surface Proteins.” <i>Biochimica et Biophysica Acta - Molecular Cell Research</i>. Elsevier, 2015. <a href=\"https://doi.org/10.1016/j.bbamcr.2014.10.009\">https://doi.org/10.1016/j.bbamcr.2014.10.009</a>.","mla":"Kawada, Daiki, et al. “The Yeast Arf-GAP Glo3p Is Required for the Endocytic Recycling of Cell Surface Proteins.” <i>Biochimica et Biophysica Acta - Molecular Cell Research</i>, vol. 1853, no. 1, Elsevier, 2015, pp. 144–56, doi:<a href=\"https://doi.org/10.1016/j.bbamcr.2014.10.009\">10.1016/j.bbamcr.2014.10.009</a>.","apa":"Kawada, D., Kobayashi, H., Tomita, T., Nakata, E., Nagano, M., Siekhaus, D. E., … Toshimaa, J. (2015). The yeast Arf-GAP Glo3p is required for the endocytic recycling of cell surface proteins. <i>Biochimica et Biophysica Acta - Molecular Cell Research</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.bbamcr.2014.10.009\">https://doi.org/10.1016/j.bbamcr.2014.10.009</a>"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87"},{"type":"journal_article","date_created":"2018-12-11T11:55:18Z","date_updated":"2021-01-12T06:54:51Z","volume":106,"_id":"2030","oa_version":"Preprint","publisher":"Elsevier","title":"A hybrid MPI-OpenMP parallel implementation for pseudospectral simulations with application to Taylor-Couette flow","doi":"10.1016/j.compfluid.2014.09.021","author":[{"first_name":"Liang","full_name":"Shi, Liang","id":"374A3F1A-F248-11E8-B48F-1D18A9856A87","last_name":"Shi"},{"first_name":"Markus","last_name":"Rampp","full_name":"Rampp, Markus"},{"full_name":"Hof, Björn","id":"3A374330-F248-11E8-B48F-1D18A9856A87","last_name":"Hof","first_name":"Björn","orcid":"0000-0003-2057-2754"},{"first_name":"Marc","full_name":"Avila, Marc","last_name":"Avila"}],"scopus_import":1,"day":"01","quality_controlled":"1","publication_status":"published","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1311.2481"}],"abstract":[{"lang":"eng","text":"A hybrid-parallel direct-numerical-simulation method with application to turbulent Taylor-Couette flow is presented. The Navier-Stokes equations are discretized in cylindrical coordinates with the spectral Fourier-Galerkin method in the axial and azimuthal directions, and high-order finite differences in the radial direction. Time is advanced by a second-order, semi-implicit projection scheme, which requires the solution of five Helmholtz/Poisson equations, avoids staggered grids and renders very small slip velocities. Nonlinear terms are evaluated with the pseudospectral method. The code is parallelized using a hybrid MPI-OpenMP strategy, which, compared with a flat MPI parallelization, is simpler to implement, allows to reduce inter-node communications and MPI overhead that become relevant at high processor-core counts, and helps to contain the memory footprint. A strong scaling study shows that the hybrid code maintains scalability up to more than 20,000 processor cores and thus allows to perform simulations at higher resolutions than previously feasible. In particular, it opens up the possibility to simulate turbulent Taylor-Couette flows at Reynolds numbers up to O(105). This enables to probe hydrodynamic turbulence in Keplerian flows in experimentally relevant regimes."}],"intvolume":"       106","page":"1 - 11","publist_id":"5042","department":[{"_id":"BjHo"}],"month":"01","year":"2015","date_published":"2015-01-01T00:00:00Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","issue":"1","citation":{"ieee":"L. Shi, M. Rampp, B. Hof, and M. Avila, “A hybrid MPI-OpenMP parallel implementation for pseudospectral simulations with application to Taylor-Couette flow,” <i>Computers and Fluids</i>, vol. 106, no. 1. Elsevier, pp. 1–11, 2015.","short":"L. Shi, M. Rampp, B. Hof, M. Avila, Computers and Fluids 106 (2015) 1–11.","ama":"Shi L, Rampp M, Hof B, Avila M. A hybrid MPI-OpenMP parallel implementation for pseudospectral simulations with application to Taylor-Couette flow. <i>Computers and Fluids</i>. 2015;106(1):1-11. doi:<a href=\"https://doi.org/10.1016/j.compfluid.2014.09.021\">10.1016/j.compfluid.2014.09.021</a>","apa":"Shi, L., Rampp, M., Hof, B., &#38; Avila, M. (2015). A hybrid MPI-OpenMP parallel implementation for pseudospectral simulations with application to Taylor-Couette flow. <i>Computers and Fluids</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.compfluid.2014.09.021\">https://doi.org/10.1016/j.compfluid.2014.09.021</a>","mla":"Shi, Liang, et al. “A Hybrid MPI-OpenMP Parallel Implementation for Pseudospectral Simulations with Application to Taylor-Couette Flow.” <i>Computers and Fluids</i>, vol. 106, no. 1, Elsevier, 2015, pp. 1–11, doi:<a href=\"https://doi.org/10.1016/j.compfluid.2014.09.021\">10.1016/j.compfluid.2014.09.021</a>.","ista":"Shi L, Rampp M, Hof B, Avila M. 2015. A hybrid MPI-OpenMP parallel implementation for pseudospectral simulations with application to Taylor-Couette flow. Computers and Fluids. 106(1), 1–11.","chicago":"Shi, Liang, Markus Rampp, Björn Hof, and Marc Avila. “A Hybrid MPI-OpenMP Parallel Implementation for Pseudospectral Simulations with Application to Taylor-Couette Flow.” <i>Computers and Fluids</i>. Elsevier, 2015. <a href=\"https://doi.org/10.1016/j.compfluid.2014.09.021\">https://doi.org/10.1016/j.compfluid.2014.09.021</a>."},"publication":"Computers and Fluids","status":"public","language":[{"iso":"eng"}],"oa":1},{"project":[{"grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification","call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425"},{"call_identifier":"FWF","grant_number":"S11407","name":"Game Theory","_id":"25863FF4-B435-11E9-9278-68D0E5697425"},{"grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"publication":" Information Processing Letters","status":"public","ec_funded":1,"date_published":"2015-01-01T00:00:00Z","year":"2015","publist_id":"5025","page":"52 - 59","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1407.4225"}],"quality_controlled":"1","doi":"10.1016/j.ipl.2014.09.001","publisher":"Elsevier","date_updated":"2021-01-12T06:54:52Z","_id":"2034","type":"journal_article","oa":1,"language":[{"iso":"eng"}],"issue":"1","citation":{"ama":"Bérard B, Chatterjee K, Sznajder N. Probabilistic opacity for Markov decision processes. <i> Information Processing Letters</i>. 2015;115(1):52-59. doi:<a href=\"https://doi.org/10.1016/j.ipl.2014.09.001\">10.1016/j.ipl.2014.09.001</a>","ieee":"B. Bérard, K. Chatterjee, and N. Sznajder, “Probabilistic opacity for Markov decision processes,” <i> Information Processing Letters</i>, vol. 115, no. 1. Elsevier, pp. 52–59, 2015.","short":"B. Bérard, K. Chatterjee, N. Sznajder,  Information Processing Letters 115 (2015) 52–59.","chicago":"Bérard, Béatrice, Krishnendu Chatterjee, and Nathalie Sznajder. “Probabilistic Opacity for Markov Decision Processes.” <i> Information Processing Letters</i>. Elsevier, 2015. <a href=\"https://doi.org/10.1016/j.ipl.2014.09.001\">https://doi.org/10.1016/j.ipl.2014.09.001</a>.","ista":"Bérard B, Chatterjee K, Sznajder N. 2015. Probabilistic opacity for Markov decision processes.  Information Processing Letters. 115(1), 52–59.","apa":"Bérard, B., Chatterjee, K., &#38; Sznajder, N. (2015). Probabilistic opacity for Markov decision processes. <i> Information Processing Letters</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.ipl.2014.09.001\">https://doi.org/10.1016/j.ipl.2014.09.001</a>","mla":"Bérard, Béatrice, et al. “Probabilistic Opacity for Markov Decision Processes.” <i> Information Processing Letters</i>, vol. 115, no. 1, Elsevier, 2015, pp. 52–59, doi:<a href=\"https://doi.org/10.1016/j.ipl.2014.09.001\">10.1016/j.ipl.2014.09.001</a>."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","month":"01","department":[{"_id":"KrCh"}],"intvolume":"       115","abstract":[{"lang":"eng","text":"Opacity is a generic security property, that has been defined on (non-probabilistic) transition systems and later on Markov chains with labels. For a secret predicate, given as a subset of runs, and a function describing the view of an external observer, the value of interest for opacity is a measure of the set of runs disclosing the secret. We extend this definition to the richer framework of Markov decision processes, where non-deterministicchoice is combined with probabilistic transitions, and we study related decidability problems with partial or complete observation hypotheses for the schedulers. We prove that all questions are decidable with complete observation and ω-regular secrets. With partial observation, we prove that all quantitative questions are undecidable but the question whether a system is almost surely non-opaquebecomes decidable for a restricted class of ω-regular secrets, as well as for all ω-regular secrets under finite-memory schedulers."}],"publication_status":"published","author":[{"last_name":"Bérard","full_name":"Bérard, Béatrice","first_name":"Béatrice"},{"last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","first_name":"Krishnendu"},{"first_name":"Nathalie","full_name":"Sznajder, Nathalie","last_name":"Sznajder"}],"scopus_import":1,"day":"01","oa_version":"Preprint","title":"Probabilistic opacity for Markov decision processes","volume":115,"date_created":"2018-12-11T11:55:20Z"},{"quality_controlled":"1","page":"1213 - 1244","ddc":["000"],"date_updated":"2021-01-12T06:54:53Z","_id":"2035","type":"journal_article","doi":"10.1007/s10208-014-9223-y","publisher":"Springer","ec_funded":1,"acknowledgement":"This research is partially supported by the Toposys project FP7-ICT-318493-STREP, by ESF under the ACAT Research Network Programme, by the Russian Government under mega project 11.G34.31.0053, and by the Polish National Science Center under Grant No. N201 419639.","date_published":"2015-10-01T00:00:00Z","project":[{"call_identifier":"FP7","name":"Topological Complex Systems","grant_number":"318493","_id":"255D761E-B435-11E9-9278-68D0E5697425"}],"status":"public","publication":"Foundations of Computational Mathematics","publist_id":"5022","year":"2015","publication_status":"published","file_date_updated":"2020-07-14T12:45:26Z","has_accepted_license":"1","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)"},"abstract":[{"lang":"eng","text":"Considering a continuous self-map and the induced endomorphism on homology, we study the eigenvalues and eigenspaces of the latter. Taking a filtration of representations, we define the persistence of the eigenspaces, effectively introducing a hierarchical organization of the map. The algorithm that computes this information for a finite sample is proved to be stable, and to give the correct answer for a sufficiently dense sample. Results computed with an implementation of the algorithm provide evidence of its practical utility.\r\n"}],"intvolume":"        15","volume":15,"date_created":"2018-12-11T11:55:20Z","author":[{"last_name":"Edelsbrunner","full_name":"Edelsbrunner, Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","first_name":"Herbert","orcid":"0000-0002-9823-6833"},{"first_name":"Grzegorz","orcid":"0000-0002-3536-9866","last_name":"Jablonski","full_name":"Jablonski, Grzegorz","id":"4483EF78-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Mrozek, Marian","last_name":"Mrozek","first_name":"Marian"}],"scopus_import":1,"day":"01","oa_version":"Published Version","title":"The persistent homology of a self-map","issue":"5","citation":{"chicago":"Edelsbrunner, Herbert, Grzegorz Jablonski, and Marian Mrozek. “The Persistent Homology of a Self-Map.” <i>Foundations of Computational Mathematics</i>. Springer, 2015. <a href=\"https://doi.org/10.1007/s10208-014-9223-y\">https://doi.org/10.1007/s10208-014-9223-y</a>.","ista":"Edelsbrunner H, Jablonski G, Mrozek M. 2015. The persistent homology of a self-map. Foundations of Computational Mathematics. 15(5), 1213–1244.","apa":"Edelsbrunner, H., Jablonski, G., &#38; Mrozek, M. (2015). The persistent homology of a self-map. <i>Foundations of Computational Mathematics</i>. Springer. <a href=\"https://doi.org/10.1007/s10208-014-9223-y\">https://doi.org/10.1007/s10208-014-9223-y</a>","mla":"Edelsbrunner, Herbert, et al. “The Persistent Homology of a Self-Map.” <i>Foundations of Computational Mathematics</i>, vol. 15, no. 5, Springer, 2015, pp. 1213–44, doi:<a href=\"https://doi.org/10.1007/s10208-014-9223-y\">10.1007/s10208-014-9223-y</a>.","ama":"Edelsbrunner H, Jablonski G, Mrozek M. The persistent homology of a self-map. <i>Foundations of Computational Mathematics</i>. 2015;15(5):1213-1244. doi:<a href=\"https://doi.org/10.1007/s10208-014-9223-y\">10.1007/s10208-014-9223-y</a>","ieee":"H. Edelsbrunner, G. Jablonski, and M. Mrozek, “The persistent homology of a self-map,” <i>Foundations of Computational Mathematics</i>, vol. 15, no. 5. Springer, pp. 1213–1244, 2015.","short":"H. Edelsbrunner, G. Jablonski, M. Mrozek, Foundations of Computational Mathematics 15 (2015) 1213–1244."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"language":[{"iso":"eng"}],"pubrep_id":"486","department":[{"_id":"HeEd"}],"file":[{"file_name":"IST-2016-486-v1+1_s10208-014-9223-y.pdf","content_type":"application/pdf","access_level":"open_access","relation":"main_file","checksum":"3566f3a8b0c1bc550e62914a88c584ff","file_size":1317546,"date_created":"2018-12-12T10:08:10Z","date_updated":"2020-07-14T12:45:26Z","creator":"system","file_id":"4670"}],"month":"10"},{"main_file_link":[{"url":"http://arxiv.org/abs/1402.1153","open_access":"1"}],"publication_status":"published","quality_controlled":"1","page":"381 - 417","intvolume":"       215","abstract":[{"text":"We study the spectrum of a large system of N identical bosons interacting via a two-body potential with strength 1/N. In this mean-field regime, Bogoliubov's theory predicts that the spectrum of the N-particle Hamiltonian can be approximated by that of an effective quadratic Hamiltonian acting on Fock space, which describes the fluctuations around a condensed state. Recently, Bogoliubov's theory has been justified rigorously in the case that the low-energy eigenvectors of the N-particle Hamiltonian display complete condensation in the unique minimizer of the corresponding Hartree functional. In this paper, we shall justify Bogoliubov's theory for the high-energy part of the spectrum of the N-particle Hamiltonian corresponding to (non-linear) excited states of the Hartree functional. Moreover, we shall extend the existing results on the excitation spectrum to the case of non-uniqueness and/or degeneracy of the Hartree minimizer. In particular, the latter covers the case of rotating Bose gases, when the rotation speed is large enough to break the symmetry and to produce multiple quantized vortices in the Hartree minimizer. ","lang":"eng"}],"volume":215,"_id":"2085","date_updated":"2021-01-12T06:55:13Z","date_created":"2018-12-11T11:55:37Z","type":"journal_article","day":"01","scopus_import":1,"doi":"10.1007/s00205-014-0781-6","author":[{"first_name":"Phan","last_name":"Nam","id":"404092F4-F248-11E8-B48F-1D18A9856A87","full_name":"Nam, Phan"},{"orcid":"0000-0002-6781-0521","first_name":"Robert","last_name":"Seiringer","full_name":"Seiringer, Robert","id":"4AFD0470-F248-11E8-B48F-1D18A9856A87"}],"title":"Collective excitations of Bose gases in the mean-field regime","oa_version":"Preprint","publisher":"Springer","citation":{"mla":"Nam, Phan, and Robert Seiringer. “Collective Excitations of Bose Gases in the Mean-Field Regime.” <i>Archive for Rational Mechanics and Analysis</i>, vol. 215, no. 2, Springer, 2015, pp. 381–417, doi:<a href=\"https://doi.org/10.1007/s00205-014-0781-6\">10.1007/s00205-014-0781-6</a>.","apa":"Nam, P., &#38; Seiringer, R. (2015). Collective excitations of Bose gases in the mean-field regime. <i>Archive for Rational Mechanics and Analysis</i>. Springer. <a href=\"https://doi.org/10.1007/s00205-014-0781-6\">https://doi.org/10.1007/s00205-014-0781-6</a>","ista":"Nam P, Seiringer R. 2015. Collective excitations of Bose gases in the mean-field regime. Archive for Rational Mechanics and Analysis. 215(2), 381–417.","chicago":"Nam, Phan, and Robert Seiringer. “Collective Excitations of Bose Gases in the Mean-Field Regime.” <i>Archive for Rational Mechanics and Analysis</i>. Springer, 2015. <a href=\"https://doi.org/10.1007/s00205-014-0781-6\">https://doi.org/10.1007/s00205-014-0781-6</a>.","short":"P. Nam, R. Seiringer, Archive for Rational Mechanics and Analysis 215 (2015) 381–417.","ieee":"P. Nam and R. Seiringer, “Collective excitations of Bose gases in the mean-field regime,” <i>Archive for Rational Mechanics and Analysis</i>, vol. 215, no. 2. Springer, pp. 381–417, 2015.","ama":"Nam P, Seiringer R. Collective excitations of Bose gases in the mean-field regime. <i>Archive for Rational Mechanics and Analysis</i>. 2015;215(2):381-417. doi:<a href=\"https://doi.org/10.1007/s00205-014-0781-6\">10.1007/s00205-014-0781-6</a>"},"issue":"2","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_published":"2015-02-01T00:00:00Z","oa":1,"publication":"Archive for Rational Mechanics and Analysis","status":"public","language":[{"iso":"eng"}],"department":[{"_id":"RoSe"}],"publist_id":"4951","year":"2015","month":"02"},{"author":[{"last_name":"Erdös","full_name":"Erdös, László","id":"4DBD5372-F248-11E8-B48F-1D18A9856A87","first_name":"László","orcid":"0000-0001-5366-9603"},{"first_name":"Antti","full_name":"Knowles, Antti","last_name":"Knowles"}],"doi":"10.1007/s00220-014-2119-5","day":"01","scopus_import":1,"oa_version":"Preprint","title":"The Altshuler-Shklovskii formulas for random band matrices I: the unimodular case","publisher":"Springer","date_updated":"2021-01-12T06:55:43Z","_id":"2166","volume":333,"type":"journal_article","date_created":"2018-12-11T11:56:05Z","page":"1365 - 1416","abstract":[{"text":"We consider the spectral statistics of large random band matrices on mesoscopic energy scales. We show that the correlation function of the local eigenvalue density exhibits a universal power law behaviour that differs from the Wigner-Dyson- Mehta statistics. This law had been predicted in the physics literature by Altshuler and Shklovskii in (Zh Eksp Teor Fiz (Sov Phys JETP) 91(64):220(127), 1986); it describes the correlations of the eigenvalue density in general metallic sampleswith weak disorder. Our result rigorously establishes the Altshuler-Shklovskii formulas for band matrices. In two dimensions, where the leading term vanishes owing to an algebraic cancellation, we identify the first non-vanishing term and show that it differs substantially from the prediction of Kravtsov and Lerner in (Phys Rev Lett 74:2563-2566, 1995). The proof is given in the current paper and its companion (Ann. H. Poincaré. arXiv:1309.5107, 2014). ","lang":"eng"}],"intvolume":"       333","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1309.5106"}],"quality_controlled":"1","publication_status":"published","year":"2015","month":"02","department":[{"_id":"LaEr"}],"publist_id":"4818","oa":1,"publication":"Communications in Mathematical Physics","language":[{"iso":"eng"}],"status":"public","issue":"3","citation":{"mla":"Erdös, László, and Antti Knowles. “The Altshuler-Shklovskii Formulas for Random Band Matrices I: The Unimodular Case.” <i>Communications in Mathematical Physics</i>, vol. 333, no. 3, Springer, 2015, pp. 1365–416, doi:<a href=\"https://doi.org/10.1007/s00220-014-2119-5\">10.1007/s00220-014-2119-5</a>.","apa":"Erdös, L., &#38; Knowles, A. (2015). The Altshuler-Shklovskii formulas for random band matrices I: the unimodular case. <i>Communications in Mathematical Physics</i>. Springer. <a href=\"https://doi.org/10.1007/s00220-014-2119-5\">https://doi.org/10.1007/s00220-014-2119-5</a>","chicago":"Erdös, László, and Antti Knowles. “The Altshuler-Shklovskii Formulas for Random Band Matrices I: The Unimodular Case.” <i>Communications in Mathematical Physics</i>. Springer, 2015. <a href=\"https://doi.org/10.1007/s00220-014-2119-5\">https://doi.org/10.1007/s00220-014-2119-5</a>.","ista":"Erdös L, Knowles A. 2015. The Altshuler-Shklovskii formulas for random band matrices I: the unimodular case. Communications in Mathematical Physics. 333(3), 1365–1416.","short":"L. Erdös, A. Knowles, Communications in Mathematical Physics 333 (2015) 1365–1416.","ieee":"L. Erdös and A. Knowles, “The Altshuler-Shklovskii formulas for random band matrices I: the unimodular case,” <i>Communications in Mathematical Physics</i>, vol. 333, no. 3. Springer, pp. 1365–1416, 2015.","ama":"Erdös L, Knowles A. The Altshuler-Shklovskii formulas for random band matrices I: the unimodular case. <i>Communications in Mathematical Physics</i>. 2015;333(3):1365-1416. doi:<a href=\"https://doi.org/10.1007/s00220-014-2119-5\">10.1007/s00220-014-2119-5</a>"},"date_published":"2015-02-01T00:00:00Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87"},{"department":[{"_id":"VlKo"}],"month":"02","arxiv":1,"citation":{"ama":"Kolmogorov V, Thapper J, Živný S. The power of linear programming for general-valued CSPs. <i>SIAM Journal on Computing</i>. 2015;44(1):1-36. doi:<a href=\"https://doi.org/10.1137/130945648\">10.1137/130945648</a>","ieee":"V. Kolmogorov, J. Thapper, and S. Živný, “The power of linear programming for general-valued CSPs,” <i>SIAM Journal on Computing</i>, vol. 44, no. 1. SIAM, pp. 1–36, 2015.","short":"V. Kolmogorov, J. Thapper, S. Živný, SIAM Journal on Computing 44 (2015) 1–36.","ista":"Kolmogorov V, Thapper J, Živný S. 2015. The power of linear programming for general-valued CSPs. SIAM Journal on Computing. 44(1), 1–36.","chicago":"Kolmogorov, Vladimir, Johan Thapper, and Stanislav Živný. “The Power of Linear Programming for General-Valued CSPs.” <i>SIAM Journal on Computing</i>. SIAM, 2015. <a href=\"https://doi.org/10.1137/130945648\">https://doi.org/10.1137/130945648</a>.","apa":"Kolmogorov, V., Thapper, J., &#38; Živný, S. (2015). The power of linear programming for general-valued CSPs. <i>SIAM Journal on Computing</i>. SIAM. <a href=\"https://doi.org/10.1137/130945648\">https://doi.org/10.1137/130945648</a>","mla":"Kolmogorov, Vladimir, et al. “The Power of Linear Programming for General-Valued CSPs.” <i>SIAM Journal on Computing</i>, vol. 44, no. 1, SIAM, 2015, pp. 1–36, doi:<a href=\"https://doi.org/10.1137/130945648\">10.1137/130945648</a>."},"issue":"1","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","oa":1,"language":[{"iso":"eng"}],"volume":44,"date_created":"2018-12-11T11:56:41Z","scopus_import":1,"day":"01","author":[{"last_name":"Kolmogorov","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","full_name":"Kolmogorov, Vladimir","first_name":"Vladimir"},{"full_name":"Thapper, Johan","last_name":"Thapper","first_name":"Johan"},{"first_name":"Stanislav","full_name":"Živný, Stanislav","last_name":"Živný"}],"oa_version":"Preprint","title":"The power of linear programming for general-valued CSPs","publication_status":"published","abstract":[{"text":"A class of valued constraint satisfaction problems (VCSPs) is characterised by a valued constraint language, a fixed set of cost functions on a finite domain. Finite-valued constraint languages contain functions that take on rational costs and general-valued constraint languages contain functions that take on rational or infinite costs. An instance of the problem is specified by a sum of functions from the language with the goal to minimise the sum. This framework includes and generalises well-studied constraint satisfaction problems (CSPs) and maximum constraint satisfaction problems (Max-CSPs).\r\nOur main result is a precise algebraic characterisation of valued constraint languages whose instances can be solved exactly by the basic linear programming relaxation (BLP). For a general-valued constraint language Γ, BLP is a decision procedure for Γ if and only if Γ admits a symmetric fractional polymorphism of every arity. For a finite-valued constraint language Γ, BLP is a decision procedure if and only if Γ admits a symmetric fractional polymorphism of some arity, or equivalently, if Γ admits a symmetric fractional polymorphism of arity 2.\r\nUsing these results, we obtain tractability of several novel and previously widely-open classes of VCSPs, including problems over valued constraint languages that are: (1) submodular on arbitrary lattices; (2) bisubmodular (also known as k-submodular) on arbitrary finite domains; (3) weakly (and hence strongly) tree-submodular on arbitrary trees. ","lang":"eng"}],"intvolume":"        44","publist_id":"4673","year":"2015","related_material":{"record":[{"id":"2518","status":"public","relation":"earlier_version"}]},"external_id":{"arxiv":["1311.4219"]},"date_published":"2015-02-01T00:00:00Z","publication":"SIAM Journal on Computing","status":"public","_id":"2271","date_updated":"2023-02-23T10:46:30Z","type":"journal_article","doi":"10.1137/130945648","publisher":"SIAM","main_file_link":[{"url":"http://arxiv.org/abs/1311.4219","open_access":"1"}],"quality_controlled":"1","page":"1 - 36"},{"date_published":"2015-01-01T00:00:00Z","ec_funded":1,"status":"public","publication":"Journal de l'Ecole Polytechnique - Mathematiques","project":[{"_id":"25681D80-B435-11E9-9278-68D0E5697425","grant_number":"291734","name":"International IST Postdoc Fellowship Programme","call_identifier":"FP7"}],"publist_id":"7344","year":"2015","quality_controlled":"1","ddc":["539"],"page":"65 - 115","type":"journal_article","_id":"473","date_updated":"2021-01-12T08:00:52Z","publisher":"Ecole Polytechnique","doi":"10.5802/jep.18","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"ieee":"M. Lewin, P. Nam, and N. Rougerie, “Derivation of nonlinear gibbs measures from many-body quantum mechanics,” <i>Journal de l’Ecole Polytechnique - Mathematiques</i>, vol. 2. Ecole Polytechnique, pp. 65–115, 2015.","short":"M. Lewin, P. Nam, N. Rougerie, Journal de l’Ecole Polytechnique - Mathematiques 2 (2015) 65–115.","ama":"Lewin M, Nam P, Rougerie N. Derivation of nonlinear gibbs measures from many-body quantum mechanics. <i>Journal de l’Ecole Polytechnique - Mathematiques</i>. 2015;2:65-115. doi:<a href=\"https://doi.org/10.5802/jep.18\">10.5802/jep.18</a>","apa":"Lewin, M., Nam, P., &#38; Rougerie, N. (2015). Derivation of nonlinear gibbs measures from many-body quantum mechanics. <i>Journal de l’Ecole Polytechnique - Mathematiques</i>. Ecole Polytechnique. <a href=\"https://doi.org/10.5802/jep.18\">https://doi.org/10.5802/jep.18</a>","mla":"Lewin, Mathieu, et al. “Derivation of Nonlinear Gibbs Measures from Many-Body Quantum Mechanics.” <i>Journal de l’Ecole Polytechnique - Mathematiques</i>, vol. 2, Ecole Polytechnique, 2015, pp. 65–115, doi:<a href=\"https://doi.org/10.5802/jep.18\">10.5802/jep.18</a>.","ista":"Lewin M, Nam P, Rougerie N. 2015. Derivation of nonlinear gibbs measures from many-body quantum mechanics. Journal de l’Ecole Polytechnique - Mathematiques. 2, 65–115.","chicago":"Lewin, Mathieu, Phan Nam, and Nicolas Rougerie. “Derivation of Nonlinear Gibbs Measures from Many-Body Quantum Mechanics.” <i>Journal de l’Ecole Polytechnique - Mathematiques</i>. Ecole Polytechnique, 2015. <a href=\"https://doi.org/10.5802/jep.18\">https://doi.org/10.5802/jep.18</a>."},"language":[{"iso":"eng"}],"pubrep_id":"951","oa":1,"file":[{"date_created":"2018-12-12T10:12:53Z","file_size":1084254,"date_updated":"2020-07-14T12:46:35Z","creator":"system","file_id":"4974","file_name":"IST-2018-951-v1+1_2015_Thanh-Nam_Derivation_of.pdf","content_type":"application/pdf","access_level":"open_access","relation":"main_file","checksum":"a40eb4016717ddc9927154798a4c164a"}],"department":[{"_id":"RoSe"}],"month":"01","file_date_updated":"2020-07-14T12:46:35Z","publication_status":"published","license":"https://creativecommons.org/licenses/by-nd/4.0/","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by-nd/4.0/legalcode","name":"Creative Commons Attribution-NoDerivatives 4.0 International (CC BY-ND 4.0)","image":"/image/cc_by_nd.png","short":"CC BY-ND (4.0)"},"abstract":[{"lang":"eng","text":"We prove that nonlinear Gibbs measures can be obtained from the corresponding many-body, grand-canonical, quantum Gibbs states, in a mean-field limit where the temperature T diverges and the interaction strength behaves as 1/T. We proceed by characterizing the interacting Gibbs state as minimizing a functional counting the free-energy relatively to the non-interacting case. We then perform an infinite-dimensional analogue of phase-space semiclassical analysis, using fine properties of the quantum relative entropy, the link between quantum de Finetti measures and upper/lower symbols in a coherent state basis, as well as Berezin-Lieb type inequalities. Our results cover the measure built on the defocusing nonlinear Schrödinger functional on a finite interval, as well as smoother interactions in dimensions d 2."}],"intvolume":"         2","has_accepted_license":"1","date_created":"2018-12-11T11:46:40Z","volume":2,"title":"Derivation of nonlinear gibbs measures from many-body quantum mechanics","oa_version":"Published Version","day":"01","scopus_import":1,"author":[{"last_name":"Lewin","full_name":"Lewin, Mathieu","first_name":"Mathieu"},{"last_name":"Phan Thanh","full_name":"Phan Thanh, Nam","id":"404092F4-F248-11E8-B48F-1D18A9856A87","first_name":"Nam"},{"full_name":"Rougerie, Nicolas","last_name":"Rougerie","first_name":"Nicolas"}]},{"type":"journal_article","date_created":"2018-12-11T11:46:41Z","date_updated":"2021-01-12T08:00:54Z","_id":"477","volume":128,"publisher":"Company of Biologists","oa_version":"None","title":"The serotonin receptor 5-HT7R regulates the morphology and migratory properties of dendritic cells","doi":"10.1242/jcs.167999","author":[{"first_name":"Katrin","last_name":"Holst","full_name":"Holst, Katrin"},{"first_name":"Daria","last_name":"Guseva","full_name":"Guseva, Daria"},{"full_name":"Schindler, Susann","last_name":"Schindler","first_name":"Susann"},{"id":"41E9FBEA-F248-11E8-B48F-1D18A9856A87","full_name":"Sixt, Michael K","last_name":"Sixt","first_name":"Michael K","orcid":"0000-0002-6620-9179"},{"first_name":"Armin","last_name":"Braun","full_name":"Braun, Armin"},{"full_name":"Chopra, Himpriya","last_name":"Chopra","first_name":"Himpriya"},{"full_name":"Pabst, Oliver","last_name":"Pabst","first_name":"Oliver"},{"full_name":"Ponimaskin, Evgeni","last_name":"Ponimaskin","first_name":"Evgeni"}],"scopus_import":1,"day":"15","quality_controlled":"1","publication_status":"published","abstract":[{"lang":"eng","text":"Dendritic cells are potent antigen-presenting cells endowed with the unique ability to initiate adaptive immune responses upon inflammation. Inflammatory processes are often associated with an increased production of serotonin, which operates by activating specific receptors. However, the functional role of serotonin receptors in regulation of dendritic cell functions is poorly understood. Here, we demonstrate that expression of serotonin receptor 5-HT7 (5-HT7TR) as well as its downstream effector Cdc42 is upregulated in dendritic cells upon maturation. Although dendritic cell maturation was independent of 5-HT7TR, receptor stimulation affected dendritic cell morphology through Cdc42-mediated signaling. In addition, basal activity of 5-HT7TR was required for the proper expression of the chemokine receptor CCR7, which is a key factor that controls dendritic cell migration. Consistent with this, we observed that 5-HT7TR enhances chemotactic motility of dendritic cells in vitro by modulating their directionality and migration velocity. Accordingly, migration of dendritic cells in murine colon explants was abolished after pharmacological receptor inhibition. Our results indicate that there is a crucial role for 5-HT7TR-Cdc42-mediated signaling in the regulation of dendritic cell morphology and motility, suggesting that 5-HT7TR could be a new target for treatment of a variety of inflammatory and immune disorders."}],"intvolume":"       128","page":"2866 - 2880","publist_id":"7343","department":[{"_id":"MiSi"}],"month":"06","year":"2015","date_published":"2015-06-15T00:00:00Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","issue":"15","citation":{"ama":"Holst K, Guseva D, Schindler S, et al. The serotonin receptor 5-HT7R regulates the morphology and migratory properties of dendritic cells. <i>Journal of Cell Science</i>. 2015;128(15):2866-2880. doi:<a href=\"https://doi.org/10.1242/jcs.167999\">10.1242/jcs.167999</a>","ieee":"K. Holst <i>et al.</i>, “The serotonin receptor 5-HT7R regulates the morphology and migratory properties of dendritic cells,” <i>Journal of Cell Science</i>, vol. 128, no. 15. Company of Biologists, pp. 2866–2880, 2015.","short":"K. Holst, D. Guseva, S. Schindler, M.K. Sixt, A. Braun, H. Chopra, O. Pabst, E. Ponimaskin, Journal of Cell Science 128 (2015) 2866–2880.","chicago":"Holst, Katrin, Daria Guseva, Susann Schindler, Michael K Sixt, Armin Braun, Himpriya Chopra, Oliver Pabst, and Evgeni Ponimaskin. “The Serotonin Receptor 5-HT7R Regulates the Morphology and Migratory Properties of Dendritic Cells.” <i>Journal of Cell Science</i>. Company of Biologists, 2015. <a href=\"https://doi.org/10.1242/jcs.167999\">https://doi.org/10.1242/jcs.167999</a>.","ista":"Holst K, Guseva D, Schindler S, Sixt MK, Braun A, Chopra H, Pabst O, Ponimaskin E. 2015. The serotonin receptor 5-HT7R regulates the morphology and migratory properties of dendritic cells. Journal of Cell Science. 128(15), 2866–2880.","apa":"Holst, K., Guseva, D., Schindler, S., Sixt, M. K., Braun, A., Chopra, H., … Ponimaskin, E. (2015). The serotonin receptor 5-HT7R regulates the morphology and migratory properties of dendritic cells. <i>Journal of Cell Science</i>. Company of Biologists. <a href=\"https://doi.org/10.1242/jcs.167999\">https://doi.org/10.1242/jcs.167999</a>","mla":"Holst, Katrin, et al. “The Serotonin Receptor 5-HT7R Regulates the Morphology and Migratory Properties of Dendritic Cells.” <i>Journal of Cell Science</i>, vol. 128, no. 15, Company of Biologists, 2015, pp. 2866–80, doi:<a href=\"https://doi.org/10.1242/jcs.167999\">10.1242/jcs.167999</a>."},"status":"public","language":[{"iso":"eng"}],"publication":"Journal of Cell Science"},{"language":[{"iso":"eng"}],"oa":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","issue":"6","citation":{"ama":"Chatterjee K, Doyen L, Randour M, Raskin J. Looking at mean-payoff and total-payoff through windows. <i>Information and Computation</i>. 2015;242(6):25-52. doi:<a href=\"https://doi.org/10.1016/j.ic.2015.03.010\">10.1016/j.ic.2015.03.010</a>","ieee":"K. Chatterjee, L. Doyen, M. Randour, and J. Raskin, “Looking at mean-payoff and total-payoff through windows,” <i>Information and Computation</i>, vol. 242, no. 6. Elsevier, pp. 25–52, 2015.","short":"K. Chatterjee, L. Doyen, M. Randour, J. Raskin, Information and Computation 242 (2015) 25–52.","chicago":"Chatterjee, Krishnendu, Laurent Doyen, Mickael Randour, and Jean Raskin. “Looking at Mean-Payoff and Total-Payoff through Windows.” <i>Information and Computation</i>. Elsevier, 2015. <a href=\"https://doi.org/10.1016/j.ic.2015.03.010\">https://doi.org/10.1016/j.ic.2015.03.010</a>.","ista":"Chatterjee K, Doyen L, Randour M, Raskin J. 2015. Looking at mean-payoff and total-payoff through windows. Information and Computation. 242(6), 25–52.","apa":"Chatterjee, K., Doyen, L., Randour, M., &#38; Raskin, J. (2015). Looking at mean-payoff and total-payoff through windows. <i>Information and Computation</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.ic.2015.03.010\">https://doi.org/10.1016/j.ic.2015.03.010</a>","mla":"Chatterjee, Krishnendu, et al. “Looking at Mean-Payoff and Total-Payoff through Windows.” <i>Information and Computation</i>, vol. 242, no. 6, Elsevier, 2015, pp. 25–52, doi:<a href=\"https://doi.org/10.1016/j.ic.2015.03.010\">10.1016/j.ic.2015.03.010</a>."},"month":"03","department":[{"_id":"KrCh"}],"abstract":[{"text":"We consider two-player games played on weighted directed graphs with mean-payoff and total-payoff objectives, two classical quantitative objectives. While for single-dimensional games the complexity and memory bounds for both objectives coincide, we show that in contrast to multi-dimensional mean-payoff games that are known to be coNP-complete, multi-dimensional total-payoff games are undecidable. We introduce conservative approximations of these objectives, where the payoff is considered over a local finite window sliding along a play, instead of the whole play. For single dimension, we show that (i) if the window size is polynomial, deciding the winner takes polynomial time, and (ii) the existence of a bounded window can be decided in NP ∩ coNP, and is at least as hard as solving mean-payoff games. For multiple dimensions, we show that (i) the problem with fixed window size is EXPTIME-complete, and (ii) there is no primitive-recursive algorithm to decide the existence of a bounded window.","lang":"eng"}],"intvolume":"       242","publication_status":"published","title":"Looking at mean-payoff and total-payoff through windows","oa_version":"Preprint","author":[{"orcid":"0000-0002-4561-241X","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee"},{"full_name":"Doyen, Laurent","last_name":"Doyen","first_name":"Laurent"},{"first_name":"Mickael","full_name":"Randour, Mickael","last_name":"Randour"},{"last_name":"Raskin","full_name":"Raskin, Jean","first_name":"Jean"}],"scopus_import":1,"day":"24","date_created":"2018-12-11T11:46:57Z","volume":242,"project":[{"_id":"2584A770-B435-11E9-9278-68D0E5697425","name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23","call_identifier":"FWF"},{"call_identifier":"FWF","name":"Game Theory","grant_number":"S11407","_id":"25863FF4-B435-11E9-9278-68D0E5697425"},{"_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"}],"status":"public","publication":"Information and Computation","date_published":"2015-03-24T00:00:00Z","ec_funded":1,"related_material":{"record":[{"id":"2279","relation":"earlier_version","status":"public"}]},"year":"2015","publist_id":"7296","page":"25 - 52","quality_controlled":"1","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1302.4248"}],"publisher":"Elsevier","doi":"10.1016/j.ic.2015.03.010","type":"journal_article","date_updated":"2023-02-23T10:36:02Z","_id":"523"},{"abstract":[{"text":"We consider concurrent games played by two players on a finite-state graph, where in every round the players simultaneously choose a move, and the current state along with the joint moves determine the successor state. We study the most fundamental objective for concurrent games, namely, mean-payoff or limit-average objective, where a reward is associated to each transition, and the goal of player 1 is to maximize the long-run average of the rewards, and the objective of player 2 is strictly the opposite (i.e., the games are zero-sum). The path constraint for player 1 could be qualitative, i.e., the mean-payoff is the maximal reward, or arbitrarily close to it; or quantitative, i.e., a given threshold between the minimal and maximal reward. We consider the computation of the almost-sure (resp. positive) winning sets, where player 1 can ensure that the path constraint is satisfied with probability 1 (resp. positive probability). Almost-sure winning with qualitative constraint exactly corresponds to the question of whether there exists a strategy to ensure that the payoff is the maximal reward of the game. Our main results for qualitative path constraints are as follows: (1) we establish qualitative determinacy results that show that for every state either player 1 has a strategy to ensure almost-sure (resp. positive) winning against all player-2 strategies, or player 2 has a spoiling strategy to falsify almost-sure (resp. positive) winning against all player-1 strategies; (2) we present optimal strategy complexity results that precisely characterize the classes of strategies required for almost-sure and positive winning for both players; and (3) we present quadratic time algorithms to compute the almost-sure and the positive winning sets, matching the best known bound of the algorithms for much simpler problems (such as reachability objectives). For quantitative constraints we show that a polynomial time solution for the almost-sure or the positive winning set would imply a solution to a long-standing open problem (of solving the value problem of turn-based deterministic mean-payoff games) that is not known to be solvable in polynomial time.","lang":"eng"}],"intvolume":"       242","publication_status":"published","day":"11","scopus_import":1,"author":[{"orcid":"0000-0002-4561-241X","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee"},{"id":"3B699956-F248-11E8-B48F-1D18A9856A87","full_name":"Ibsen-Jensen, Rasmus","last_name":"Ibsen-Jensen","orcid":"0000-0003-4783-0389","first_name":"Rasmus"}],"title":"Qualitative analysis of concurrent mean payoff games","oa_version":"Preprint","volume":242,"date_created":"2018-12-11T11:46:57Z","oa":1,"language":[{"iso":"eng"}],"citation":{"short":"K. Chatterjee, R. Ibsen-Jensen, Information and Computation 242 (2015) 2–24.","ieee":"K. Chatterjee and R. Ibsen-Jensen, “Qualitative analysis of concurrent mean payoff games,” <i>Information and Computation</i>, vol. 242, no. 6. Elsevier, pp. 2–24, 2015.","ama":"Chatterjee K, Ibsen-Jensen R. Qualitative analysis of concurrent mean payoff games. <i>Information and Computation</i>. 2015;242(6):2-24. doi:<a href=\"https://doi.org/10.1016/j.ic.2015.03.009\">10.1016/j.ic.2015.03.009</a>","mla":"Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. “Qualitative Analysis of Concurrent Mean Payoff Games.” <i>Information and Computation</i>, vol. 242, no. 6, Elsevier, 2015, pp. 2–24, doi:<a href=\"https://doi.org/10.1016/j.ic.2015.03.009\">10.1016/j.ic.2015.03.009</a>.","apa":"Chatterjee, K., &#38; Ibsen-Jensen, R. (2015). Qualitative analysis of concurrent mean payoff games. <i>Information and Computation</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.ic.2015.03.009\">https://doi.org/10.1016/j.ic.2015.03.009</a>","ista":"Chatterjee K, Ibsen-Jensen R. 2015. Qualitative analysis of concurrent mean payoff games. Information and Computation. 242(6), 2–24.","chicago":"Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. “Qualitative Analysis of Concurrent Mean Payoff Games.” <i>Information and Computation</i>. Elsevier, 2015. <a href=\"https://doi.org/10.1016/j.ic.2015.03.009\">https://doi.org/10.1016/j.ic.2015.03.009</a>."},"issue":"6","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","month":"10","arxiv":1,"department":[{"_id":"KrCh"}],"page":"2 - 24","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1409.5306"}],"quality_controlled":"1","doi":"10.1016/j.ic.2015.03.009","publisher":"Elsevier","_id":"524","date_updated":"2023-02-23T12:24:45Z","type":"journal_article","publication":"Information and Computation","status":"public","date_published":"2015-10-11T00:00:00Z","year":"2015","related_material":{"record":[{"relation":"earlier_version","status":"public","id":"5403"}]},"external_id":{"arxiv":["1409.5306"]},"publist_id":"7295"},{"day":"22","scopus_import":1,"doi":"10.1016/j.cell.2015.09.037","author":[{"full_name":"Li, Wenyang","last_name":"Li","first_name":"Wenyang"},{"full_name":"Ma, Mengdi","last_name":"Ma","first_name":"Mengdi"},{"first_name":"Ying","last_name":"Feng","full_name":"Feng, Ying"},{"first_name":"Hongjiang","orcid":"0000-0001-5039-9660","last_name":"Li","id":"33CA54A6-F248-11E8-B48F-1D18A9856A87","full_name":"Li, Hongjiang"},{"first_name":"Yichuan","full_name":"Wang, Yichuan","last_name":"Wang"},{"first_name":"Yutong","last_name":"Ma","full_name":"Ma, Yutong"},{"last_name":"Li","full_name":"Li, Mingzhe","first_name":"Mingzhe"},{"first_name":"Fengying","last_name":"An","full_name":"An, Fengying"},{"first_name":"Hongwei","full_name":"Guo, Hongwei","last_name":"Guo"}],"oa_version":"None","title":"EIN2-directed translational regulation of ethylene signaling in arabidopsis","publisher":"Cell Press","_id":"532","volume":163,"date_updated":"2021-01-12T08:01:27Z","date_created":"2018-12-11T11:47:00Z","type":"journal_article","page":"670 - 683","intvolume":"       163","abstract":[{"text":"Ethylene is a gaseous phytohormone that plays vital roles in plant growth and development. Previous studies uncovered EIN2 as an essential signal transducer linking ethylene perception on ER to transcriptional regulation in the nucleus through a “cleave and shuttle” model. In this study, we report another mechanism of EIN2-mediated ethylene signaling, whereby EIN2 imposes the translational repression of EBF1 and EBF2 mRNA. We find that the EBF1/2 3′ UTRs mediate EIN2-directed translational repression and identify multiple poly-uridylates (PolyU) motifs as functional cis elements of 3′ UTRs. Furthermore, we demonstrate that ethylene induces EIN2 to associate with 3′ UTRs and target EBF1/2 mRNA to cytoplasmic processing-body (P-body) through interacting with multiple P-body factors, including EIN5 and PABs. Our study illustrates translational regulation as a key step in ethylene signaling and presents mRNA 3′ UTR functioning as a “signal transducer” to sense and relay cellular signaling in plants.","lang":"eng"}],"quality_controlled":"1","publication_status":"published","year":"2015","month":"10","department":[{"_id":"JiFr"}],"publist_id":"7285","language":[{"iso":"eng"}],"publication":"Cell","status":"public","citation":{"mla":"Li, Wenyang, et al. “EIN2-Directed Translational Regulation of Ethylene Signaling in Arabidopsis.” <i>Cell</i>, vol. 163, no. 3, Cell Press, 2015, pp. 670–83, doi:<a href=\"https://doi.org/10.1016/j.cell.2015.09.037\">10.1016/j.cell.2015.09.037</a>.","apa":"Li, W., Ma, M., Feng, Y., Li, H., Wang, Y., Ma, Y., … Guo, H. (2015). EIN2-directed translational regulation of ethylene signaling in arabidopsis. <i>Cell</i>. Cell Press. <a href=\"https://doi.org/10.1016/j.cell.2015.09.037\">https://doi.org/10.1016/j.cell.2015.09.037</a>","chicago":"Li, Wenyang, Mengdi Ma, Ying Feng, Hongjiang Li, Yichuan Wang, Yutong Ma, Mingzhe Li, Fengying An, and Hongwei Guo. “EIN2-Directed Translational Regulation of Ethylene Signaling in Arabidopsis.” <i>Cell</i>. Cell Press, 2015. <a href=\"https://doi.org/10.1016/j.cell.2015.09.037\">https://doi.org/10.1016/j.cell.2015.09.037</a>.","ista":"Li W, Ma M, Feng Y, Li H, Wang Y, Ma Y, Li M, An F, Guo H. 2015. EIN2-directed translational regulation of ethylene signaling in arabidopsis. Cell. 163(3), 670–683.","short":"W. Li, M. Ma, Y. Feng, H. Li, Y. Wang, Y. Ma, M. Li, F. An, H. Guo, Cell 163 (2015) 670–683.","ieee":"W. Li <i>et al.</i>, “EIN2-directed translational regulation of ethylene signaling in arabidopsis,” <i>Cell</i>, vol. 163, no. 3. Cell Press, pp. 670–683, 2015.","ama":"Li W, Ma M, Feng Y, et al. EIN2-directed translational regulation of ethylene signaling in arabidopsis. <i>Cell</i>. 2015;163(3):670-683. doi:<a href=\"https://doi.org/10.1016/j.cell.2015.09.037\">10.1016/j.cell.2015.09.037</a>"},"issue":"3","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_published":"2015-10-22T00:00:00Z"},{"publisher":"IST Austria","title":"Unifying two views on multiple mean-payoff objectives in Markov decision processes","oa_version":"Published Version","day":"12","alternative_title":["IST Austria Technical Report"],"author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","first_name":"Krishnendu","orcid":"0000-0002-4561-241X"},{"last_name":"Komarkova","full_name":"Komarkova, Zuzana","first_name":"Zuzana"},{"id":"44CEF464-F248-11E8-B48F-1D18A9856A87","full_name":"Kretinsky, Jan","last_name":"Kretinsky","orcid":"0000-0002-8122-2881","first_name":"Jan"}],"doi":"10.15479/AT:IST-2015-318-v1-1","date_created":"2018-12-12T11:39:17Z","type":"technical_report","_id":"5429","date_updated":"2023-02-23T12:26:16Z","ddc":["004"],"abstract":[{"lang":"eng","text":"We consider Markov decision processes (MDPs) with multiple limit-average (or mean-payoff) objectives. \r\nThere have been two different views: (i) the expectation semantics, where the goal is to optimize the expected mean-payoff objective, and (ii) the satisfaction semantics, where the goal is to maximize the probability of runs such that the mean-payoff value stays above a given vector.  \r\nWe consider the problem where the goal is to optimize the expectation under the constraint that the satisfaction semantics is ensured, and thus consider a generalization that unifies the existing semantics.\r\nOur problem captures the notion of optimization with respect to strategies that are risk-averse (i.e., ensures certain probabilistic guarantee).\r\nOur main results are algorithms for the decision problem which are always polynomial in the size of the MDP. We also show that an approximation of the Pareto-curve can be computed in time polynomial in the size of the MDP, and the approximation factor, but exponential in the number of dimensions.\r\nFinally, we present a complete characterization of the strategy complexity (in terms of memory bounds and randomization) required to solve our problem."}],"has_accepted_license":"1","page":"41","file_date_updated":"2020-07-14T12:46:52Z","publication_status":"published","publication_identifier":{"issn":["2664-1690"]},"month":"01","related_material":{"record":[{"id":"1657","status":"public","relation":"later_version"},{"relation":"later_version","status":"public","id":"466"},{"relation":"later_version","status":"public","id":"5435"}]},"year":"2015","file":[{"file_size":689863,"date_created":"2018-12-12T11:54:11Z","date_updated":"2020-07-14T12:46:52Z","creator":"system","file_id":"5533","file_name":"IST-2015-318-v1+1_main.pdf","access_level":"open_access","content_type":"application/pdf","relation":"main_file","checksum":"e4869a584567c506349abda9c8ec7db3"}],"department":[{"_id":"KrCh"}],"pubrep_id":"318","language":[{"iso":"eng"}],"status":"public","oa":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_published":"2015-01-12T00:00:00Z","citation":{"ama":"Chatterjee K, Komarkova Z, Kretinsky J. <i>Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes</i>. IST Austria; 2015. doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-318-v1-1\">10.15479/AT:IST-2015-318-v1-1</a>","ieee":"K. Chatterjee, Z. Komarkova, and J. Kretinsky, <i>Unifying two views on multiple mean-payoff objectives in Markov decision processes</i>. IST Austria, 2015.","short":"K. Chatterjee, Z. Komarkova, J. Kretinsky, Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes, IST Austria, 2015.","ista":"Chatterjee K, Komarkova Z, Kretinsky J. 2015. Unifying two views on multiple mean-payoff objectives in Markov decision processes, IST Austria, 41p.","chicago":"Chatterjee, Krishnendu, Zuzana Komarkova, and Jan Kretinsky. <i>Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes</i>. IST Austria, 2015. <a href=\"https://doi.org/10.15479/AT:IST-2015-318-v1-1\">https://doi.org/10.15479/AT:IST-2015-318-v1-1</a>.","apa":"Chatterjee, K., Komarkova, Z., &#38; Kretinsky, J. (2015). <i>Unifying two views on multiple mean-payoff objectives in Markov decision processes</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2015-318-v1-1\">https://doi.org/10.15479/AT:IST-2015-318-v1-1</a>","mla":"Chatterjee, Krishnendu, et al. <i>Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes</i>. IST Austria, 2015, doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-318-v1-1\">10.15479/AT:IST-2015-318-v1-1</a>."}},{"day":"10","alternative_title":["IST Austria Technical Report"],"doi":"10.15479/AT:IST-2015-319-v1-1","author":[{"orcid":"0000-0002-4561-241X","first_name":"Krishnendu","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"id":"3B699956-F248-11E8-B48F-1D18A9856A87","full_name":"Ibsen-Jensen, Rasmus","last_name":"Ibsen-Jensen","first_name":"Rasmus","orcid":"0000-0003-4783-0389"},{"id":"49704004-F248-11E8-B48F-1D18A9856A87","full_name":"Pavlogiannis, Andreas","last_name":"Pavlogiannis","first_name":"Andreas","orcid":"0000-0002-8943-0722"}],"title":"Faster algorithms for quantitative verification in constant treewidth graphs","oa_version":"Published Version","publisher":"IST Austria","_id":"5430","date_updated":"2023-02-23T12:26:22Z","date_created":"2018-12-12T11:39:17Z","type":"technical_report","has_accepted_license":"1","page":"31","ddc":["000"],"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. 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 mul- tiplicative 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 · n | )) = O ( n · log( n · W )) , when the output is a b , as compared to the previously best known algorithm with running time O ( n 2 · log( n · W )) . Third, for the minimum initial credit problem we show that (i) for general graphs the problem can be solved in O ( n 2 · m ) time and the associated decision problem can be solved in O ( n · m ) time, improving the previous known O ( n 3 · m · log( n · W )) and O ( n 2 · m ) bounds, respectively; and (ii) for constant treewidth graphs we present an algorithm that requires O ( n · log n ) time, improving the previous known O ( n 4 · log( n · W )) bound. We have implemented some of our algorithms and show that they present a significant speedup on standard benchmarks.","lang":"eng"}],"file_date_updated":"2020-07-14T12:46:52Z","publication_status":"published","publication_identifier":{"issn":["2664-1690"]},"year":"2015","month":"02","related_material":{"record":[{"relation":"later_version","status":"public","id":"1607"},{"id":"5437","relation":"later_version","status":"public"}]},"department":[{"_id":"KrCh"}],"file":[{"access_level":"open_access","content_type":"application/pdf","file_name":"IST-2015-319-v1+1_long.pdf","checksum":"62c6ea01e342553dcafb88a070fb1ad5","relation":"main_file","date_updated":"2020-07-14T12:46:52Z","creator":"system","file_size":1089651,"date_created":"2018-12-12T11:53:21Z","file_id":"5482"}],"oa":1,"status":"public","pubrep_id":"319","language":[{"iso":"eng"}],"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-319-v1-1\">10.15479/AT:IST-2015-319-v1-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-319-v1-1\">https://doi.org/10.15479/AT:IST-2015-319-v1-1</a>","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-319-v1-1\">https://doi.org/10.15479/AT:IST-2015-319-v1-1</a>.","ista":"Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. 2015. Faster algorithms for quantitative verification in constant treewidth graphs, IST Austria, 31p.","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-319-v1-1\">10.15479/AT:IST-2015-319-v1-1</a>"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_published":"2015-02-10T00:00:00Z"}]