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

Marcos Kiwi

Marcos Kiwi contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
math.COmath.PRComputational ComplexityData Structures and AlgorithmsDiscrete MathematicsSocial and Information Networks

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
6works
0followers
6topics
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

6 published item(s)

preprint2022arXiv

Tail bounds for detection times in mobile hyperbolic graphs

Motivated by Krioukov et al.'s model of random hyperbolic graphs for real-world networks, and inspired by the analysis of a dynamic model of graphs in Euclidean space by Peres et al., we introduce a dynamic model of hyperbolic graphs in which vertices are allowed to move according to a Brownian motion maintaining the distribution of vertices in hyperbolic space invariant. For different parameters of the speed of angular and radial motion, we analyze tail bounds for detection times of a fixed target and obtain a complete picture, for very different regimes, of how and when the target is detected: as a function of the time passed, we characterize the subset of the hyperbolic space where particles typically detecting the target are initially located. We overcome several substantial technical difficulties not present in Euclidean space, and provide a complete picture on tail bounds. On the way, we obtain also new results for the time more general continuous processes with drift and reflecting barrier spent in certain regions, and we also obtain improved bounds for independent sums of Pareto random variables.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Repetition-free longest common subsequence of random sequences

A repetition free Longest Common Subsequence (LCS) of two sequences x and y is an LCS of x and y where each symbol may appear at most once. Let R denote the length of a repetition free LCS of two sequences of n symbols each one chosen randomly, uniformly, and independently over a k-ary alphabet. We study the asymptotic, in n and k, behavior of R and establish that there are three distinct regimes, depending on the relative speed of growth of n and k. For each regime we establish the limiting behavior of R. In fact, we do more, since we actually establish tail bounds for large deviations of R from its limiting behavior. Our study is motivated by the so called exemplar model proposed by Sankoff (1999) and the related similarity measure introduced by Adi et al. (2007). A natural question that arises in this context, which as we show is related to long standing open problems in the area of probabilistic combinatorics, is to understand the asymptotic, in n and k, behavior of parameter R.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Strict majority bootstrap percolation in the r-wheel

In this paper we study the strict majority bootstrap percolation process on graphs. Vertices may be active or passive. Initially, active vertices are chosen independently with probability p. Each passive vertex becomes active if at least half of its neighbors are active (and thereafter never changes its state). If at the end of the process all vertices become active then we say that the initial set of active vertices percolates on the graph. We address the problem of finding graphs for which percolation is likely to occur for small values of p. Specifically, we study a graph that we call r-wheel: a ring of n vertices augmented with a universal vertex where each vertex in the ring is connected to its r closest neighbors to the left and to its r closest neighbors to the right. We prove that the critical probability is 1/4. In other words, if p>1/4 then for large values of r percolation occurs with probability arbitrarily close to 1 as n goes to infinity. On the other hand, if p<1/4 then the probability of percolation is bounded away from 1.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Computational Hardness of Enumerating Satisfying Spin-Assignments in Triangulations

Satisfying spin-assignments in triangulations of a surface are states of minimum energy of the antiferromagnetic Ising model on triangulations which correspond (via geometric duality) to perfect matchings in cubic bridgeless graphs. In this work we show that it is NP-complete to decide whether or not a surface triangulation admits a satisfying spin-assignment, and that it is #P-complete to determine the number of such assignments. Both results are derived via an elaborate (and atypical) reduction that maps a Boolean formula in 3-conjunctive normal form into a triangulation of an orientable closed surface.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Generalizations and Variants of the Largest Non-crossing Matching Problem in Random Bipartite Graphs

We are interested in the statistics of the length of the longest increasing subsequence of 2-rowed lexicographically sorted arrays chosen according to distinct families of distributions D = (D_n)_n, and when n goes to infinity. This framework encompasses well studied problems such as the so called Longest Increasing Subsequence problem, the Longest Common Subsequence problem, problems concerning directed bond percolation models, among others. We define several natural families of distinct distributions and characterize the asymptotic behavior of the expected length of a longest increasing subsequence chosen according to them. In particular, we consider generalizations to d-rowed arrays as well as symmetry restricted two-rowed arrays.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Counting perfect matchings of cubic graphs in the geometric dual

Lovász and Plummer conjectured, in the mid 1970&#39;s, that every cubic graph G with no cutedge has an exponential in |V(G)| number of perfect matchings. In this work we show that every cubic planar graph G whose geometric dual graph is a stack triangulation has at least 3 times the golden ratio to |V(G)|/72 distinct perfect matchings. Our work builds on a novel approach relating Lovász and Plummer&#39;s conjecture and the number of so called groundstates of the widely studied Ising model from statistical physics.

0 citations0 reviewsNo code linkedOpen access