MRMiklos Z. Racz

Miklos Z. Racz

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Miklos Z. Racz has a total of 15 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Coexistence in Preferential Attachment Networks

    by Tonći Antunović, Elchanan Mossel, Miklós Z. Rácz

    We introduce a new model of competition on growing networks. This extends the preferential attachment model, with the key property that node choices evolve simultaneously with the network. When a new node joins the network, it chooses neighbours by preferential attachment, and selects its type based on the number of initial neighbours of each type. The model is analysed in detail, and in particular, we determine the possible proportions of the various types in the limit of large networks. An important qualitative feature we find is that, in contrast to many current theoretical models, often several competitors will coexist. This matches empirical observations in many real-world networks.


  • Top Cited Papers

    Testing for high‐dimensional geometry in random graphs

    by Sébastien Bubeck, Jian Ding, Ronen Eldan, Miklós Z. Rácz

    We study the problem of detecting the presence of an underlying high‐dimensional geometric structure in a random graph. Under the null hypothesis, the observed graph is a realization of an Erdős‐Rényi random graph G(n, p). Under the alternative, the graph is generated from the model, where each vertex corresponds to a latent independent random vector uniformly distributed on the sphere , and two vertices are connected if the corresponding latent vectors are close enough. In the dense regime (i.e., p is a constant), we propose a near‐optimal and computationally efficient testing procedure based on a new quantity which we call signed triangles. The proof of the detection lower bound is based on a new bound on the total variation distance between a Wishart matrix and an appropriately normalized GOE matrix. In the sparse regime, we make a conjecture for the optimal detection boundary. We conclude the paper with some preliminary steps on the problem of estimating the dimension in . © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 503–532, 2016


  • Open Access

    Coexistence in preferential attachment networks

    by Tonći Antunović, Elchanan Mossel, Miklos Z. Racz

    We introduce a new model of competition on growing networks. This extends the preferential attachment model, with the key property that node choices evolve simultaneously with the network. When a new node joins the network, it chooses neighbours by preferential attachment, and selects its type based on the number of initial neighbours of each type. The model is analysed in detail, and in particular, we determine the possible proportions of the various types in the limit of large networks. An important qualitative feature we find is that, in contrast to many current theoretical models, often several competitors will coexist. This matches empirical observations in many real-world networks.

  • Open Access

    Testing for high-dimensional geometry in random graphs

    by Sébastien Bubeck, Jian Ding, Ronen Eldan, Miklós Rácz

    We study the problem of detecting the presence of an underlying high-dimensional geometric structure in a random graph. Under the null hypothesis, the observed graph is a realization of an Erd\H{o}s-R\'enyi random graph $G(n,p)$. Under the alternative, the graph is generated from the $G(n,p,d)$ model, where each vertex corresponds to a latent independent random vector uniformly distributed on the sphere $\mathbb{S}^{d-1}$, and two vertices are connected if the corresponding latent vectors are close enough. In the dense regime (i.e., $p$ is a constant), we propose a near-optimal and computationally efficient testing procedure based on a new quantity which we call signed triangles. The proof of the detection lower bound is based on a new bound on the total variation distance between a Wishart matrix and an appropriately normalized GOE matrix. In the sparse regime, we make a conjecture for the optimal detection boundary. We conclude the paper with some preliminary steps on the problem of estimating the dimension in $G(n,p,d)$.

  • Open Access

    Braess's paradox for the spectral gap in random graphs and delocalization of eigenvectors

    by Ronen Eldan, Miklós Rácz, Tselil Schramm

    We study how the spectral gap of the normalized Laplacian of a random graph changes when an edge is added to or removed from the graph. There are known examples of graphs where, perhaps counterintuitively, adding an edge can decrease the spectral gap, a phenomenon that is analogous to Braess's paradox in traffic networks. We show that this is often the case in random graphs in a strong sense. More precisely, we show that for typical instances of Erd\H{o}s-R\'enyi random graphs $G(n,p)$ with constant edge density $p \in (0,1)$, the addition of a random edge will decrease the spectral gap with positive probability, strictly bounded away from zero. To do this, we prove a new delocalization result for eigenvectors of the Laplacian of $G(n,p)$, which might be of independent interest.

  • Dynamic Budget-Constrained Pricing in the Cloud

    by Eric Friedman, Miklós Z. Rácz, Scott Shenker


  • Can one hear the shape of a population history?

    by Junhyong Kim, Elchanan Mossel, Miklós Z. Rácz, Nathan Ross


  • Open Access

    From trees to seeds: on the inference of the seed from large trees in the uniform attachment model

    by Sébastien Bubeck, Ronen Eldan, Elchanan Mossel, Miklós Z. Rácz

    We study the influence of the seed in random trees grown according to the uniform attachment model, also known as uniform random recursive trees. We show that different seeds lead to different distributions of limiting trees from a total variation point of view. To do this, we construct statistics that measure, in a certain well-defined sense, global "balancedness" properties of such trees. Our paper follows recent results on the same question for the preferential attachment model.

  • Open Access

    Can one hear the shape of a population history?

    by Junhyong Kim, Elchanan Mossel, Miklós Z. Rácz, Nathan Ross

    Reconstructing past population size from present day genetic data is a major goal of population genetics. Recent empirical studies infer population size history using coalescent-based models applied to a small number of individuals. Here we provide tight bounds on the amount of exact coalescence time data needed to recover the population size history of a single, panmictic population at a certain level of accuracy. In practice, coalescence times are estimated from sequence data and so our lower bounds should be taken as rather conservative.