[{"title":"Lecture notes on quantum Brownian motion","author":[{"last_name":"Erdös","full_name":"László Erdös","orcid":"0000-0001-5366-9603","id":"4DBD5372-F248-11E8-B48F-1D18A9856A87","first_name":"László"}],"publist_id":"4196","extern":1,"date_updated":"2021-01-12T06:59:08Z","citation":{"chicago":"Erdös, László. “Lecture Notes on Quantum Brownian Motion,” 95:3–98. Oxford University Press, 2012.","ista":"Erdös L. 2012. Lecture notes on quantum Brownian motion. Les Houches Summer School 2010, Quantum Theory from Small to Large Scales, vol. 95, 3–98.","mla":"Erdös, László. Lecture Notes on Quantum Brownian Motion. Vol. 95, Oxford University Press, 2012, pp. 3–98.","short":"L. Erdös, in:, Oxford University Press, 2012, pp. 3–98.","ieee":"L. Erdös, “Lecture notes on quantum Brownian motion,” presented at the Les Houches Summer School 2010, 2012, vol. 95, pp. 3–98.","ama":"Erdös L. Lecture notes on quantum Brownian motion. In: Vol 95. Oxford University Press; 2012:3-98.","apa":"Erdös, L. (2012). Lecture notes on quantum Brownian motion (Vol. 95, pp. 3–98). Presented at the Les Houches Summer School 2010, Oxford University Press."},"status":"public","type":"conference","conference":{"name":"Les Houches Summer School 2010"},"_id":"2700","volume":95,"date_published":"2012-05-24T00:00:00Z","date_created":"2018-12-11T11:59:08Z","page":"3 - 98","day":"24","year":"2012","publication_status":"published","month":"05","intvolume":" 95","quality_controlled":0,"alternative_title":["Quantum Theory from Small to Large Scales"],"publisher":"Oxford University Press","oa":1,"main_file_link":[{"url":"http://arxiv.org/abs/1009.0843","open_access":"1"}]},{"title":"Average case analysis of the classical algorithm for Markov decision processes with Büchi objectives","author":[{"first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"last_name":"Joglekar","full_name":"Joglekar, Manas","first_name":"Manas"},{"full_name":"Shah, Nisarg","last_name":"Shah","first_name":"Nisarg"}],"publist_id":"4180","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","citation":{"ista":"Chatterjee K, Joglekar M, Shah N. 2012. Average case analysis of the classical algorithm for Markov decision processes with Büchi objectives. FSTTCS: Foundations of Software Technology and Theoretical Computer Science, LIPIcs, vol. 18, 461–473.","chicago":"Chatterjee, Krishnendu, Manas Joglekar, and Nisarg Shah. “Average Case Analysis of the Classical Algorithm for Markov Decision Processes with Büchi Objectives,” 18:461–73. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2012. https://doi.org/10.4230/LIPIcs.FSTTCS.2012.461.","short":"K. Chatterjee, M. Joglekar, N. Shah, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2012, pp. 461–473.","ieee":"K. Chatterjee, M. Joglekar, and N. Shah, “Average case analysis of the classical algorithm for Markov decision processes with Büchi objectives,” presented at the FSTTCS: Foundations of Software Technology and Theoretical Computer Science, Hyderabad, India, 2012, vol. 18, pp. 461–473.","ama":"Chatterjee K, Joglekar M, Shah N. Average case analysis of the classical algorithm for Markov decision processes with Büchi objectives. In: Vol 18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2012:461-473. doi:10.4230/LIPIcs.FSTTCS.2012.461","apa":"Chatterjee, K., Joglekar, M., & Shah, N. (2012). Average case analysis of the classical algorithm for Markov decision processes with Büchi objectives (Vol. 18, pp. 461–473). Presented at the FSTTCS: Foundations of Software Technology and Theoretical Computer Science, Hyderabad, India: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.FSTTCS.2012.461","mla":"Chatterjee, Krishnendu, et al. Average Case Analysis of the Classical Algorithm for Markov Decision Processes with Büchi Objectives. Vol. 18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2012, pp. 461–73, doi:10.4230/LIPIcs.FSTTCS.2012.461."},"project":[{"grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification","_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"call_identifier":"FWF","_id":"25863FF4-B435-11E9-9278-68D0E5697425","name":"Game Theory","grant_number":"S11407"},{"name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"date_published":"2012-12-10T00:00:00Z","doi":"10.4230/LIPIcs.FSTTCS.2012.461","date_created":"2018-12-11T11:59:13Z","page":"461 - 473","day":"10","has_accepted_license":"1","year":"2012","quality_controlled":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","oa":1,"file_date_updated":"2020-07-14T12:45:45Z","department":[{"_id":"KrCh"}],"ddc":["000"],"date_updated":"2023-02-23T10:06:04Z","status":"public","pubrep_id":"525","type":"conference","tmp":{"short":"CC BY-NC-ND (4.0)","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","image":"/images/cc_by_nc_nd.png"},"conference":{"name":"FSTTCS: Foundations of Software Technology and Theoretical Computer Science","end_date":"2012-12-17","location":"Hyderabad, India","start_date":"2012-12-15"},"_id":"2715","volume":18,"related_material":{"record":[{"relation":"later_version","id":"1598","status":"public"}]},"ec_funded":1,"license":"https://creativecommons.org/licenses/by-nc-nd/4.0/","file":[{"content_type":"application/pdf","access_level":"open_access","relation":"main_file","file_id":"5040","checksum":"d4d644ed1a885dbfc4fa1ef4c5724dab","date_updated":"2020-07-14T12:45:45Z","file_size":519040,"creator":"system","date_created":"2018-12-12T10:13:53Z","file_name":"IST-2016-525-v1+1_42_1_.pdf"}],"language":[{"iso":"eng"}],"publication_status":"published","month":"12","intvolume":" 18","scopus_import":1,"alternative_title":["LIPIcs"],"oa_version":"Published Version","abstract":[{"lang":"eng","text":"We consider Markov decision processes (MDPs) with specifications given as Büchi (liveness) objectives. We consider the problem of computing the set of almost-sure winning vertices from where the objective can be ensured with probability 1. We study for the first time the average case complexity of the classical algorithm for computing the set of almost-sure winning vertices for MDPs with Büchi objectives. Our contributions are as follows: First, we show that for MDPs with constant out-degree the expected number of iterations is at most logarithmic and the average case running time is linear (as compared to the worst case linear number of iterations and quadratic time complexity). Second, for the average case analysis over all MDPs we show that the expected number of iterations is constant and the average case running time is linear (again as compared to the worst case linear number of iterations and quadratic time complexity). Finally we also show that given that all MDPs are equally likely, the probability that the classical algorithm requires more than constant number of iterations is exponentially small."}]},{"quality_controlled":"1","publisher":"Springer","acknowledgement":"Author supported by Austrian Science Fund (FWF) Grant No P 23499-N23, FWF NFN Grant No S11407 (RiSE), ERC Start Grant (279307: Graph Games), Microsoft faculty fellowship.","page":"115-131","doi":"10.1007/978-3-642-32940-1_10","date_published":"2012-09-15T00:00:00Z","date_created":"2022-03-21T08:00:21Z","year":"2012","day":"15","publication":"CONCUR 2012 - Concurrency Theory","project":[{"grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification","_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"grant_number":"S11407","name":"Game Theory","call_identifier":"FWF","_id":"25863FF4-B435-11E9-9278-68D0E5697425"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"author":[{"orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Mickael","last_name":"Randour","full_name":"Randour, Mickael"},{"last_name":"Raskin","full_name":"Raskin, Jean-François","first_name":"Jean-François"}],"external_id":{"arxiv":["1201.5073"]},"article_processing_charge":"No","title":"Strategy synthesis for multi-dimensional quantitative objectives","editor":[{"last_name":"Koutny","full_name":"Koutny, Maciej","first_name":"Maciej"},{"last_name":"Ulidowski","full_name":"Ulidowski, Irek","first_name":"Irek"}],"citation":{"mla":"Chatterjee, Krishnendu, et al. “Strategy Synthesis for Multi-Dimensional Quantitative Objectives.” CONCUR 2012 - Concurrency Theory, edited by Maciej Koutny and Irek Ulidowski, vol. 7454, Springer, 2012, pp. 115–31, doi:10.1007/978-3-642-32940-1_10.","ama":"Chatterjee K, Randour M, Raskin J-F. Strategy synthesis for multi-dimensional quantitative objectives. In: Koutny M, Ulidowski I, eds. CONCUR 2012 - Concurrency Theory. Vol 7454. Berlin, Heidelberg: Springer; 2012:115-131. doi:10.1007/978-3-642-32940-1_10","apa":"Chatterjee, K., Randour, M., & Raskin, J.-F. (2012). Strategy synthesis for multi-dimensional quantitative objectives. In M. Koutny & I. Ulidowski (Eds.), CONCUR 2012 - Concurrency Theory (Vol. 7454, pp. 115–131). Berlin, Heidelberg: Springer. https://doi.org/10.1007/978-3-642-32940-1_10","short":"K. Chatterjee, M. Randour, J.-F. Raskin, in:, M. Koutny, I. Ulidowski (Eds.), CONCUR 2012 - Concurrency Theory, Springer, Berlin, Heidelberg, 2012, pp. 115–131.","ieee":"K. Chatterjee, M. Randour, and J.-F. Raskin, “Strategy synthesis for multi-dimensional quantitative objectives,” in CONCUR 2012 - Concurrency Theory, Newcastle upon Tyne, United Kingdom, 2012, vol. 7454, pp. 115–131.","chicago":"Chatterjee, Krishnendu, Mickael Randour, and Jean-François Raskin. “Strategy Synthesis for Multi-Dimensional Quantitative Objectives.” In CONCUR 2012 - Concurrency Theory, edited by Maciej Koutny and Irek Ulidowski, 7454:115–31. Berlin, Heidelberg: Springer, 2012. https://doi.org/10.1007/978-3-642-32940-1_10.","ista":"Chatterjee K, Randour M, Raskin J-F. 2012. Strategy synthesis for multi-dimensional quantitative objectives. CONCUR 2012 - Concurrency Theory. CONCUR: Conference on Concurrency Theory, LNCS, vol. 7454, 115–131."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","alternative_title":["LNCS"],"scopus_import":"1","month":"09","place":"Berlin, Heidelberg","intvolume":" 7454","abstract":[{"lang":"eng","text":"Multi-dimensional mean-payoff and energy games provide the mathematical foundation for the quantitative study of reactive systems, and play a central role in the emerging quantitative theory of verification and synthesis. In this work, we study the strategy synthesis problem for games with such multi-dimensional objectives along with a parity condition, a canonical way to express ω-regular conditions. While in general, the winning strategies in such games may require infinite memory, for synthesis the most relevant problem is the construction of a finite-memory winning strategy (if one exists). Our main contributions are as follows. First, we show a tight exponential bound (matching upper and lower bounds) on the memory required for finite-memory winning strategies in both multi-dimensional mean-payoff and energy games along with parity objectives. This significantly improves the triple exponential upper bound for multi energy games (without parity) that could be derived from results in literature for games on VASS (vector addition systems with states). Second, we present an optimal symbolic and incremental algorithm to compute a finite-memory winning strategy (if one exists) in such games. Finally, we give a complete characterization of when finite memory of strategies can be traded off for randomness. In particular, we show that for one-dimension mean-payoff parity games, randomized memoryless strategies are as powerful as their pure finite-memory counterparts."}],"oa_version":"Preprint","volume":7454,"related_material":{"record":[{"relation":"later_version","status":"public","id":"2716"}]},"ec_funded":1,"publication_identifier":{"issn":["0302-9743","1611-3349"],"isbn":["9783642329395"],"eisbn":["9783642329401"]},"publication_status":"published","language":[{"iso":"eng"}],"type":"conference","conference":{"location":"Newcastle upon Tyne, United Kingdom","end_date":"2012-09-07","start_date":"2012-09-04","name":"CONCUR: Conference on Concurrency Theory"},"status":"public","_id":"10904","department":[{"_id":"KrCh"}],"date_updated":"2023-02-23T10:55:06Z"},{"abstract":[{"text":"Consider N×N Hermitian or symmetric random matrices H with independent entries, where the distribution of the (i,j) matrix element is given by the probability measure vij with zero expectation and with variance σ ιj 2. We assume that the variances satisfy the normalization condition Σiσij2=1 for all j and that there is a positive constant c such that c≤Nσ ιj 2 ιc -1. We further assume that the probability distributions νij have a uniform subexponential decay. We prove that the Stieltjes transform of the empirical eigenvalue distribution of H is given by the Wigner semicircle law uniformly up to the edges of the spectrum with an error of order (Nη) -1 where η is the imaginary part of the spectral parameter in the Stieltjes transform. There are three corollaries to this strong local semicircle law: (1) Rigidity of eigenvalues: If γj=γj,N denotes the classical location of the j-th eigenvalue under the semicircle law ordered in increasing order, then the j-th eigenvalue λj is close to γj in the sense that for some positive constants C, c P{double-struck}(∃j:|λ j-γ j|≥(logN) CloglogN[min(j,N-j+1)] -1/3N -2/3)≤ C exp[-(logN) cloglogN] for N large enough. (2) The proof of Dyson's conjecture (Dyson, 1962 [15]) which states that the time scale of the Dyson Brownian motion to reach local equilibrium is of order N -1 up to logarithmic corrections. (3) The edge universality holds in the sense that the probability distributions of the largest (and the smallest) eigenvalues of two generalized Wigner ensembles are the same in the large N limit provided that the second moments of the two ensembles are identical.","lang":"eng"}],"quality_controlled":0,"publisher":"Academic Press","intvolume":" 229","month":"02","year":"2012","publication_status":"published","publication":"Advances in Mathematics","day":"15","page":"1435 - 1515","date_created":"2018-12-11T11:59:30Z","date_published":"2012-02-15T00:00:00Z","doi":"10.1016/j.aim.2011.12.010","issue":"3","volume":229,"_id":"2770","type":"journal_article","status":"public","citation":{"short":"L. Erdös, H. Yau, J. Yin, Advances in Mathematics 229 (2012) 1435–1515.","ieee":"L. Erdös, H. Yau, and J. Yin, “Rigidity of eigenvalues of generalized Wigner matrices,” Advances in Mathematics, vol. 229, no. 3. Academic Press, pp. 1435–1515, 2012.","apa":"Erdös, L., Yau, H., & Yin, J. (2012). Rigidity of eigenvalues of generalized Wigner matrices. Advances in Mathematics. Academic Press. https://doi.org/10.1016/j.aim.2011.12.010","ama":"Erdös L, Yau H, Yin J. Rigidity of eigenvalues of generalized Wigner matrices. Advances in Mathematics. 2012;229(3):1435-1515. doi:10.1016/j.aim.2011.12.010","mla":"Erdös, László, et al. “Rigidity of Eigenvalues of Generalized Wigner Matrices.” Advances in Mathematics, vol. 229, no. 3, Academic Press, 2012, pp. 1435–515, doi:10.1016/j.aim.2011.12.010.","ista":"Erdös L, Yau H, Yin J. 2012. Rigidity of eigenvalues of generalized Wigner matrices. Advances in Mathematics. 229(3), 1435–1515.","chicago":"Erdös, László, Horng Yau, and Jun Yin. “Rigidity of Eigenvalues of Generalized Wigner Matrices.” Advances in Mathematics. Academic Press, 2012. https://doi.org/10.1016/j.aim.2011.12.010."},"date_updated":"2021-01-12T06:59:35Z","extern":1,"author":[{"full_name":"László Erdös","orcid":"0000-0001-5366-9603","last_name":"Erdös","first_name":"László","id":"4DBD5372-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Horng","full_name":"Yau, Horng-Tzer","last_name":"Yau"},{"first_name":"Jun","last_name":"Yin","full_name":"Yin, Jun"}],"publist_id":"4120","title":"Rigidity of eigenvalues of generalized Wigner matrices"},{"status":"public","type":"journal_article","_id":"2769","title":"The local relaxation flow approach to universality of the local statistics for random matrices","publist_id":"4121","author":[{"id":"4DBD5372-F248-11E8-B48F-1D18A9856A87","first_name":"László","last_name":"Erdös","orcid":"0000-0001-5366-9603","full_name":"László Erdös"},{"last_name":"Schlein","full_name":"Schlein, Benjamin","first_name":"Benjamin"},{"first_name":"Horng","last_name":"Yau","full_name":"Yau, Horng-Tzer"},{"full_name":"Yin, Jun","last_name":"Yin","first_name":"Jun"}],"extern":1,"date_updated":"2021-01-12T06:59:34Z","citation":{"short":"L. Erdös, B. Schlein, H. Yau, J. Yin, Annales de l’institut Henri Poincare (B) Probability and Statistics 48 (2012) 1–46.","ieee":"L. Erdös, B. Schlein, H. Yau, and J. Yin, “The local relaxation flow approach to universality of the local statistics for random matrices,” Annales de l’institut Henri Poincare (B) Probability and Statistics, vol. 48, no. 1. Institute of Mathematical Statistics, pp. 1–46, 2012.","ama":"Erdös L, Schlein B, Yau H, Yin J. The local relaxation flow approach to universality of the local statistics for random matrices. Annales de l’institut Henri Poincare (B) Probability and Statistics. 2012;48(1):1-46. doi:10.1214/10-AIHP388","apa":"Erdös, L., Schlein, B., Yau, H., & Yin, J. (2012). The local relaxation flow approach to universality of the local statistics for random matrices. Annales de l’institut Henri Poincare (B) Probability and Statistics. Institute of Mathematical Statistics. https://doi.org/10.1214/10-AIHP388","mla":"Erdös, László, et al. “The Local Relaxation Flow Approach to Universality of the Local Statistics for Random Matrices.” Annales de l’institut Henri Poincare (B) Probability and Statistics, vol. 48, no. 1, Institute of Mathematical Statistics, 2012, pp. 1–46, doi:10.1214/10-AIHP388.","ista":"Erdös L, Schlein B, Yau H, Yin J. 2012. The local relaxation flow approach to universality of the local statistics for random matrices. Annales de l’institut Henri Poincare (B) Probability and Statistics. 48(1), 1–46.","chicago":"Erdös, László, Benjamin Schlein, Horng Yau, and Jun Yin. “The Local Relaxation Flow Approach to Universality of the Local Statistics for Random Matrices.” Annales de l’institut Henri Poincare (B) Probability and Statistics. Institute of Mathematical Statistics, 2012. https://doi.org/10.1214/10-AIHP388."},"intvolume":" 48","month":"02","publisher":"Institute of Mathematical Statistics","quality_controlled":0,"abstract":[{"lang":"eng","text":"We present a generalization of the method of the local relaxation flow to establish the universality of local spectral statistics of a broad class of large random matrices. We show that the local distribution of the eigenvalues coincides with the local statistics of the corresponding Gaussian ensemble provided the distribution of the individual matrix element is smooth and the eigenvalues {X J} N j=1 are close to their classical location {y j} N j=1 determined by the limiting density of eigenvalues. Under the scaling where the typical distance between neighboring eigenvalues is of order 1/N, the necessary apriori estimate on the location of eigenvalues requires only to know that E|x j - γ j| 2 ≤ N-1-ε on average. This information can be obtained by well established methods for various matrix ensembles. We demonstrate the method by proving local spectral universality for sample covariance matrices."}],"date_created":"2018-12-11T11:59:30Z","date_published":"2012-02-01T00:00:00Z","issue":"1","doi":"10.1214/10-AIHP388","volume":48,"page":"1 - 46","publication":"Annales de l'institut Henri Poincare (B) Probability and Statistics","day":"01","publication_status":"published","year":"2012"}]