BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Nina Holden

Nina Holden contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
math.PRmath-phmath.MPData Structures and Algorithmsmath.CODistributed, Parallel, and Cluster ComputingInformation Theorymath.IT

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
7works
0followers
8topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

Published work

7 published item(s)

preprint2023arXiv

Baxter permuton and Liouville quantum gravity

The Baxter permuton is a random probability measure on the unit square which describes the scaling limit of uniform Baxter permutations. We find an explict formula for the expectation of the Baxter permuton, i.e.\ the density of its intensity measure. This answers a question of Dokos and Pak (2014). We also prove that all pattern densities of the Baxter permuton are strictly positive, distinguishing it from other permutons arising as scaling limits of pattern-avoiding permutations. Our proofs rely on a recent connection between the Baxter permuton and Liouville quantum gravity (LQG) coupled with the Schramm-Loewner evolution (SLE). The method works equally well for a two-parameter generalization of the Baxter permuton recently introduced by the first author, except that the density is not as explicit. This new family of permutons, called \emph{skew Brownian permuton}, describes the scaling limit of a number of random constrained permutations. We finally observe that in the LQG/SLE framework, the expected proportion of inversions in a skew Brownian permuton equals $\frac{π-2θ}{2π}$ where $θ$ is the so-called imaginary geometry angle between a certain pair of SLE curves.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Integrability of SLE via conformal welding of random surfaces

We demonstrate how to obtain integrable results for the Schramm-Loewner evolution (SLE) from Liouville conformal field theory (LCFT) and the mating-of-trees framework for Liouville quantum gravity (LQG). In particular, we prove an exact formula for the law of a conformal derivative of a classical variant of SLE called $\mathrm{SLE}_κ(ρ_-;ρ_+)$. Our proof is built on two connections between SLE, LCFT, and mating-of-trees. Firstly, LCFT and mating-of-trees provide equivalent but complementary methods to describe natural random surfaces in LQG. Using a novel tool that we call the uniform embedding of an LQG surface, we extend earlier equivalence results by allowing fewer marked points and more generic singularities. Secondly, the conformal welding of these random surfaces produces SLE curves as their interfaces. In particular, we rely on the conformal welding results proved in our companion paper [AHS20]. Our paper is an essential part of a program proving integrability results for SLE, LCFT, and mating-of-trees based on these two connections.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Mating of trees for critical Liouville quantum gravity

In a groundbreaking work, Duplantier, Miller and Sheffield showed that subcritical Liouville quantum gravity (LQG) coupled with Schramm-Loewner evolutions (SLE) can be described by the mating of two continuum random trees. In this paper, we consider the counterpart of their result for critical LQG and SLE, i.e., for the case when $γ^2=κ=16/κ=4$. We prove that as one sends $κ\downarrow 4$ in the subcritical setting, the space-filling SLE$_κ$ in a disk degenerates to the CLE$_4$ exploration introduced by Werner and Wu, along with a collection of i.i.d.\ coin tosses indexed by the branch points of the exploration. Furthermore, in the $κ=16/γ^2\downarrow 4$ limit, the pair of continuum random trees collapse into a single continuum random tree, and we observe that upon applying an appropriate affine transform to the encoding Brownian motions before taking the limit, we get convergence to a pair of independent Brownian motions $(A,B)$. The Brownian motion $A$ encodes the LQG distance from the CLE loops to the boundary of the disk, while the Brownian motion $B$ encodes the boundary lengths of the CLE$_4$ loops. In contrast to the subcritical setting, $(A,B)$ does not determine the CLE-decorated LQG surface.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A mating-of-trees approach for graph distances in random planar maps

We introduce a general technique for proving estimates for certain random planar maps which belong to the $γ$-Liouville quantum gravity (LQG) universality class for $γ\in (0,2)$. The family of random planar maps we consider are those which can be encoded by a two-dimensional random walk with i.i.d.\ increments via a mating-of-trees bijection, and includes the uniform infinite planar triangulation (UIPT; $γ=\sqrt{8/3}$); and planar maps weighted by the number of different spanning trees ($γ=\sqrt 2$), bipolar orientations ($γ=\sqrt{4/3}$), or Schnyder woods ($γ=1$) that can be put on the map. Using our technique, we prove estimates for graph distances in the above family of random planar maps. In particular, we obtain non-trivial upper and lower bounds for the cardinality of a graph distance ball consistent with the Watabiki (1993) prediction for the Hausdorff dimension of $γ$-LQG and we establish the existence of an exponent for certain distances in the map. The basic idea of our approach is to compare a given random planar map $M$ to a mated-CRT map---a random planar map constructed from a correlated two-dimensional Brownian motion---using a strong coupling (Zaitsev, 1998) of the encoding walk for $M$ and the Brownian motion used to construct the mated-CRT map. This allows us to deduce estimates for graph distances in $M$ from the estimates for graph distances in the mated-CRT map which we proved (using continuum theory) in a previous work. In the special case when $γ=\sqrt{8/3}$, we instead deduce estimates for the $\sqrt{8/3}$-mated-CRT map from known results for the UIPT. The arguments of this paper do not directly use SLE/LQG, and can be read without any knowledge of these objects.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Subpolynomial trace reconstruction for random strings and arbitrary deletion probability

