Publications (37)
Fewer colors for perfect simulation of proper colorings
Mark Huber
Given a graph and color set , a is an assignment of a color to each vertex of such that no two vertices connected by an edge ar…
Random construction of interpolating sets for high dimensional integration
Mark Huber, Sarah Schott
Many high dimensional integrals can be reduced to the problem of finding the relative measures of two sets. Often one set will be exponentially larger than the other, making it dif…
Robust estimation of the mean with bounded relative standard deviation
Mark Huber
Many randomized approximation algorithms operate by giving a procedure for simulating a random variable which has mean equal to the target answer, and a relative standard…
Generating uniform linear extensions using few random bits
Mark Huber
A \emph{linear extension} of a partial order \(\preceq\) over items \(A = \{ 1, 2, \ldots, n \}\) is a permutation \(Ï\) such that for all \(i < j\) in \(A\), it holds that \(\neg…
Multivariate distributions with fixed marginals and correlations
Mark Huber, Nevena Maric
Consider the problem of drawing random variates from a distribution where the marginal of each is specified, as well as the correlation between every pair…
An unbiased estimate for the mean of a {0,1} random variable with relative error distribution independent of the mean
Mark Huber
Say are independent identically distributed Bernoulli random variables with mean . This paper builds a new estimate of that has the property that t…
Perfect simulation of Vervaat perpetuities
James Allen Fill, Mark Huber
We use coupling into and from the past to sample perfectly in a simple and provably fast fashion from the Vervaat family of perpetuities. The family includes the Dickman distributi…
An estimator for Poisson means whose relative error distribution is known
Mark Huber
Suppose that are a stream of independent, identically distributed Poisson random variables with mean . This work presents a new estimate for with t…
Halving the bounds for the Markov, Chebyshev, and Chernoff Inequalities using smoothing
Mark Huber
The Markov, Chebyshev, and Chernoff inequalities are some of the most widely used methods for bounding the tail probabilities of random variables. In all three cases, the bounds ar…
Tail inequalities for restricted classes of discrete random variables
Mark Huber
Let be an integrable discrete random variable over with for all . Then for any integer , $\mat…
Approximation algorithms for the normalizing constant of Gibbs distributions
Mark Huber
Consider a family of distributions where means that . Here is the proper normalizing constant, equal to $\sum_…
The splitting of double-component active asteroid P/2016 J1 (PANSTARRS)
Fernando Moreno, Francisco Pozuelos, Bojan Novakovic +20
We present deep imaging observations, orbital dynamics, and dust tail model analyses of the double-component asteroid P/2016 J1 (J1-A and J1-B). The observations were acquired at t…
The Pulsar-White Dwarf-Planet System in Messier 4: Improved Astrometry
Harvey B. Richer, Rodrigo Ibata, Gregory G. Fahlman +1
A young and undermassive white dwarf has been identified as the possible companion to the millisecond pulsar PSR B1620-26 in Messier 4. This association is important as it then hel…
Proper colorings of a graph in linear time using a number of colors linear in the maximum degree of the graph
Kritika Bhandari, Mark Huber
A new algorithm for exactly sampling from the set of proper colorings of a graph is presented. This is the first such algorithm that has an expected running time that is guaranteed…
SN 2024iss: A Multi-Wavelength Exposé of a Type IIb Supernova with an Early-Time Ultraviolet Spectrum and Shock Breakout Constraints
Rujula Yete, Wynn Jacobson-Galan, Ferdinand Ferdinand +49
We present multi-wavelength observations and a comprehensive analysis of the nearby (D14 Mpc) Type IIb supernova (SN IIb) 2024iss. Observations of SN2024iss include an early…
The Anomalous Acceleration of PSR J2043+1711: Long-Period Orbital Companion or Stellar Flyby?
Thomas Donlon, Sukanya Chakrabarti, Michael T. Lam +53
Based on the rate of change of its orbital period, PSR J2043+1711 has a substantial peculiar acceleration of 3.5 0.8 mm/s/yr, which deviates from the acceleration predicted b…
Bernoulli Correlations and Cut Polytopes
Mark Huber, Nevena Maric
Given symmetric Bernoulli variables, what can be said about their correlation matrix viewed as a vector? We show that the set of those vectors is a polytope…
A Periodically Varying Luminous Quasar at z=2 from the Pan-STARRS1 Medium Deep Survey: A Candidate Supermassive Black Hole Binary in the Gravitational Wave-Driven Regime
Tingting Liu, Suvi Gezari, Sebastien Heinis +11
Supermassive black hole binaries (SMBHBs) should be an inevitable consequence of the hierarchical growth of massive galaxies through mergers, and the strongest sirens of gravitatio…
Improving Monte Carlo randomized approximation schemes
Mark Huber
Consider a central problem in randomized approximation schemes that use a Monte Carlo approach. Given a sequence of independent, identically distributed random variables $X_1,X_2,\…
Optimal rolling of fair dice using fair coins
Mark Huber, Danny Vargas
In 1976, Knuth and Yao presented an algorithm for sampling from a finite distribution using flips of a fair coin that on average used the optimal number of flips. Here we show how…
Conditions for rapid mixing of parallel and simulated tempering on multimodal distributions
Dawn B. Woodard, Scott C. Schmidler, Mark Huber
We give conditions under which a Markov chain constructed via parallel or simulated tempering is guaranteed to be rapidly mixing, which are applicable to a wide range of multimodal…
Reducing the Ising model to matchings
Mark Huber, Jenny Law
Canonical paths is one of the most powerful tools available to show that a Markov chain is rapidly mixing, thereby enabling approximate sampling from complex high dimensional distr…
Exact Sampling from Perfect Matchings of Dense Nearly Regular Bipartite Graphs
Mark Huber
We present the first algorithm for generating random variates exactly uniformly from the set of perfect matchings of a bipartite graph with a polynomial expected running time over…
An optimal -approximation scheme for the mean of random variables with bounded relative variance
Mark Huber
Randomized approximation algorithms for many #P-complete problems (such as the partition function of a Gibbs distribution, the volume of a convex body, the permanent of a …
The Extremely Metal-Poor SN 2023ufx: A Local Analog to High-Redshift Type II Supernovae
Michael A. Tucker, Jason Hinkle, Charlotte R. Angus +26
We present extensive observations of the Type II supernova (SN II) 2023ufx which is likely the most metal-poor SN II observed to-date. It exploded in the outskirts of a low-metalli…
Optimal linear Bernoulli factories for small mean problems
Mark Huber
Suppose a coin with unknown probability of heads can be flipped as often as desired. A Bernoulli factory for a function is an algorithm that uses flips of the coin together…
Differential expression analysis for multiple conditions
Ciaran Evans, Johanna Hardin, Mark Huber +2
As high-throughput sequencing has become common practice, the cost of sequencing large amounts of genetic data has been drastically reduced, leading to much larger data sets for an…
Designing Perfect Simulation Algorithms using Local Correctness
Mark Huber
Consider a randomized algorithm that draws samples exactly from a distribution using recursion. Such an algorithm is called a perfect simulation, and here a variety of methods for…
Partially Recursive Acceptance Rejection
Mark Huber
Generating random variates from high-dimensional distributions is often done approximately using Markov chain Monte Carlo. In certain cases, perfect simulation algorithms exist tha…
Nearly optimal Bernoulli factories for linear functions
Mark Huber
Suppose that are independent identically distributed Bernoulli random variables with mean . A Bernoulli factory for a function takes as input $X_1,X_2,\ldot…
Minimum correlation for any bivariate Geometric distribution
Mark Huber, Nevena Maric
Consider a bivariate Geometric random variable where the first component has parameter and the second parameter . It is not possible to make the correlation between the…
Tight relative estimation in the mean of Bernoulli random variables
Mark Huber
Given a stream of Bernoulli random variables, consider the problem of estimating the mean of the random variable within a specified relative error with a specified probability of f…
Spatial birth-death swap chains
Mark Huber
Markov chains have long been used for generating random variates from spatial point processes. Broadly speaking, these chains fall into two categories: Metropolis-Hastings type cha…
Perfect Sampling Using Bounding Chains
Mark Huber
Bounding chains are a technique that offers three benefits to Markov chain practitioners: a theoretical bound on the mixing time of the chain under restricted conditions, experimen…
Generating from the Strauss Process using stitching
Mark Huber
The STrauss process is a point process with unnormalized density with respect to a Poisson point process, where each pair of points within a specified distance of each other co…
The Fundamental Theorem of Perfect Simulation
Mark Huber
Here several perfect simulation algorithms are brought under a single framework, and shown to derive from the same probabilistic result, called here the Fundamental Theorem of Perf…
Fast Perfect Simulation of Vervaat Perpetutities
Kirkwood Cloud, Mark Huber
This work presents a faster method of simulating exactly from a distribution known as a Vervaat perpetuity. A parameter of the Vervaat perpetuity is . An earlier…