[{"language":[{"iso":"eng"}],"publication_status":"published","related_material":{"record":[{"relation":"part_of_dissertation","status":"public","id":"6473"}]},"volume":115,"issue":"23","pmid":1,"oa_version":"Preprint","abstract":[{"text":"Although cells respond specifically to environments, how environmental identity is encoded intracellularly is not understood. Here, we study this organization of information in budding yeast by estimating the mutual information between environmental transitions and the dynamics of nuclear translocation for 10 transcription factors. Our method of estimation is general, scalable, and based on decoding from single cells. The dynamics of the transcription factors are necessary to encode the highest amounts of extracellular information, and we show that information is transduced through two channels: Generalists (Msn2/4, Tod6 and Dot6, Maf1, and Sfp1) can encode the nature of multiple stresses, but only if stress is high; specialists (Hog1, Yap1, and Mig1/2) encode one particular stress, but do so more quickly and for a wider range of magnitudes. In particular, Dot6 encodes almost as much information as Msn2, the master regulator of the environmental stress response. Each transcription factor reports differently, and it is only their collective behavior that distinguishes between multiple environmental states. Changes in the dynamics of the localization of transcription factors thus constitute a precise, distributed internal representation of extracellular change. We predict that such multidimensional representations are common in cellular decision-making.","lang":"eng"}],"intvolume":" 115","month":"06","main_file_link":[{"url":"https://www.biorxiv.org/content/early/2017/09/21/192039","open_access":"1"}],"scopus_import":"1","date_updated":"2023-09-11T12:58:24Z","department":[{"_id":"GaTk"}],"_id":"281","status":"public","article_type":"original","type":"journal_article","publication":"PNAS","day":"05","year":"2018","isi":1,"date_created":"2018-12-11T11:45:35Z","doi":"10.1073/pnas.1716659115","date_published":"2018-06-05T00:00:00Z","page":"6088 - 6093","acknowledgement":"This work was supported by the Biotechnology and Biological Sciences Research Council (J.M.J.P., I.F., and P.S.S.), the Engineering and Physical Sciences Research Council (EPSRC) (A.A.G.), and Austrian Science Fund Grant FWF P28844 (to G.T.).","oa":1,"quality_controlled":"1","publisher":"National Academy of Sciences","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","citation":{"ista":"Granados A, Pietsch J, Cepeda Humerez SA, Farquhar I, Tkačik G, Swain P. 2018. Distributed and dynamic intracellular organization of extracellular information. PNAS. 115(23), 6088–6093.","chicago":"Granados, Alejandro, Julian Pietsch, Sarah A Cepeda Humerez, Isebail Farquhar, Gašper Tkačik, and Peter Swain. “Distributed and Dynamic Intracellular Organization of Extracellular Information.” PNAS. National Academy of Sciences, 2018. https://doi.org/10.1073/pnas.1716659115.","ama":"Granados A, Pietsch J, Cepeda Humerez SA, Farquhar I, Tkačik G, Swain P. Distributed and dynamic intracellular organization of extracellular information. PNAS. 2018;115(23):6088-6093. doi:10.1073/pnas.1716659115","apa":"Granados, A., Pietsch, J., Cepeda Humerez, S. A., Farquhar, I., Tkačik, G., & Swain, P. (2018). Distributed and dynamic intracellular organization of extracellular information. PNAS. National Academy of Sciences. https://doi.org/10.1073/pnas.1716659115","ieee":"A. Granados, J. Pietsch, S. A. Cepeda Humerez, I. Farquhar, G. Tkačik, and P. Swain, “Distributed and dynamic intracellular organization of extracellular information,” PNAS, vol. 115, no. 23. National Academy of Sciences, pp. 6088–6093, 2018.","short":"A. Granados, J. Pietsch, S.A. Cepeda Humerez, I. Farquhar, G. Tkačik, P. Swain, PNAS 115 (2018) 6088–6093.","mla":"Granados, Alejandro, et al. “Distributed and Dynamic Intracellular Organization of Extracellular Information.” PNAS, vol. 115, no. 23, National Academy of Sciences, 2018, pp. 6088–93, doi:10.1073/pnas.1716659115."},"title":"Distributed and dynamic intracellular organization of extracellular information","external_id":{"isi":["000434114900071"],"pmid":["29784812"]},"article_processing_charge":"No","publist_id":"7618","author":[{"first_name":"Alejandro","full_name":"Granados, Alejandro","last_name":"Granados"},{"full_name":"Pietsch, Julian","last_name":"Pietsch","first_name":"Julian"},{"last_name":"Cepeda Humerez","full_name":"Cepeda Humerez, Sarah A","id":"3DEE19A4-F248-11E8-B48F-1D18A9856A87","first_name":"Sarah A"},{"full_name":"Farquhar, Isebail","last_name":"Farquhar","first_name":"Isebail"},{"first_name":"Gasper","id":"3D494DCA-F248-11E8-B48F-1D18A9856A87","full_name":"Tkacik, Gasper","orcid":"0000-0002-6699-1455","last_name":"Tkacik"},{"full_name":"Swain, Peter","last_name":"Swain","first_name":"Peter"}],"project":[{"name":"Biophysics of information processing in gene regulation","grant_number":"P28844-B27","_id":"254E9036-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"}]},{"article_number":"jcs207696","publist_id":"7184","author":[{"full_name":"Yamamoto, Wataru","last_name":"Yamamoto","first_name":"Wataru"},{"last_name":"Wada","full_name":"Wada, Suguru","first_name":"Suguru"},{"first_name":"Makoto","last_name":"Nagano","full_name":"Nagano, Makoto"},{"first_name":"Kaito","full_name":"Aoshima, Kaito","last_name":"Aoshima"},{"last_name":"Siekhaus","full_name":"Siekhaus, Daria E","orcid":"0000-0001-8323-8353","first_name":"Daria E","id":"3D224B9E-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Toshima","full_name":"Toshima, Junko","first_name":"Junko"},{"full_name":"Toshima, Jiro","last_name":"Toshima","first_name":"Jiro"}],"external_id":{"isi":["000424786900012"],"pmid":["29192062"]},"article_processing_charge":"No","title":"Distinct roles for plasma membrane PtdIns 4 P and PtdIns 4 5 P2 during yeast receptor mediated endocytosis","citation":{"ista":"Yamamoto W, Wada S, Nagano M, Aoshima K, Siekhaus DE, Toshima J, Toshima J. 2018. Distinct roles for plasma membrane PtdIns 4 P and PtdIns 4 5 P2 during yeast receptor mediated endocytosis. Journal of Cell Science. 131(1), jcs207696.","chicago":"Yamamoto, Wataru, Suguru Wada, Makoto Nagano, Kaito Aoshima, Daria E Siekhaus, Junko Toshima, and Jiro Toshima. “Distinct Roles for Plasma Membrane PtdIns 4 P and PtdIns 4 5 P2 during Yeast Receptor Mediated Endocytosis.” Journal of Cell Science. Company of Biologists, 2018. https://doi.org/10.1242/jcs.207696.","apa":"Yamamoto, W., Wada, S., Nagano, M., Aoshima, K., Siekhaus, D. E., Toshima, J., & Toshima, J. (2018). Distinct roles for plasma membrane PtdIns 4 P and PtdIns 4 5 P2 during yeast receptor mediated endocytosis. Journal of Cell Science. Company of Biologists. https://doi.org/10.1242/jcs.207696","ama":"Yamamoto W, Wada S, Nagano M, et al. Distinct roles for plasma membrane PtdIns 4 P and PtdIns 4 5 P2 during yeast receptor mediated endocytosis. Journal of Cell Science. 2018;131(1). doi:10.1242/jcs.207696","ieee":"W. Yamamoto et al., “Distinct roles for plasma membrane PtdIns 4 P and PtdIns 4 5 P2 during yeast receptor mediated endocytosis,” Journal of Cell Science, vol. 131, no. 1. Company of Biologists, 2018.","short":"W. Yamamoto, S. Wada, M. Nagano, K. Aoshima, D.E. Siekhaus, J. Toshima, J. Toshima, Journal of Cell Science 131 (2018).","mla":"Yamamoto, Wataru, et al. “Distinct Roles for Plasma Membrane PtdIns 4 P and PtdIns 4 5 P2 during Yeast Receptor Mediated Endocytosis.” Journal of Cell Science, vol. 131, no. 1, jcs207696, Company of Biologists, 2018, doi:10.1242/jcs.207696."},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","quality_controlled":"1","publisher":"Company of Biologists","oa":1,"doi":"10.1242/jcs.207696","date_published":"2018-01-04T00:00:00Z","date_created":"2018-12-11T11:47:32Z","isi":1,"year":"2018","day":"04","publication":"Journal of Cell Science","type":"journal_article","status":"public","_id":"620","department":[{"_id":"DaSi"}],"date_updated":"2023-09-11T12:57:13Z","scopus_import":"1","main_file_link":[{"url":"https://www.ncbi.nlm.nih.gov/pubmed/29192062","open_access":"1"}],"month":"01","intvolume":" 131","abstract":[{"text":"Clathrin-mediated endocytosis requires the coordinated assembly of various endocytic proteins and lipids at the plasma membrane. Accumulating evidence demonstrates a crucial role for phosphatidylinositol-4,5-bisphosphate (PtdIns(4,5)P2) in endocytosis, but specific roles for PtdIns(4)P other than as the biosynthetic precursor of PtdIns(4,5)P2 have not been clarified. In this study we investigated the role of PtdIns(4)P or PtdIns(4,5)P2 in receptor-mediated endocytosis through the construction of temperature-sensitive (ts) mutants for the PI 4-kinases Stt4p and Pik1p and the PtdIns(4) 5-kinase Mss4p. Quantitative analyses of endocytosis revealed that both the stt4(ts)pik1(ts) and mss4(ts) mutants have a severe defect in endocytic internalization. Live-cell imaging of endocytic protein dynamics in stt4(ts)pik1(ts) and mss4(ts) mutants revealed that PtdIns(4)P is required for the recruitment of the alpha-factor receptor Ste2p to clathrin-coated pits whereas PtdIns(4,5)P2 is required for membrane internalization. We also found that the localization to endocytic sites of the ENTH/ANTH domain-bearing clathrin adaptors, Ent1p/Ent2p and Yap1801p/Yap1802p, is significantly impaired in the stt4(ts)pik1(ts) mutant, but not in the mss4(ts) mutant. These results suggest distinct roles in successive steps for PtdIns(4)P and PtdIns(4,5)P2 during receptor-mediated endocytosis.","lang":"eng"}],"oa_version":"Published Version","pmid":1,"volume":131,"issue":"1","publication_status":"published","language":[{"iso":"eng"}]},{"date_updated":"2023-09-11T13:30:51Z","ddc":["000"],"department":[{"_id":"ToHe"}],"file_date_updated":"2020-07-14T12:45:17Z","_id":"182","conference":{"start_date":"2018-04-11","end_date":"2018-04-13","location":"Porto, Portugal","name":"HSCC: Hybrid Systems: Computation and Control"},"type":"conference","status":"public","publication_status":"published","publication_identifier":{"isbn":["978-1-4503-5642-8 "]},"language":[{"iso":"eng"}],"file":[{"access_level":"open_access","relation":"main_file","content_type":"application/pdf","file_id":"7833","checksum":"81eabc96430e84336ea88310ac0a1ad0","creator":"dernst","date_updated":"2020-07-14T12:45:17Z","file_size":5900421,"date_created":"2020-05-14T12:18:29Z","file_name":"2018_HSCC_Bakhirkin.pdf"}],"abstract":[{"lang":"eng","text":"We describe a new algorithm for the parametric identification problem for signal temporal logic (STL), stated as follows. Given a densetime real-valued signal w and a parameterized temporal logic formula φ, compute the subset of the parameter space that renders the formula satisfied by the signal. Unlike previous solutions, which were based on search in the parameter space or quantifier elimination, our procedure works recursively on φ and computes the evolution over time of the set of valid parameter assignments. This procedure is similar to that of monitoring or computing the robustness of φ relative to w. Our implementation and experiments demonstrate that this approach can work well in practice."}],"oa_version":"Submitted Version","scopus_import":"1","alternative_title":["HSCC Proceedings"],"month":"04","citation":{"mla":"Bakhirkin, Alexey, et al. “Efficient Parametric Identification for STL.” Proceedings of the 21st International Conference on Hybrid Systems, ACM, 2018, pp. 177–86, doi:10.1145/3178126.3178132.","ama":"Bakhirkin A, Ferrere T, Maler O. Efficient parametric identification for STL. In: Proceedings of the 21st International Conference on Hybrid Systems. ACM; 2018:177-186. doi:10.1145/3178126.3178132","apa":"Bakhirkin, A., Ferrere, T., & Maler, O. (2018). Efficient parametric identification for STL. In Proceedings of the 21st International Conference on Hybrid Systems (pp. 177–186). Porto, Portugal: ACM. https://doi.org/10.1145/3178126.3178132","short":"A. Bakhirkin, T. Ferrere, O. Maler, in:, Proceedings of the 21st International Conference on Hybrid Systems, ACM, 2018, pp. 177–186.","ieee":"A. Bakhirkin, T. Ferrere, and O. Maler, “Efficient parametric identification for STL,” in Proceedings of the 21st International Conference on Hybrid Systems, Porto, Portugal, 2018, pp. 177–186.","chicago":"Bakhirkin, Alexey, Thomas Ferrere, and Oded Maler. “Efficient Parametric Identification for STL.” In Proceedings of the 21st International Conference on Hybrid Systems, 177–86. ACM, 2018. https://doi.org/10.1145/3178126.3178132.","ista":"Bakhirkin A, Ferrere T, Maler O. 2018. Efficient parametric identification for STL. Proceedings of the 21st International Conference on Hybrid Systems. HSCC: Hybrid Systems: Computation and Control, HSCC Proceedings, , 177–186."},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","article_processing_charge":"No","external_id":{"isi":["000474781600020"]},"author":[{"first_name":"Alexey","full_name":"Bakhirkin, Alexey","last_name":"Bakhirkin"},{"first_name":"Thomas","id":"40960E6E-F248-11E8-B48F-1D18A9856A87","full_name":"Ferrere, Thomas","orcid":"0000-0001-5199-3143","last_name":"Ferrere"},{"first_name":"Oded","full_name":"Maler, Oded","last_name":"Maler"}],"publist_id":"7739","title":"Efficient parametric identification for STL","project":[{"_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"S 11407_N23","name":"Rigorous Systems Engineering"}],"year":"2018","has_accepted_license":"1","isi":1,"publication":"Proceedings of the 21st International Conference on Hybrid Systems","day":"11","page":"177 - 186","date_created":"2018-12-11T11:45:04Z","doi":"10.1145/3178126.3178132","date_published":"2018-04-11T00:00:00Z","oa":1,"quality_controlled":"1","publisher":"ACM"},{"department":[{"_id":"KrCh"}],"date_updated":"2023-09-11T13:23:42Z","status":"public","type":"conference","conference":{"name":"LICS: Logic in Computer Science","start_date":"2018-07-09","end_date":"2018-07-12","location":"Oxford, United Kingdom"},"_id":"143","volume":"F138033","ec_funded":1,"language":[{"iso":"eng"}],"publication_identifier":{"isbn":["978-1-4503-5583-4"]},"publication_status":"published","month":"07","scopus_import":"1","alternative_title":["ACM/IEEE Symposium on Logic in Computer Science"],"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1804.10985"}],"oa_version":"Preprint","abstract":[{"lang":"eng","text":"Vector Addition Systems with States (VASS) provide a well-known and fundamental model for the analysis of concurrent processes, parameterized systems, and are also used as abstract models of programs in resource bound analysis. In this paper we study the problem of obtaining asymptotic bounds on the termination time of a given VASS. In particular, we focus on the practically important case of obtaining polynomial bounds on termination time. Our main contributions are as follows: First, we present a polynomial-time algorithm for deciding whether a given VASS has a linear asymptotic complexity. We also show that if the complexity of a VASS is not linear, it is at least quadratic. Second, we classify VASS according to quantitative properties of their cycles. We show that certain singularities in these properties are the key reason for non-polynomial asymptotic complexity of VASS. In absence of singularities, we show that the asymptotic complexity is always polynomial and of the form Θ(nk), for some integer k d, where d is the dimension of the VASS. We present a polynomial-time algorithm computing the optimal k. For general VASS, the same algorithm, which is based on a complete technique for the construction of ranking functions in VASS, produces a valid lower bound, i.e., a k such that the termination complexity is (nk). Our results are based on new insights into the geometry of VASS dynamics, which hold the potential for further applicability to VASS analysis."}],"title":"Efficient algorithms for asymptotic bounds on termination time in VASS","author":[{"first_name":"Tomáš","last_name":"Brázdil","full_name":"Brázdil, Tomáš"},{"last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu"},{"last_name":"Kučera","full_name":"Kučera, Antonín","first_name":"Antonín"},{"id":"3CC3B868-F248-11E8-B48F-1D18A9856A87","first_name":"Petr","last_name":"Novotny","full_name":"Novotny, Petr"},{"first_name":"Dominik","full_name":"Velan, Dominik","last_name":"Velan"},{"full_name":"Zuleger, Florian","last_name":"Zuleger","first_name":"Florian"}],"publist_id":"7780","external_id":{"isi":["000545262800020"]},"article_processing_charge":"No","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","citation":{"ista":"Brázdil T, Chatterjee K, Kučera A, Novotný P, Velan D, Zuleger F. 2018. Efficient algorithms for asymptotic bounds on termination time in VASS. LICS: Logic in Computer Science, ACM/IEEE Symposium on Logic in Computer Science, vol. F138033, 185–194.","chicago":"Brázdil, Tomáš, Krishnendu Chatterjee, Antonín Kučera, Petr Novotný, Dominik Velan, and Florian Zuleger. “Efficient Algorithms for Asymptotic Bounds on Termination Time in VASS,” F138033:185–94. IEEE, 2018. https://doi.org/10.1145/3209108.3209191.","short":"T. Brázdil, K. Chatterjee, A. Kučera, P. Novotný, D. Velan, F. Zuleger, in:, IEEE, 2018, pp. 185–194.","ieee":"T. Brázdil, K. Chatterjee, A. Kučera, P. Novotný, D. Velan, and F. Zuleger, “Efficient algorithms for asymptotic bounds on termination time in VASS,” presented at the LICS: Logic in Computer Science, Oxford, United Kingdom, 2018, vol. F138033, pp. 185–194.","apa":"Brázdil, T., Chatterjee, K., Kučera, A., Novotný, P., Velan, D., & Zuleger, F. (2018). Efficient algorithms for asymptotic bounds on termination time in VASS (Vol. F138033, pp. 185–194). Presented at the LICS: Logic in Computer Science, Oxford, United Kingdom: IEEE. https://doi.org/10.1145/3209108.3209191","ama":"Brázdil T, Chatterjee K, Kučera A, Novotný P, Velan D, Zuleger F. Efficient algorithms for asymptotic bounds on termination time in VASS. In: Vol F138033. IEEE; 2018:185-194. doi:10.1145/3209108.3209191","mla":"Brázdil, Tomáš, et al. Efficient Algorithms for Asymptotic Bounds on Termination Time in VASS. Vol. F138033, IEEE, 2018, pp. 185–94, doi:10.1145/3209108.3209191."},"project":[{"grant_number":"ICT15-003","name":"Efficient Algorithms for Computer Aided Verification","_id":"25892FC0-B435-11E9-9278-68D0E5697425"},{"grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications","_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"},{"grant_number":"S 11407_N23","name":"Rigorous Systems Engineering","_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"}],"doi":"10.1145/3209108.3209191","date_published":"2018-07-09T00:00:00Z","date_created":"2018-12-11T11:44:51Z","page":"185 - 194","day":"09","isi":1,"year":"2018","quality_controlled":"1","publisher":"IEEE","oa":1},{"project":[{"_id":"25FBA906-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"616160","name":"Discrete Optimization in Computer Vision: Theory and Practice"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","citation":{"ista":"Mohapatra P, Rolinek M, Jawahar CV, Kolmogorov V, Kumar MP. 2018. Efficient optimization for rank-based loss functions. 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition. CVPR: Conference on Computer Vision and Pattern Recognition, 3693–3701.","chicago":"Mohapatra, Pritish, Michal Rolinek, C V Jawahar, Vladimir Kolmogorov, and M Pawan Kumar. “Efficient Optimization for Rank-Based Loss Functions.” In 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, 3693–3701. IEEE, 2018. https://doi.org/10.1109/cvpr.2018.00389.","apa":"Mohapatra, P., Rolinek, M., Jawahar, C. V., Kolmogorov, V., & Kumar, M. P. (2018). Efficient optimization for rank-based loss functions. In 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition (pp. 3693–3701). Salt Lake City, UT, USA: IEEE. https://doi.org/10.1109/cvpr.2018.00389","ama":"Mohapatra P, Rolinek M, Jawahar CV, Kolmogorov V, Kumar MP. Efficient optimization for rank-based loss functions. In: 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition. IEEE; 2018:3693-3701. doi:10.1109/cvpr.2018.00389","ieee":"P. Mohapatra, M. Rolinek, C. V. Jawahar, V. Kolmogorov, and M. P. Kumar, “Efficient optimization for rank-based loss functions,” in 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, Salt Lake City, UT, USA, 2018, pp. 3693–3701.","short":"P. Mohapatra, M. Rolinek, C.V. Jawahar, V. Kolmogorov, M.P. Kumar, in:, 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, IEEE, 2018, pp. 3693–3701.","mla":"Mohapatra, Pritish, et al. “Efficient Optimization for Rank-Based Loss Functions.” 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, IEEE, 2018, pp. 3693–701, doi:10.1109/cvpr.2018.00389."},"title":"Efficient optimization for rank-based loss functions","author":[{"first_name":"Pritish","full_name":"Mohapatra, Pritish","last_name":"Mohapatra"},{"last_name":"Rolinek","full_name":"Rolinek, Michal","id":"3CB3BC06-F248-11E8-B48F-1D18A9856A87","first_name":"Michal"},{"first_name":"C V","last_name":"Jawahar","full_name":"Jawahar, C V"},{"first_name":"Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","full_name":"Kolmogorov, Vladimir","last_name":"Kolmogorov"},{"full_name":"Kumar, M Pawan","last_name":"Kumar","first_name":"M Pawan"}],"article_processing_charge":"No","external_id":{"arxiv":["1604.08269"],"isi":["000457843603087"]},"publisher":"IEEE","quality_controlled":"1","oa":1,"day":"28","publication":"2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition","isi":1,"year":"2018","doi":"10.1109/cvpr.2018.00389","date_published":"2018-06-28T00:00:00Z","date_created":"2018-12-11T11:45:33Z","page":"3693-3701","_id":"273","status":"public","type":"conference","conference":{"name":"CVPR: Conference on Computer Vision and Pattern Recognition","location":"Salt Lake City, UT, USA","end_date":"2018-06-22","start_date":"2018-06-18"},"date_updated":"2023-09-11T13:24:43Z","department":[{"_id":"VlKo"}],"oa_version":"Preprint","abstract":[{"text":"The accuracy of information retrieval systems is often measured using complex loss functions such as the average precision (AP) or the normalized discounted cumulative gain (NDCG). Given a set of positive and negative samples, the parameters of a retrieval system can be estimated by minimizing these loss functions. However, the non-differentiability and non-decomposability of these loss functions does not allow for simple gradient based optimization algorithms. This issue is generally circumvented by either optimizing a structured hinge-loss upper bound to the loss function or by using asymptotic methods like the direct-loss minimization framework. Yet, the high computational complexity of loss-augmented inference, which is necessary for both the frameworks, prohibits its use in large training data sets. To alleviate this deficiency, we present a novel quicksort flavored algorithm for a large class of non-decomposable loss functions. We provide a complete characterization of the loss functions that are amenable to our algorithm, and show that it includes both AP and NDCG based loss functions. Furthermore, we prove that no comparison based algorithm can improve upon the computational complexity of our approach asymptotically. We demonstrate the effectiveness of our approach in the context of optimizing the structured hinge loss upper bound of AP and NDCG loss for learning models for a variety of vision tasks. We show that our approach provides significantly better results than simpler decomposable loss functions, while requiring a comparable training time.","lang":"eng"}],"month":"06","scopus_import":"1","main_file_link":[{"url":"https://arxiv.org/abs/1604.08269","open_access":"1"}],"language":[{"iso":"eng"}],"publication_identifier":{"isbn":["9781538664209"]},"publication_status":"published","ec_funded":1},{"abstract":[{"text":"We report on quantum capacitance measurements of high quality, graphite- and hexagonal boron nitride encapsulated Bernal stacked trilayer graphene devices. At zero applied magnetic field, we observe a number of electron density- and electrical displacement-tuned features in the electronic compressibility associated with changes in Fermi surface topology. At high displacement field and low density, strong trigonal warping gives rise to emergent Dirac gullies centered near the corners of the hexagonal Brillouin and related by three fold rotation symmetry. At low magnetic fields of B=1.25~T, the gullies manifest as a change in the degeneracy of the Landau levels from two to three. Weak incompressible states are also observed at integer filling within these triplets Landau levels, which a Hartree-Fock analysis indicates are associated with Coulomb-driven nematic phases that spontaneously break rotation symmetry.","lang":"eng"}],"oa_version":"Preprint","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1805.01038"}],"scopus_import":"1","intvolume":" 121","month":"10","publication_status":"published","language":[{"iso":"eng"}],"volume":121,"issue":"16","_id":"289","type":"journal_article","article_type":"original","status":"public","date_updated":"2023-09-11T13:39:50Z","department":[{"_id":"MaSe"}],"acknowledgement":"The experimental work at UCSB was funded by the National Science Foundation under Grant No. DMR- 1654186. Work at Columbia was supported by the National Science Foundation under Grant No. DMR- 1507788. K. W. and T. T. acknowledge support from the Elemental Strategy Initiative conducted by the Ministry of Education, Culture, Sports, Science and Technology, Japan, and the Japan Society for the Promotion of Science KAKENHI Grant No. JP15K21722. E. M. S. acknowledges the support of the Elings Fellowship from the California Nanosystems Institute at the University of California, Santa Barbara. A. F. Y. acknowledges the support of the David and Lucile Packard foundation and the Sloan Foundation. Measurements made use of a dilution refrigerator funded through the Major Research Instrumentation program of the U.S. National Science Foundation under Grant No. DMR- 1531389, and the MRL Shared Experimental Facilities, which are supported by the MRSEC Program of the U.S. National Science Foundation under Grant No. DMR- 1720256.","oa":1,"publisher":"American Physical Society","quality_controlled":"1","year":"2018","isi":1,"publication":"Physical Review Letters","day":"19","date_created":"2018-12-11T11:45:38Z","date_published":"2018-10-19T00:00:00Z","doi":"10.1103/PhysRevLett.121.167601","article_number":"167601","citation":{"chicago":"Zibrov, Alexander, Peng Rao, Carlos Kometter, Jia Li, Cory Dean, Takashi Taniguchi, Kenji Watanabe, Maksym Serbyn, and Andrea Young. “Emergent Dirac Gullies and Gully-Symmetry-Breaking Quantum Hall States in ABA Trilayer Graphene.” Physical Review Letters. American Physical Society, 2018. https://doi.org/10.1103/PhysRevLett.121.167601.","ista":"Zibrov A, Rao P, Kometter C, Li J, Dean C, Taniguchi T, Watanabe K, Serbyn M, Young A. 2018. Emergent dirac gullies and gully-symmetry-breaking quantum hall states in ABA trilayer graphene. Physical Review Letters. 121(16), 167601.","mla":"Zibrov, Alexander, et al. “Emergent Dirac Gullies and Gully-Symmetry-Breaking Quantum Hall States in ABA Trilayer Graphene.” Physical Review Letters, vol. 121, no. 16, 167601, American Physical Society, 2018, doi:10.1103/PhysRevLett.121.167601.","ama":"Zibrov A, Rao P, Kometter C, et al. Emergent dirac gullies and gully-symmetry-breaking quantum hall states in ABA trilayer graphene. Physical Review Letters. 2018;121(16). doi:10.1103/PhysRevLett.121.167601","apa":"Zibrov, A., Rao, P., Kometter, C., Li, J., Dean, C., Taniguchi, T., … Young, A. (2018). Emergent dirac gullies and gully-symmetry-breaking quantum hall states in ABA trilayer graphene. Physical Review Letters. American Physical Society. https://doi.org/10.1103/PhysRevLett.121.167601","ieee":"A. Zibrov et al., “Emergent dirac gullies and gully-symmetry-breaking quantum hall states in ABA trilayer graphene,” Physical Review Letters, vol. 121, no. 16. American Physical Society, 2018.","short":"A. Zibrov, P. Rao, C. Kometter, J. Li, C. Dean, T. Taniguchi, K. Watanabe, M. Serbyn, A. Young, Physical Review Letters 121 (2018)."},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","external_id":{"arxiv":["1805.01038"],"isi":["000447307500007"]},"article_processing_charge":"No","author":[{"full_name":"Zibrov, Alexander","last_name":"Zibrov","first_name":"Alexander"},{"last_name":"Peng","orcid":"0000-0003-1250-0021","full_name":"Peng, Rao","first_name":"Rao","id":"47C23AC6-02D0-11E9-BD0E-99399A5D3DEB"},{"last_name":"Kometter","full_name":"Kometter, Carlos","first_name":"Carlos"},{"last_name":"Li","full_name":"Li, Jia","first_name":"Jia"},{"full_name":"Dean, Cory","last_name":"Dean","first_name":"Cory"},{"full_name":"Taniguchi, Takashi","last_name":"Taniguchi","first_name":"Takashi"},{"first_name":"Kenji","last_name":"Watanabe","full_name":"Watanabe, Kenji"},{"full_name":"Serbyn, Maksym","orcid":"0000-0002-2399-5827","last_name":"Serbyn","first_name":"Maksym","id":"47809E7E-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Andrea","last_name":"Young","full_name":"Young, Andrea"}],"title":"Emergent dirac gullies and gully-symmetry-breaking quantum hall states in ABA trilayer graphene"},{"external_id":{"isi":["000439042800001"],"pmid":["29293441"]},"article_processing_charge":"No","author":[{"first_name":"Vahid","full_name":"Salari, Vahid","last_name":"Salari"},{"orcid":"0000-0003-0415-1423","full_name":"Barzanjeh, Shabir","last_name":"Barzanjeh","first_name":"Shabir","id":"2D25E1F6-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Cifra, Michal","last_name":"Cifra","first_name":"Michal"},{"last_name":"Simon","full_name":"Simon, Christoph","first_name":"Christoph"},{"last_name":"Scholkmann","full_name":"Scholkmann, Felix","first_name":"Felix"},{"last_name":"Alirezaei","full_name":"Alirezaei, Zahra","first_name":"Zahra"},{"first_name":"Jack","last_name":"Tuszynski","full_name":"Tuszynski, Jack"}],"title":"Electromagnetic fields and optomechanics In cancer diagnostics and treatment","citation":{"chicago":"Salari, Vahid, Shabir Barzanjeh, Michal Cifra, Christoph Simon, Felix Scholkmann, Zahra Alirezaei, and Jack Tuszynski. “Electromagnetic Fields and Optomechanics In Cancer Diagnostics and Treatment.” Frontiers in Bioscience - Landmark. Frontiers in Bioscience, 2018. https://doi.org/10.2741/4651.","ista":"Salari V, Barzanjeh S, Cifra M, Simon C, Scholkmann F, Alirezaei Z, Tuszynski J. 2018. Electromagnetic fields and optomechanics In cancer diagnostics and treatment. Frontiers in Bioscience - Landmark. 23(8), 1391–1406.","mla":"Salari, Vahid, et al. “Electromagnetic Fields and Optomechanics In Cancer Diagnostics and Treatment.” Frontiers in Bioscience - Landmark, vol. 23, no. 8, Frontiers in Bioscience, 2018, pp. 1391–406, doi:10.2741/4651.","apa":"Salari, V., Barzanjeh, S., Cifra, M., Simon, C., Scholkmann, F., Alirezaei, Z., & Tuszynski, J. (2018). Electromagnetic fields and optomechanics In cancer diagnostics and treatment. Frontiers in Bioscience - Landmark. Frontiers in Bioscience. https://doi.org/10.2741/4651","ama":"Salari V, Barzanjeh S, Cifra M, et al. Electromagnetic fields and optomechanics In cancer diagnostics and treatment. Frontiers in Bioscience - Landmark. 2018;23(8):1391-1406. doi:10.2741/4651","short":"V. Salari, S. Barzanjeh, M. Cifra, C. Simon, F. Scholkmann, Z. Alirezaei, J. Tuszynski, Frontiers in Bioscience - Landmark 23 (2018) 1391–1406.","ieee":"V. Salari et al., “Electromagnetic fields and optomechanics In cancer diagnostics and treatment,” Frontiers in Bioscience - Landmark, vol. 23, no. 8. Frontiers in Bioscience, pp. 1391–1406, 2018."},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","project":[{"call_identifier":"H2020","_id":"258047B6-B435-11E9-9278-68D0E5697425","name":"Microwave-to-Optical Quantum Link: Quantum Teleportation and Quantum Illumination with cavity Optomechanics SUPEREOM","grant_number":"707438"}],"page":"1391 - 1406","date_created":"2018-12-11T11:45:37Z","doi":"10.2741/4651","date_published":"2018-03-01T00:00:00Z","year":"2018","isi":1,"publication":"Frontiers in Bioscience - Landmark","day":"01","oa":1,"quality_controlled":"1","publisher":"Frontiers in Bioscience","acknowledgement":"The work of SB has been supported by the European Unions Horizon 2020 research and innovation program under the Marie Sklodowska Curie grant agreement No MSC-IF 707438 SUPEREOM. JAT gratefully acknowledges funding support from NSERC (Canada) for his research. MC acknowledges support from the Czech Science Foundation, projects 15-17102S and 17-11898S and he participates in COST Action BM1309, CA15211 and bilateral exchange project between Czech and Slovak Academies of Sciences, SAV-15-22.","department":[{"_id":"JoFi"}],"date_updated":"2023-09-11T13:38:14Z","type":"journal_article","status":"public","_id":"287","ec_funded":1,"issue":"8","volume":23,"publication_status":"published","language":[{"iso":"eng"}],"main_file_link":[{"open_access":"1","url":"https://www.bioscience.org/2018/v23/af/4651/fulltext.htm"}],"scopus_import":"1","intvolume":" 23","month":"03","abstract":[{"text":"In this paper, we discuss biological effects of electromagnetic (EM) fields in the context of cancer biology. In particular, we review the nanomechanical properties of microtubules (MTs), the latter being one of the most successful targets for cancer therapy. We propose an investigation on the coupling of electromagnetic radiation to mechanical vibrations of MTs as an important basis for biological and medical applications. In our opinion, optomechanical methods can accurately monitor and control the mechanical properties of isolated MTs in a liquid environment. Consequently, studying nanomechanical properties of MTs may give useful information for future applications to diagnostic and therapeutic technologies involving non-invasive externally applied physical fields. For example, electromagnetic fields or high intensity ultrasound can be used therapeutically avoiding harmful side effects of chemotherapeutic agents or classical radiation therapy.","lang":"eng"}],"pmid":1,"oa_version":"Submitted Version"},{"publisher":"ACM","quality_controlled":"1","oa":1,"date_published":"2018-01-01T00:00:00Z","doi":"10.1145/3078632","date_created":"2018-12-11T11:46:24Z","day":"01","publication":"Journal of the ACM","isi":1,"year":"2018","project":[{"call_identifier":"FP7","_id":"25681D80-B435-11E9-9278-68D0E5697425","grant_number":"291734","name":"International IST Postdoc Fellowship Programme"}],"article_number":"5","title":"Embeddability in the 3-Sphere is decidable","publist_id":"7398","author":[{"first_name":"Jiří","full_name":"Matoušek, Jiří","last_name":"Matoušek"},{"first_name":"Eric","full_name":"Sedgwick, Eric","last_name":"Sedgwick"},{"id":"38AC689C-F248-11E8-B48F-1D18A9856A87","first_name":"Martin","full_name":"Tancer, Martin","orcid":"0000-0002-1191-6714","last_name":"Tancer"},{"orcid":"0000-0002-1494-0568","full_name":"Wagner, Uli","last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","first_name":"Uli"}],"external_id":{"isi":["000425685900006"],"arxiv":["1402.0815"]},"article_processing_charge":"No","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","citation":{"apa":"Matoušek, J., Sedgwick, E., Tancer, M., & Wagner, U. (2018). Embeddability in the 3-Sphere is decidable. Journal of the ACM. ACM. https://doi.org/10.1145/3078632","ama":"Matoušek J, Sedgwick E, Tancer M, Wagner U. Embeddability in the 3-Sphere is decidable. Journal of the ACM. 2018;65(1). doi:10.1145/3078632","short":"J. Matoušek, E. Sedgwick, M. Tancer, U. Wagner, Journal of the ACM 65 (2018).","ieee":"J. Matoušek, E. Sedgwick, M. Tancer, and U. Wagner, “Embeddability in the 3-Sphere is decidable,” Journal of the ACM, vol. 65, no. 1. ACM, 2018.","mla":"Matoušek, Jiří, et al. “Embeddability in the 3-Sphere Is Decidable.” Journal of the ACM, vol. 65, no. 1, 5, ACM, 2018, doi:10.1145/3078632.","ista":"Matoušek J, Sedgwick E, Tancer M, Wagner U. 2018. Embeddability in the 3-Sphere is decidable. Journal of the ACM. 65(1), 5.","chicago":"Matoušek, Jiří, Eric Sedgwick, Martin Tancer, and Uli Wagner. “Embeddability in the 3-Sphere Is Decidable.” Journal of the ACM. ACM, 2018. https://doi.org/10.1145/3078632."},"month":"01","intvolume":" 65","scopus_import":"1","main_file_link":[{"url":"https://arxiv.org/abs/1402.0815","open_access":"1"}],"oa_version":"Preprint","abstract":[{"lang":"eng","text":"We show that the following algorithmic problem is decidable: given a 2-dimensional simplicial complex, can it be embedded (topologically, or equivalently, piecewise linearly) in R3? By a known reduction, it suffices to decide the embeddability of a given triangulated 3-manifold X into the 3-sphere S3. The main step, which allows us to simplify X and recurse, is in proving that if X can be embedded in S3, then there is also an embedding in which X has a short meridian, that is, an essential curve in the boundary of X bounding a disk in S3 \\ X with length bounded by a computable function of the number of tetrahedra of X."}],"related_material":{"record":[{"status":"public","id":"2157","relation":"earlier_version"}]},"issue":"1","volume":65,"ec_funded":1,"language":[{"iso":"eng"}],"publication_status":"published","status":"public","article_type":"original","type":"journal_article","_id":"425","department":[{"_id":"UlWa"}],"date_updated":"2023-09-11T13:38:49Z"},{"project":[{"_id":"25B07788-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"250152","name":"Limits to selection in biology and in evolutionary computation"}],"external_id":{"isi":["000440392900014"]},"article_processing_charge":"No","author":[{"full_name":"Barton, Nicholas H","orcid":"0000-0002-8548-5240","last_name":"Barton","first_name":"Nicholas H","id":"4880FE40-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Alison","full_name":"Etheridge, Alison","last_name":"Etheridge"}],"publist_id":"7250","title":"Establishment in a new habitat by polygenic adaptation","citation":{"ista":"Barton NH, Etheridge A. 2018. Establishment in a new habitat by polygenic adaptation. Theoretical Population Biology. 122(7), 110–127.","chicago":"Barton, Nicholas H, and Alison Etheridge. “Establishment in a New Habitat by Polygenic Adaptation.” Theoretical Population Biology. Academic Press, 2018. https://doi.org/10.1016/j.tpb.2017.11.007.","ama":"Barton NH, Etheridge A. Establishment in a new habitat by polygenic adaptation. Theoretical Population Biology. 2018;122(7):110-127. doi:10.1016/j.tpb.2017.11.007","apa":"Barton, N. H., & Etheridge, A. (2018). Establishment in a new habitat by polygenic adaptation. Theoretical Population Biology. Academic Press. https://doi.org/10.1016/j.tpb.2017.11.007","ieee":"N. H. Barton and A. Etheridge, “Establishment in a new habitat by polygenic adaptation,” Theoretical Population Biology, vol. 122, no. 7. Academic Press, pp. 110–127, 2018.","short":"N.H. Barton, A. Etheridge, Theoretical Population Biology 122 (2018) 110–127.","mla":"Barton, Nicholas H., and Alison Etheridge. “Establishment in a New Habitat by Polygenic Adaptation.” Theoretical Population Biology, vol. 122, no. 7, Academic Press, 2018, pp. 110–27, doi:10.1016/j.tpb.2017.11.007."},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","oa":1,"publisher":"Academic Press","quality_controlled":"1","page":"110-127","date_created":"2018-12-11T11:47:12Z","doi":"10.1016/j.tpb.2017.11.007","date_published":"2018-07-01T00:00:00Z","year":"2018","isi":1,"has_accepted_license":"1","publication":"Theoretical Population Biology","day":"01","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by-nc/4.0/legalcode","image":"/images/cc_by_nc.png","name":"Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0)","short":"CC BY-NC (4.0)"},"article_type":"original","type":"journal_article","status":"public","_id":"564","file_date_updated":"2020-07-14T12:47:09Z","department":[{"_id":"NiBa"}],"date_updated":"2023-09-11T13:41:22Z","ddc":["519","576"],"scopus_import":"1","intvolume":" 122","month":"07","abstract":[{"text":"Maladapted individuals can only colonise a new habitat if they can evolve a\r\npositive growth rate fast enough to avoid extinction, a process known as evolutionary\r\nrescue. We treat log fitness at low density in the new habitat as a\r\nsingle polygenic trait and thus use the infinitesimal model to follow the evolution\r\nof the growth rate; this assumes that the trait values of offspring of a\r\nsexual union are normally distributed around the mean of the parents’ trait\r\nvalues, with variance that depends only on the parents’ relatedness. The\r\nprobability that a single migrant can establish depends on just two parameters:\r\nthe mean and genetic variance of the trait in the source population.\r\nThe chance of success becomes small if migrants come from a population\r\nwith mean growth rate in the new habitat more than a few standard deviations\r\nbelow zero; this chance depends roughly equally on the probability\r\nthat the initial founder is unusually fit, and on the subsequent increase in\r\ngrowth rate of its offspring as a result of selection. The loss of genetic variation\r\nduring the founding event is substantial, but highly variable. With\r\ncontinued migration at rate M, establishment is inevitable; when migration\r\nis rare, the expected time to establishment decreases inversely with M.\r\nHowever, above a threshold migration rate, the population may be trapped\r\nin a ‘sink’ state, in which adaptation is held back by gene flow; above this\r\nthreshold, the expected time to establishment increases exponentially with M. This threshold behaviour is captured by a deterministic approximation,\r\nwhich assumes a Gaussian distribution of the trait in the founder population\r\nwith mean and variance evolving deterministically. By assuming a constant\r\ngenetic variance, we also develop a diffusion approximation for the joint distribution\r\nof population size and trait mean, which extends to include stabilising\r\nselection and density regulation. Divergence of the population from its\r\nancestors causes partial reproductive isolation, which we measure through\r\nthe reproductive value of migrants into the newly established population.","lang":"eng"}],"oa_version":"Submitted Version","license":"https://creativecommons.org/licenses/by-nc/4.0/","ec_funded":1,"issue":"7","volume":122,"related_material":{"record":[{"id":"9842","status":"public","relation":"research_data"}]},"publication_status":"published","language":[{"iso":"eng"}],"file":[{"content_type":"application/pdf","access_level":"open_access","relation":"main_file","file_id":"7199","checksum":"0b96f6db47e3e91b5e7d103b847c239d","date_updated":"2020-07-14T12:47:09Z","file_size":2287682,"creator":"nbarton","date_created":"2019-12-21T09:36:39Z","file_name":"bartonetheridge.pdf"}]},{"page":"246 - 249","date_published":"2018-07-04T00:00:00Z","doi":"10.1038/s41586-018-0277-x","date_created":"2018-12-11T11:44:56Z","isi":1,"has_accepted_license":"1","year":"2018","day":"04","publication":"Nature","quality_controlled":"1","publisher":"Nature Publishing Group","oa":1,"acknowledgement":"European Research Council Start Grant 279307, Austrian Science Fund (FWF) grant P23499-N23, \r\nC.H. acknowledges support from the ISTFELLOW programme.","publist_id":"7764","author":[{"last_name":"Hilbe","full_name":"Hilbe, Christian","orcid":"0000-0001-5116-955X","id":"2FDF8F3C-F248-11E8-B48F-1D18A9856A87","first_name":"Christian"},{"first_name":"Štepán","full_name":"Šimsa, Štepán","last_name":"Šimsa"},{"last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Martin","last_name":"Nowak","full_name":"Nowak, Martin"}],"external_id":{"isi":["000438240900054"]},"article_processing_charge":"No","title":"Evolution of cooperation in stochastic games","citation":{"mla":"Hilbe, Christian, et al. “Evolution of Cooperation in Stochastic Games.” Nature, vol. 559, no. 7713, Nature Publishing Group, 2018, pp. 246–49, doi:10.1038/s41586-018-0277-x.","short":"C. Hilbe, Š. Šimsa, K. Chatterjee, M. Nowak, Nature 559 (2018) 246–249.","ieee":"C. Hilbe, Š. Šimsa, K. Chatterjee, and M. Nowak, “Evolution of cooperation in stochastic games,” Nature, vol. 559, no. 7713. Nature Publishing Group, pp. 246–249, 2018.","ama":"Hilbe C, Šimsa Š, Chatterjee K, Nowak M. Evolution of cooperation in stochastic games. Nature. 2018;559(7713):246-249. doi:10.1038/s41586-018-0277-x","apa":"Hilbe, C., Šimsa, Š., Chatterjee, K., & Nowak, M. (2018). Evolution of cooperation in stochastic games. Nature. Nature Publishing Group. https://doi.org/10.1038/s41586-018-0277-x","chicago":"Hilbe, Christian, Štepán Šimsa, Krishnendu Chatterjee, and Martin Nowak. “Evolution of Cooperation in Stochastic Games.” Nature. Nature Publishing Group, 2018. https://doi.org/10.1038/s41586-018-0277-x.","ista":"Hilbe C, Šimsa Š, Chatterjee K, Nowak M. 2018. Evolution of cooperation in stochastic games. Nature. 559(7713), 246–249."},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","project":[{"name":"Game Theory","grant_number":"S11407","_id":"25863FF4-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425","name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307"},{"call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425","name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23"},{"_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"S 11407_N23","name":"Rigorous Systems Engineering"},{"grant_number":"291734","name":"International IST Postdoc Fellowship Programme","call_identifier":"FP7","_id":"25681D80-B435-11E9-9278-68D0E5697425"}],"issue":"7713","volume":559,"related_material":{"link":[{"description":"News on IST Homepage","relation":"press_release","url":"https://ist.ac.at/en/news/engineering-cooperation/"}]},"ec_funded":1,"publication_status":"published","file":[{"checksum":"011ab905cf9a410bc2b96f15174d654d","file_id":"7049","content_type":"application/pdf","relation":"main_file","access_level":"open_access","file_name":"2018_Nature_Hilbe.pdf","date_created":"2019-11-19T08:09:57Z","file_size":2834442,"date_updated":"2020-07-14T12:45:02Z","creator":"dernst"}],"language":[{"iso":"eng"}],"scopus_import":"1","month":"07","intvolume":" 559","abstract":[{"text":"Social dilemmas occur when incentives for individuals are misaligned with group interests 1-7 . According to the 'tragedy of the commons', these misalignments can lead to overexploitation and collapse of public resources. The resulting behaviours can be analysed with the tools of game theory 8 . The theory of direct reciprocity 9-15 suggests that repeated interactions can alleviate such dilemmas, but previous work has assumed that the public resource remains constant over time. Here we introduce the idea that the public resource is instead changeable and depends on the strategic choices of individuals. An intuitive scenario is that cooperation increases the public resource, whereas defection decreases it. Thus, cooperation allows the possibility of playing a more valuable game with higher payoffs, whereas defection leads to a less valuable game. We analyse this idea using the theory of stochastic games 16-19 and evolutionary game theory. We find that the dependence of the public resource on previous interactions can greatly enhance the propensity for cooperation. For these results, the interaction between reciprocity and payoff feedback is crucial: neither repeated interactions in a constant environment nor single interactions in a changing environment yield similar cooperation rates. Our framework shows which feedbacks between exploitation and environment - either naturally occurring or designed - help to overcome social dilemmas.","lang":"eng"}],"oa_version":"Submitted Version","file_date_updated":"2020-07-14T12:45:02Z","department":[{"_id":"KrCh"}],"date_updated":"2023-09-11T13:43:22Z","ddc":["000"],"type":"journal_article","status":"public","_id":"157"}]