The insertion-deletion channel takes as input a bit string ${\bf x}\in\{0,1\}^{n}$, and outputs a string where bits have been deleted and inserted independently at random. The trace reconstruction problem is to recover $\bf x$ from many independent outputs (called &#34;traces&#34;) of the insertion-deletion channel applied to $\bf x$. We show that if $\bf x$ is chosen uniformly at random, then $\exp(O(\log^{1/3} n))$ traces suffice to reconstruct $\bf x$ with high probability. For the deletion channel with deletion probability $q < 1/2$ the earlier upper bound was $\exp(O(\log^{1/2} n))$. The case of $q\geq 1/2$ or the case where insertions are allowed has not been previously analyzed, and therefore the earlier upper bound was as for worst-case strings, i.e., $\exp(O( n^{1/3}))$. We also show that our reconstruction algorithm runs in $n^{1+o(1)}$ time. A key ingredient in our proof is a delicate two-step alignment procedure where we estimate the location in each trace corresponding to a given bit of $\bf x$. The alignment is done by viewing the strings as random walks and comparing the increments in the walk associated with the input string and the trace, respectively.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Communication cost of consensus for nodes with limited memory

Motivated by applications in blockchains and sensor networks, we consider a model of $n$ nodes trying to reach consensus on their majority bit. Each node $i$ is assigned a bit at time zero, and is a finite automaton with $m$ bits of memory (i.e., $2^m$ states) and a Poisson clock. When the clock of $i$ rings, $i$ can choose to communicate, and is then matched to a uniformly chosen node $j$. The nodes $j$ and $i$ may update their states based on the state of the other node. Previous work has focused on minimizing the time to consensus and the probability of error, while our goal is minimizing the number of communications. We show that when $m>3 \log\log\log(n)$, consensus can be reached at linear communication cost, but this is impossible if $m<\log\log\log(n)$. We also study a synchronous variant of the model, where our upper and lower bounds on $m$ for achieving linear communication cost are $2\log\log\log(n)$ and $\log\log\log(n)$, respectively. A key step is to distinguish when nodes can become aware of knowing the majority bit and stop communicating. We show that this is impossible if their memory is too low.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Liouville quantum gravity with matter central charge in $(1,25)$: a probabilistic approach

There is a substantial literature concerning Liouville quantum gravity (LQG) in two dimensions with conformal matter field of central charge ${\mathbf{c}}_{\mathrm M}\in(-\infty,1]$. Via the DDK ansatz, LQG can equivalently be described as the random geometry obtained by exponentiating $γ$ times a variant of the planar Gaussian free field (GFF), where $γ\in(0,2]$ satisfies $\mathbf c_{\mathrm M}=25-6(2/γ+γ/2)^2$. Physics considerations suggest that LQG should also make sense in the regime when $\mathbf c_{\mathrm M}>1$. However, the behavior in this regime is rather mysterious in part because the corresponding value of $γ$ is complex, so analytic continuations of various formulas give complex answers which are difficult to interpret in a probabilistic setting. We introduce and study a discretization of LQG which makes sense for all values of $\mathbf c_{\mathrm M}\in(-\infty,25)$. Our discretization consists of a random planar map, defined as the adjacency graph of a tiling of the plane by dyadic squares which all have approximately the same &#34;LQG size&#34; with respect to the GFF. We prove that several formulas for dimension-related quantities are still valid for $\mathbf c_{\mathrm M}\in(1,25)$, with the caveat that the dimension is infinite when the formulas give a complex answer. In particular, we prove an extension of the (geometric) KPZ formula for $\mathbf c_{\mathrm M}\in(1,25)$, which gives a finite quantum dimension iff the Euclidean dimension is at most $(25-\mathbf c_{\mathrm M})/12$. We also show that the graph distance between typical points with respect to our discrete model grows polynomially whereas the cardinality of a graph distance ball of radius $r$ grows faster than any power of $r$ (which suggests that the Hausdorff dimension of LQG is infinite for $\mathbf c_{\mathrm M}\in(1,25)$). We include a substantial list of open problems.

0 citations0 reviewsNo code linkedOpen access