BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Miklós Z. Rácz

Miklós Z. Rácz appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.PRmath.STStatistics TheoryDiscrete MathematicsData Structures and Algorithmsmath.COSocial and Information NetworksPopulations and Evolution

Catalog footprint

What is connected

6works
8topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

6 published item(s)

preprint2021arXiv

Tree trace reconstruction using subtraces

Tree trace reconstruction aims to learn the binary node labels of a tree, given independent samples of the tree passed through an appropriately defined deletion channel. In recent work, Davies, Rácz, and Rashtchian used combinatorial methods to show that $\exp(\mathcal{O}(k \log_{k} n))$ samples suffice to reconstruct a complete $k$-ary tree with $n$ nodes with high probability. We provide an alternative proof of this result, which allows us to generalize it to a broader class of tree topologies and deletion models. In our proofs, we introduce the notion of a subtrace, which enables us to connect with and generalize recent mean-based complex analytic algorithms for string trace reconstruction.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Finding a planted clique by adaptive probing

We consider a variant of the planted clique problem where we are allowed unbounded computational time but can only investigate a small part of the graph by adaptive edge queries. We determine (up to logarithmic factors) the number of queries necessary both for detecting the presence of a planted clique and for finding the planted clique. Specifically, let $G \sim G(n,1/2,k)$ be a random graph on $n$ vertices with a planted clique of size $k$. We show that no algorithm that makes at most $q = o(n^2 / k^2 + n)$ adaptive queries to the adjacency matrix of $G$ is likely to find the planted clique. On the other hand, when $k \geq (2+ε) \log_2 n$ there exists a simple algorithm (with unbounded computational power) that finds the planted clique with high probability by making $q = O( (n^2 / k^2) \log^2 n + n \log n)$ adaptive queries. For detection, the additive $n$ term is not necessary: the number of queries needed to detect the presence of a planted clique is $n^2 / k^2$ (up to logarithmic factors).

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Multidimensional sticky Brownian motions as limits of exclusion processes

We study exclusion processes on the integer lattice in which particles change their velocities due to stickiness. Specifically, whenever two or more particles occupy adjacent sites, they stick together for an extended period of time, and the entire particle system is slowed down until the ``collision'' is resolved. We show that under diffusive scaling of space and time such processes converge to what one might refer to as a sticky reflected Brownian motion in the wedge. The latter behaves as a Brownian motion with constant drift vector and diffusion matrix in the interior of the wedge, and reflects at the boundary of the wedge after spending an instant of time there. In particular, this leads to a natural multidimensional generalization of sticky Brownian motion on the half-line, which is of interest in both queuing theory and stochastic portfolio theory. For instance, this can model a market, which experiences a slowdown due to a major event (such as a court trial between some of the largest firms in the market) deciding about the new market leader.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Can one hear the shape of a population history?

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.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

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

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.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

On the influence of the seed graph in the preferential attachment model

We study the influence of the seed graph in the preferential attachment model, focusing on the case of trees. We first show that the seed has no effect from a weak local limit point of view. On the other hand, we conjecture that different seeds lead to different distributions of limiting trees from a total variation point of view. We take a first step in proving this conjecture by showing that seeds with different degree profiles lead to different limiting distributions for the (appropriately normalized) maximum degree, implying that such seeds lead to different (in total variation) limiting trees.

0 citations0 reviewsNo code linkedOpen access