[{"scopus_import":"1","day":"15","article_processing_charge":"No","page":"115-131","publication":"CONCUR 2012 - Concurrency Theory","citation":{"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.","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.","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.","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.","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","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.","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"},"date_published":"2012-09-15T00:00:00Z","alternative_title":["LNCS"],"type":"conference","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."}],"title":"Strategy synthesis for multi-dimensional quantitative objectives","status":"public","intvolume":" 7454","_id":"10904","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Preprint","month":"09","publication_identifier":{"issn":["0302-9743","1611-3349"],"eisbn":["9783642329401"],"isbn":["9783642329395"]},"quality_controlled":"1","project":[{"_id":"2584A770-B435-11E9-9278-68D0E5697425","grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification","call_identifier":"FWF"},{"_id":"25863FF4-B435-11E9-9278-68D0E5697425","grant_number":"S11407","name":"Game Theory","call_identifier":"FWF"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"external_id":{"arxiv":["1201.5073"]},"language":[{"iso":"eng"}],"conference":{"name":"CONCUR: Conference on Concurrency Theory","end_date":"2012-09-07","start_date":"2012-09-04","location":"Newcastle upon Tyne, United Kingdom"},"doi":"10.1007/978-3-642-32940-1_10","place":"Berlin, Heidelberg","ec_funded":1,"publication_status":"published","editor":[{"last_name":"Koutny","first_name":"Maciej","full_name":"Koutny, Maciej"},{"first_name":"Irek","last_name":"Ulidowski","full_name":"Ulidowski, Irek"}],"publisher":"Springer","department":[{"_id":"KrCh"}],"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.","year":"2012","date_updated":"2023-02-23T10:55:06Z","date_created":"2022-03-21T08:00:21Z","volume":7454,"author":[{"full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X"},{"full_name":"Randour, Mickael","last_name":"Randour","first_name":"Mickael"},{"full_name":"Raskin, Jean-François","first_name":"Jean-François","last_name":"Raskin"}],"related_material":{"record":[{"id":"2716","relation":"later_version","status":"public"}]}},{"page":"1435 - 1515","quality_controlled":0,"citation":{"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","ista":"Erdös L, Yau H, Yin J. 2012. Rigidity of eigenvalues of generalized Wigner matrices. Advances in Mathematics. 229(3), 1435–1515.","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","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.","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.","short":"L. Erdös, H. Yau, J. Yin, Advances in Mathematics 229 (2012) 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."},"publication":"Advances in Mathematics","date_published":"2012-02-15T00:00:00Z","doi":"10.1016/j.aim.2011.12.010","month":"02","day":"15","intvolume":" 229","publisher":"Academic Press","status":"public","publication_status":"published","title":"Rigidity of eigenvalues of generalized Wigner matrices","year":"2012","_id":"2770","volume":229,"date_updated":"2021-01-12T06:59:35Z","date_created":"2018-12-11T11:59:30Z","author":[{"first_name":"László","last_name":"Erdös","id":"4DBD5372-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-5366-9603","full_name":"László Erdös"},{"last_name":"Yau","first_name":"Horng","full_name":"Yau, Horng-Tzer"},{"last_name":"Yin","first_name":"Jun","full_name":"Yin, Jun"}],"type":"journal_article","extern":1,"publist_id":"4120","issue":"3","abstract":[{"lang":"eng","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."}]},{"publication_status":"published","title":"The local relaxation flow approach to universality of the local statistics for random matrices","status":"public","publisher":"Institute of Mathematical Statistics","intvolume":" 48","year":"2012","_id":"2769","date_created":"2018-12-11T11:59:30Z","date_updated":"2021-01-12T06:59:34Z","volume":48,"author":[{"full_name":"László Erdös","last_name":"Erdös","first_name":"László","orcid":"0000-0001-5366-9603","id":"4DBD5372-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Schlein, Benjamin","last_name":"Schlein","first_name":"Benjamin"},{"full_name":"Yau, Horng-Tzer","last_name":"Yau","first_name":"Horng"},{"full_name":"Yin, Jun","first_name":"Jun","last_name":"Yin"}],"type":"journal_article","extern":1,"abstract":[{"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.","lang":"eng"}],"issue":"1","publist_id":"4121","quality_controlled":0,"page":"1 - 46","publication":"Annales de l'institut Henri Poincare (B) Probability and Statistics","citation":{"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","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.","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","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.","short":"L. Erdös, B. Schlein, H. Yau, J. Yin, Annales de l’institut Henri Poincare (B) Probability and Statistics 48 (2012) 1–46.","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.","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."},"date_published":"2012-02-01T00:00:00Z","doi":"10.1214/10-AIHP388","month":"02","day":"01"},{"author":[{"orcid":"0000-0001-5366-9603","id":"4DBD5372-F248-11E8-B48F-1D18A9856A87","last_name":"Erdös","first_name":"László","full_name":"László Erdös"},{"last_name":"Yau","first_name":"Horng","full_name":"Yau, Horng-Tzer"},{"first_name":"Jun","last_name":"Yin","full_name":"Yin, Jun"}],"volume":154,"date_updated":"2021-01-12T06:59:33Z","date_created":"2018-12-11T11:59:29Z","_id":"2767","year":"2012","publisher":"Springer","intvolume":" 154","title":"Bulk universality for generalized Wigner matrices","status":"public","publication_status":"published","issue":"1-2","publist_id":"4123","abstract":[{"lang":"eng","text":"Consider N × N Hermitian or symmetric random matrices H where the distribution of the (i, j) matrix element is given by a probability measure ν ij with a subexponential decay. Let σ ij 2 be the variance for the probability measure ν ij with the normalization property that Σ iσ i,j 2 = 1 for all j. Under essentially the only condition that c ≤ N σ ij 2 ≤ c -1 for some constant c > 0, we prove that, in the limit N → ∞, the eigenvalue spacing statistics of H in the bulk of the spectrum coincide with those of the Gaussian unitary or orthogonal ensemble (GUE or GOE). We also show that for band matrices with bandwidth M the local semicircle law holds to the energy scale M -1. "}],"extern":1,"type":"journal_article","doi":"10.1007/s00440-011-0390-3","date_published":"2012-10-01T00:00:00Z","citation":{"ama":"Erdös L, Yau H, Yin J. Bulk universality for generalized Wigner matrices. Probability Theory and Related Fields. 2012;154(1-2):341-407. doi:10.1007/s00440-011-0390-3","ieee":"L. Erdös, H. Yau, and J. Yin, “Bulk universality for generalized Wigner matrices,” Probability Theory and Related Fields, vol. 154, no. 1–2. Springer, pp. 341–407, 2012.","apa":"Erdös, L., Yau, H., & Yin, J. (2012). Bulk universality for generalized Wigner matrices. Probability Theory and Related Fields. Springer. https://doi.org/10.1007/s00440-011-0390-3","ista":"Erdös L, Yau H, Yin J. 2012. Bulk universality for generalized Wigner matrices. Probability Theory and Related Fields. 154(1–2), 341–407.","short":"L. Erdös, H. Yau, J. Yin, Probability Theory and Related Fields 154 (2012) 341–407.","mla":"Erdös, László, et al. “Bulk Universality for Generalized Wigner Matrices.” Probability Theory and Related Fields, vol. 154, no. 1–2, Springer, 2012, pp. 341–407, doi:10.1007/s00440-011-0390-3.","chicago":"Erdös, László, Horng Yau, and Jun Yin. “Bulk Universality for Generalized Wigner Matrices.” Probability Theory and Related Fields. Springer, 2012. https://doi.org/10.1007/s00440-011-0390-3."},"publication":"Probability Theory and Related Fields","page":"341 - 407","quality_controlled":0,"month":"10","day":"01"},{"day":"01","month":"01","date_published":"2012-01-01T00:00:00Z","doi":"10.1007/s00220-011-1373-z","quality_controlled":0,"page":"507 - 542","publication":"Communications in Mathematical Physics","citation":{"ista":"Erdös L, Hasler D. 2012. Wegner estimate and Anderson localization for random magnetic fields. Communications in Mathematical Physics. 309(2), 507–542.","ieee":"L. Erdös and D. Hasler, “Wegner estimate and Anderson localization for random magnetic fields,” Communications in Mathematical Physics, vol. 309, no. 2. Springer, pp. 507–542, 2012.","apa":"Erdös, L., & Hasler, D. (2012). Wegner estimate and Anderson localization for random magnetic fields. Communications in Mathematical Physics. Springer. https://doi.org/10.1007/s00220-011-1373-z","ama":"Erdös L, Hasler D. Wegner estimate and Anderson localization for random magnetic fields. Communications in Mathematical Physics. 2012;309(2):507-542. doi:10.1007/s00220-011-1373-z","chicago":"Erdös, László, and David Hasler. “Wegner Estimate and Anderson Localization for Random Magnetic Fields.” Communications in Mathematical Physics. Springer, 2012. https://doi.org/10.1007/s00220-011-1373-z.","mla":"Erdös, László, and David Hasler. “Wegner Estimate and Anderson Localization for Random Magnetic Fields.” Communications in Mathematical Physics, vol. 309, no. 2, Springer, 2012, pp. 507–42, doi:10.1007/s00220-011-1373-z.","short":"L. Erdös, D. Hasler, Communications in Mathematical Physics 309 (2012) 507–542."},"extern":1,"abstract":[{"lang":"eng","text":"We consider a two dimensional magnetic Schrödinger operator with a spatially stationary random magnetic field. We assume that the magnetic field has a positive lower bound and that it has Fourier modes on arbitrarily short scales. We prove the Wegner estimate at arbitrary energy, i. e. we show that the averaged density of states is finite throughout the whole spectrum. We also prove Anderson localization at the bottom of the spectrum."}],"publist_id":"4122","issue":"2","type":"journal_article","date_created":"2018-12-11T11:59:30Z","date_updated":"2021-01-12T06:59:34Z","volume":309,"author":[{"full_name":"László Erdös","first_name":"László","last_name":"Erdös","id":"4DBD5372-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-5366-9603"},{"full_name":"Hasler, David G","first_name":"David","last_name":"Hasler"}],"status":"public","title":"Wegner estimate and Anderson localization for random magnetic fields","publication_status":"published","publisher":"Springer","intvolume":" 309","_id":"2768","year":"2012"}]