@inproceedings{2700, author = {László Erdös}, pages = {3 -- 98}, publisher = {Oxford University Press}, title = {{Lecture notes on quantum Brownian motion}}, volume = {95}, year = {2012}, } @inproceedings{2715, abstract = {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.}, author = {Chatterjee, Krishnendu and Joglekar, Manas and Shah, Nisarg}, location = {Hyderabad, India}, pages = {461 -- 473}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Average case analysis of the classical algorithm for Markov decision processes with Büchi objectives}}, doi = {10.4230/LIPIcs.FSTTCS.2012.461}, volume = {18}, year = {2012}, } @inproceedings{10904, abstract = {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.}, author = {Chatterjee, Krishnendu and Randour, Mickael and Raskin, Jean-François}, booktitle = {CONCUR 2012 - Concurrency Theory}, editor = {Koutny, Maciej and Ulidowski, Irek}, isbn = {9783642329395}, issn = {0302-9743}, location = {Newcastle upon Tyne, United Kingdom}, pages = {115--131}, publisher = {Springer}, title = {{Strategy synthesis for multi-dimensional quantitative objectives}}, doi = {10.1007/978-3-642-32940-1_10}, volume = {7454}, year = {2012}, } @article{2770, abstract = {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.}, author = {László Erdös and Yau, Horng-Tzer and Yin, Jun}, journal = {Advances in Mathematics}, number = {3}, pages = {1435 -- 1515}, publisher = {Academic Press}, title = {{Rigidity of eigenvalues of generalized Wigner matrices}}, doi = {10.1016/j.aim.2011.12.010}, volume = {229}, year = {2012}, } @article{2769, abstract = {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.}, author = {László Erdös and Schlein, Benjamin and Yau, Horng-Tzer and Yin, Jun}, journal = {Annales de l'institut Henri Poincare (B) Probability and Statistics}, number = {1}, pages = {1 -- 46}, publisher = {Institute of Mathematical Statistics}, title = {{The local relaxation flow approach to universality of the local statistics for random matrices}}, doi = {10.1214/10-AIHP388}, volume = {48}, year = {2012}, } @article{2767, abstract = {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. }, author = {László Erdös and Yau, Horng-Tzer and Yin, Jun}, journal = {Probability Theory and Related Fields}, number = {1-2}, pages = {341 -- 407}, publisher = {Springer}, title = {{Bulk universality for generalized Wigner matrices}}, doi = {10.1007/s00440-011-0390-3}, volume = {154}, year = {2012}, } @article{2768, abstract = {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.}, author = {László Erdös and Hasler, David G}, journal = {Communications in Mathematical Physics}, number = {2}, pages = {507 -- 542}, publisher = {Springer}, title = {{Wegner estimate and Anderson localization for random magnetic fields}}, doi = {10.1007/s00220-011-1373-z}, volume = {309}, year = {2012}, } @article{2775, abstract = {The Wigner-Dyson-Gaudin-Mehta conjecture asserts that the local eigenvalue statistics of large random matrices exhibit universal behavior depending only on the symmetry class of the matrix ensemble. For invariant matrix models, the eigenvalue distributions are given by a log-gas with potential V and inverse temperature β = 1, 2, 4, corresponding to the orthogonal, unitary and symplectic ensembles. For β ∉ {1, 2, 4}, there is no natural random matrix ensemble behind this model, but the statistical physics interpretation of the log-gas is still valid for all β > 0. The universality conjecture for invariant ensembles asserts that the local eigenvalue statistics are independent of V. In this article, we review our recent solution to the universality conjecture for both invariant and non-invariant ensembles. We will also demonstrate that the local ergodicity of the Dyson Brownian motion is the intrinsic mechanism behind the universality. Furthermore, we review the solution of Dyson's conjecture on the local relaxation time of the Dyson Brownian motion. Related questions such as delocalization of eigenvectors and local version of Wigner's semicircle law will also be discussed.}, author = {László Erdös and Yau, Horng-Tzer}, journal = {Bulletin of the American Mathematical Society}, number = {3}, pages = {377 -- 414}, publisher = {American Mathematical Society}, title = {{Universality of local spectral statistics of random matrices}}, doi = {10.1090/S0273-0979-2012-01372-1}, volume = {49}, year = {2012}, } @article{2777, abstract = {We consider a large neutral molecule with total nuclear charge Z in a model with self-generated classical magnetic field and where the kinetic energy of the electrons is treated relativistically. To ensure stability, we assume that Zα < 2/π, where α denotes the fine structure constant. We are interested in the ground state energy in the simultaneous limit Z → ∞, α → 0 such that κ = Zα is fixed. The leading term in the energy asymptotics is independent of κ, it is given by the Thomas-Fermi energy of order Z7/3 and it is unchanged by including the self-generated magnetic field. We prove the first correction term to this energy, the so-called Scott correction of the form S(αZ)Z2. The current paper extends the result of Solovej et al. [Commun. Pure Appl. Math.LXIII, 39-118 (2010)] on the Scott correction for relativistic molecules to include a self-generated magnetic field. Furthermore, we show that the corresponding Scott correction function S, first identified by Solovej et al. [Commun. Pure Appl. Math.LXIII, 39-118 (2010)], is unchanged by including a magnetic field. We also prove new Lieb-Thirring inequalities for the relativistic kinetic energy with magnetic fields.}, author = {László Erdös and Fournais, Søren and Solovej, Jan P}, journal = {Journal of Mathematical Physics}, number = {9}, publisher = {American Institute of Physics}, title = {{Relativistic Scott correction in self-generated magnetic fields}}, doi = {10.1063/1.3697417}, volume = {53}, year = {2012}, } @article{2772, abstract = {We consider the semiclassical asymptotics of the sum of negative eigenvalues of the three-dimensional Pauli operator with an external potential and a self-generated magnetic field B. We also add the field energy β ∫ B 2 and we minimize over all magnetic fields. The parameter β effectively determines the strength of the field. We consider the weak field regime with βh 2 ≥ const > 0, where h is the semiclassical parameter. For smooth potentials we prove that the semiclassical asymptotics of the total energy is given by the non-magnetic Weyl term to leading order with an error bound that is smaller by a factor h 1+e{open}, i. e. the subleading term vanishes. However for potentials with a Coulomb singularity, the subleading term does not vanish due to the non-semiclassical effect of the singularity. Combined with a multiscale technique, this refined estimate is used in the companion paper (Erdo{double acute}s et al. in Scott correction for large molecules with a self-generated magnetic field, Preprint, 2011) to prove the second order Scott correction to the ground state energy of large atoms and molecules.}, author = {László Erdös and Fournais, Søren and Solovej, Jan P}, journal = {Annales Henri Poincare}, number = {4}, pages = {671 -- 730}, publisher = {Birkhäuser}, title = {{Second order semiclassics with self generated magnetic fields}}, doi = {10.1007/s00023-011-0150-z}, volume = {13}, year = {2012}, } @article{2776, abstract = {We consider the ensemble of adjacency matrices of Erdős-Rényi random graphs, i.e. graphs on N vertices where every edge is chosen independently and with probability p ≡ p(N). We rescale the matrix so that its bulk eigenvalues are of order one. Under the assumption pN≫N2/3 , we prove the universality of eigenvalue distributions both in the bulk and at the edge of the spectrum. More precisely, we prove (1) that the eigenvalue spacing of the Erdős-Rényi graph in the bulk of the spectrum has the same distribution as that of the Gaussian orthogonal ensemble; and (2) that the second largest eigenvalue of the Erdős-Rényi graph has the same distribution as the largest eigenvalue of the Gaussian orthogonal ensemble. As an application of our method, we prove the bulk universality of generalized Wigner matrices under the assumption that the matrix entries have at least 4 + ε moments.}, author = {László Erdös and Knowles, Antti and Yau, Horng-Tzer and Yin, Jun}, journal = {Communications in Mathematical Physics}, number = {3}, pages = {587 -- 640}, publisher = {Springer}, title = {{Spectral statistics of Erdős-Rényi graphs II: Eigenvalue spacing and the extreme eigenvalues}}, doi = {10.1007/s00220-012-1527-7}, volume = {314}, year = {2012}, } @article{2774, abstract = {We consider a large neutral molecule with total nuclear charge Z in non-relativistic quantum mechanics with a self-generated classical electromagnetic field. To ensure stability, we assume that Zα 2 ≤ κ 0 for a sufficiently small κ 0, where α denotes the fine structure constant. We show that, in the simultaneous limit Z → ∞, α → 0 such that κ = Zα 2 is fixed, the ground state energy of the system is given by a two term expansion c 1Z 7/3 + c 2(κ) Z 2 + o(Z 2). The leading term is given by the non-magnetic Thomas-Fermi theory. Our result shows that the magnetic field affects only the second (so-called Scott) term in the expansion.}, author = {László Erdös and Fournais, Søren and Solovej, Jan P}, journal = {Communications in Mathematical Physics}, number = {3}, pages = {847 -- 882}, publisher = {Springer}, title = {{Scott correction for large atoms and molecules in a self-generated magnetic field}}, doi = {10.1007/s00220-012-1468-1}, volume = {312}, year = {2012}, } @article{2773, abstract = {Recently we proved [3, 4, 6, 7, 9, 10, 11] that the eigenvalue correlation functions of a general class of random matrices converge, weakly with respect to the energy, to the corresponding ones of Gaussian matrices. Tao and Vu [15] gave a proof that for the special case of Hermitian Wigner matrices the convergence can be strengthened to vague convergence at any fixed energy in the bulk. In this article we show that this theorem is an immediate corollary of our earlier results. Indeed, a more general form of this theorem also follows directly from our work [2].}, author = {László Erdös and Yau, Horng-Tzer}, journal = {Electronic Journal of Probability}, publisher = {Institute of Mathematical Statistics}, title = {{A comment on the Wigner-Dyson-Mehta bulk universality conjecture for Wigner matrices}}, doi = {10.1214/EJP.v17-1779}, volume = {17}, year = {2012}, } @article{2771, abstract = {We consider a magnetic Schrödinger operator in two dimensions. The magnetic field is given as the sum of a large and constant magnetic field and a random magnetic field. Moreover, we allow for an additional deterministic potential as well as a magnetic field which are both periodic. We show that the spectrum of this operator is contained in broadened bands around the Landau levels and that the edges of these bands consist of pure point spectrum with exponentially decaying eigenfunctions. The proof is based on a recent Wegner estimate obtained in Erdos and Hasler (Commun. Math. Phys., preprint, arXiv:1012.5185) and a multiscale analysis.}, author = {László Erdös and Hasler, David G}, journal = {Journal of Statistical Physics}, number = {5}, pages = {900 -- 923}, publisher = {Springer}, title = {{Anderson localization at band edges for random magnetic fields}}, doi = {10.1007/s10955-012-0445-6}, volume = {146}, year = {2012}, } @article{2778, abstract = {We prove the bulk universality of the β-ensembles with non-convex regular analytic potentials for any β > 0. This removes the convexity assumption appeared in the earlier work [P. Bourgade, L. Erdös, and H.-T. Yau, Universality of general β-ensembles, preprint arXiv:0907.5605 (2011)]. The convexity condition enabled us to use the logarithmic Sobolev inequality to estimate events with small probability. The new idea is to introduce a "convexified measure" so that the local statistics are preserved under this convexification.}, author = {Bourgade, Paul and László Erdös and Yau, Horng-Tzer}, journal = {Journal of Mathematical Physics}, number = {9}, publisher = {American Institute of Physics}, title = {{Bulk universality of general β-ensembles with non-convex potential}}, doi = {10.1063/1.4751478}, volume = {53}, year = {2012}, } @article{2779, abstract = {We consider a two-dimensional magnetic Schrödinger operator on a square lattice with a spatially stationary random magnetic field. We prove Anderson localization near the spectral edges. We use a new approach to establish a Wegner estimate that does not rely on the monotonicity of the energy on the random parameters.}, author = {László Erdös and Hasler, David G}, journal = {Annales Henri Poincare}, number = {8}, pages = {1719 -- 1731}, publisher = {Birkhäuser}, title = {{Wegner estimate for random magnetic Laplacian on ℤ 2}}, doi = {10.1007/s00023-012-0177-9}, volume = {13}, year = {2012}, } @article{2802, abstract = {When a binary fluid demixes under a slow temperature ramp, nucleation, coarsening and sedimentation of droplets lead to an oscillatory evolution of the phase-separating system. The advection of the sedimenting droplets is found to be chaotic. The flow is driven by density differences between two phases. Here, we show how image processing can be combined with particle tracking to resolve droplet size and velocity simultaneously. Droplets are used as tracer particles, and the sedimentation velocity is determined. Taking these effects into account, droplets with radii in the range of 4-40 μm are detected and tracked. Based on these data, we resolve the oscillations in the droplet size distribution that are coupled to the convective flow.}, author = {Lapp, Tobias and Rohloff, Martin and Vollmer, Jürgen T and Björn Hof}, journal = {Experiments in Fluids}, number = {5}, pages = {1187 -- 1200}, publisher = {Springer}, title = {{Particle tracking for polydisperse sedimenting droplets in phase separation}}, doi = {10.1007/s00348-011-1243-7}, volume = {52}, year = {2012}, } @article{2803, abstract = {Recent numerical studies suggest that in pipe and related shear flows, the region of phase space separating laminar from turbulent motion is organized by a chaotic attractor, called an edge state, which mediates the transition process. We here confirm the existence of the edge state in laboratory experiments. We observe that it governs the dynamics during the decay of turbulence underlining its potential relevance for turbulence control. In addition we unveil two unstable traveling wave solutions underlying the experimental flow fields. This observation corroborates earlier suggestions that unstable solutions organize turbulence and its stability border.}, author = {de Lózar, Alberto and Mellibovsky, Fernando and Avila, Marc and Björn Hof}, journal = {Physical Review Letters}, number = {21}, publisher = {American Physical Society}, title = {{Edge state in pipe flow experiments}}, doi = {10.1103/PhysRevLett.108.214502}, volume = {108}, year = {2012}, } @article{2804, abstract = {The analysis of the size distribution of droplets condensing on a substrate (breath figures) is a test ground for scaling theories. Here, we show that a faithful description of these distributions must explicitly deal with the growth mechanisms of the droplets. This finding establishes a gateway connecting nucleation and growth of the smallest droplets on surfaces to gross features of the evolution of the droplet size distribution}, author = {Blaschke, Johannes and Lapp, Tobias and Björn Hof and Vollmer, Jürgen T}, journal = {Physical Review Letters}, number = {6}, publisher = {American Physical Society}, title = {{Breath figures: Nucleation, growth, coalescence, and the size distribution of droplets}}, doi = {10.1103/PhysRevLett.109.068701}, volume = {109}, year = {2012}, } @inproceedings{2825, abstract = {We study the problem of maximum marginal prediction (MMP) in probabilistic graphical models, a task that occurs, for example, as the Bayes optimal decision rule under a Hamming loss. MMP is typically performed as a two-stage procedure: one estimates each variable's marginal probability and then forms a prediction from the states of maximal probability. In this work we propose a simple yet effective technique for accelerating MMP when inference is sampling-based: instead of the above two-stage procedure we directly estimate the posterior probability of each decision variable. This allows us to identify the point of time when we are sufficiently certain about any individual decision. Whenever this is the case, we dynamically prune the variables we are confident about from the underlying factor graph. Consequently, at any time only samples of variables whose decision is still uncertain need to be created. Experiments in two prototypical scenarios, multi-label classification and image inpainting, show that adaptive sampling can drastically accelerate MMP without sacrificing prediction accuracy.}, author = {Lampert, Christoph}, location = {Lake Tahoe, NV, United States}, pages = {82 -- 90}, publisher = {Neural Information Processing Systems}, title = {{Dynamic pruning of factor graphs for maximum marginal prediction}}, volume = {1}, year = {2012}, }