3 citations · 11 across the 8 of their papers we have counts for
11 papers
A large deviation principle for block models
Christian Borgs, Jennifer Chayes, Julia Gaudio +2
We initiate a study of large deviations for block model random graphs in the dense regime. Following Chatterjee-Varadhan(2011), we establish an LDP for dense block models, viewed a…
Correlation decay for hard spheres via Markov chains
Tyler Helmuth, Will Perkins, Samantha Petti
We improve upon all known lower bounds on the critical fugacity and critical density of the hard sphere model in dimensions two and higher. As the dimension tends to infinity our i…
Thresholds in random motif graphs
Michael Anastos, Peleg Michaeli, Samantha Petti
We introduce a natural generalization of the Erdős-Rényi random graph model in which random instances of a fixed motif are added independently. The binomial random motif graph $G(H…
Approximating Sparse Graphs: The Random Overlapping Communities Model
Samantha Petti, Santosh S. Vempala
How can we approximate sparse graphs and sequences of sparse graphs (with unbounded average degree)? We consider convergence in the first moments of the graph spectrum (equival…
Random Overlapping Communities: Approximating Motif Densities of Large Graphs
Samantha Petti, Santosh Vempala
A wide variety of complex networks (social, biological, information etc.) exhibit local clustering with substantial variation in the clustering coefficient (the probability of neig…
Balanced Allocation Through Random Walk
Alan Frieze, Samantha Petti
We consider the allocation problem in which items are to be allocated to bins with capacity . The items arrive sequentially and when…
The covertime of a biased random walk on
Colin Cooper, Alan Frieze, Samantha Petti
We analyze the covertime of a biased random walk on the random graph . The walk is biased towards visiting vertices of low degree and this makes the covertime less than in…
A Space of Phylogenetic Networks
Satyan L. Devadoss, Samantha Petti
A classic problem in computational biology is constructing a phylogenetic tree given a set of distances between n species. In most cases, a tree structure is too constraining. We c…
Cortical Computation via Iterative Constructions
Christos Papadimitrou, Samantha Petti, Santosh Vempala
We study Boolean functions of an arbitrary number of input variables that can be realized by simple iterative constructions based on constant-size primitives. This restricted type…
Multi-crossing Number for Knots and the Kauffman Bracket Polynomial
Colin Adams, Orsola Capovilla-Searle, Jesse Freeman +5
A multi-crossing (or n-crossing) is a singular point in a projection at which n strands cross so that each strand bisects the crossing. We generalize the classic result of Kauffman…
Bounds on Übercrossing and Petal Numbers for Knots
Colin Adams, Orsola Capovilla-Searle, Jesse Freeman +5
An -crossing is a point in the projection of a knot where strands cross so that each strand bisects the crossing. An übercrossing projection has a single -crossing and a…