I don't have any particular recipe [for developing new proofs] ... It is like being lost in a jungle and trying to use all the knowledge that you can gather to come up with some new tricks, and with some luck, you might find a way out. - Maryam Mirzakhani
Peer-Reviewed
Enhancing Environmental Enforcement with Near Real-Time Monitoring: Likelihood-Based Detection of Structural Expansion of Intensive Livestock Farms.
[journal]
[pdf]
[Code]
Ben Chugg^{*}, Brandon Anderson^{*}, Seiji Eicher, Sandy Lee, Daniel E. Ho. Journal of Applied Earth Observation and Geoinformation. 2021.
Environmental enforcement has historically relied on physical, resource-intensive, and infrequent inspections. Advances in remote sensing and computer vision have the potential to augment compliance monitoring, by providing early warning signals of permit violations. We demonstrate a process for rapid identification of significant structural expansion using satellite imagery and focusing on Concentrated Animal Feeding Operations (CAFOs) as a test case. Unpermitted expansion has been a particular challenge with CAFOs, which pose significant health and environmental risks. Using a new hand-labeled dataset of 175,736 images of 1,513 CAFOs, we combine state-of-the-art building segmentation with a likelihood-based change-point detection model to provide a robust signal of building expansion (AUC = 0.80). A major advantage of this approach is that it is able to work with high-cadence (daily to weekly), but lower resolution (3m/pixel), satellite imagery. It is also highly generalizable and thus provides a near real-time monitoring tool to prioritize enforcement resources to other settings where unpermitted construction poses environmental risk, e.g. zoning, habitat modification, or wetland protection.
Evaluation of Allocation Schemes of COVID-19 Testing Resources in a Community-Based Door-to-Door Testing Program.
[journal]
More Info: Daily Mail, Infodig,
Stanford News, LabPulse summary
Ben Chugg^{*}, Lisa Lu^{*}, Derek Ouyang^{*}, Ben Anderson, Raymond Ha et al. Journals of the American Medical Assocation (JAMA), Health Forum. 2021.
Composable Computation in Leaderless, Discrete Chemical Reaction Networks.
[pdf]
Hooman Hashemi, Ben Chugg, Anne Condon. International Conference on DNA Computing and Molecular Programming. 2020.
We classify the functions \(f:\mathbb{N}^d \rightarrow \mathbb{N}\)
that are stably computable by leaderless, output-oblivious discrete (stochastic)
Chemical Reaction Networks (CRNs). CRNs that compute such functions
are systems of reactions over species that include \(d\) designated
input species, whose initial counts represent an input \(x \in
\mathbb{N}^d\), and one output species whose eventual count represents
\(f(x)\). Chen et al. showed that the class of functions computable by CRNs is
precisely the semilinear functions.
In output-oblivious CRNs, the output species is never a reactant. Output-oblivious CRNs are easily composable since a downstream CRN can consume the output of an upstream CRN without affecting its correctness. Severson et al. showed that output-oblivious CRNs compute exactly the subclass of semilinear functions that are eventually the minimum of
quilt-affine functions, i.e., affine functions with different intercepts in each of finitely many congruence classes. They call such functions the output-oblivious functions. A leaderless CRN can compute only superadditive functions, and so a leaderless output-oblivious CRN can compute only superadditive, output-oblivious functions. In this work we show that a function
\(f:\mathbb{N}^d \rightarrow \mathbb{N}\) is stably computable by a leaderless, output-oblivious CRN if and only if it is superadditive and
output-oblivious.
Simultaneous Visibility Representations of Undirected Graphs. [journal] [pdf]
Ben Chugg, Will Evans, Kelvin Wong. Journal of Computational Geometry. 2021. Canadian Conference on Computational Geometry. 2020.
We consider the problem of determining if a pair of undirected graphs \(\langle G_V,G_H\rangle\), which share the same vertex set, has a representation using opaque geometric shapes for vertices, and vertical/horizontal visibility between shapes to determine the edges of \(G_V/G_H\). While such a simultaneous visibility representation of two graphs can be determined efficiently if the direction of the required visibility for each edge is provided (and the vertex shapes are sufficiently simple), it was unclear if edge direction is critical for efficiency. We show that the problem is NP-complete without that information, even for graphs that are only slightly more complex than paths. In addition, we characterize which pairs of paths have simultaneous visibility representations using fixed orientation L-shapes. This narrows the range of possible graph families for which determining simultaneous visibility representation is non-trivial yet not NP-hard.
Submodular Stochastic Probing with Prices. [pdf]
Ben Chugg, Takanori Maehara. International Conference on Control, Decision, and Information Technologies. 2019.
We introduce Stochastic Probing with Prices (SPP), a variant of the Stochastic
Probing (SP) model in which we must pay a price to probe an element. A SPP problem involves two set systems \((\mathcal{N} , \mathcal{I}_{in})\) and \((\mathcal{N} , \mathcal{I}_{out})\) where each \(e\in\mathcal{N}\) is active with
probability \(p_e\). To discover whether an element \(e\) is active, it must be probed by paying
the price \(\Delta_e\). If an element is probed and is active, then it is irrevocably added to the
solution. Moreover, at all times, the set of probed elements must lie in \(\mathcal{I}_{out}\), and the
solution (the set of probed and active elements) must lie in \(\mathcal{I}_{in}\). The goal is to maximize a submodular set function \(f\) minus the cost of the probes. We give a bi-criteria
approximation algorithm to the online version of this problem, in which the elements
are shown to the algorithm in a possibly adversarial order. Our results translate to
state-of-the-art approximations for the traditional (online) stochastic probing problem.
Output-Oblivious Stochastic Chemical Reaction Networks. [pdf]
Ben Chugg, Anne Condon, Hooman Hashemi. International Conference on Principles of Distributed Systems. 2018.
We classify the functions \(f: \mathbb{N}^2\to \mathbb{N}\)
which are stably computable by output-oblivious Stochastic
Chemical Reaction Networks (CRNs), i.e., systems of reactions in which output species are never
reactants. While it is known that precisely the semilinear functions are stably computable by
CRNs, such CRNs sometimes rely on initially producing too many output species, and then
consuming the excess in order to reach a correct stable state. These CRNs may be difficult to
integrate into larger systems: if the output of a CRN \(C\) becomes the input to a downstream CRN \(C'\), then \(C'\)
could inadvertently consume too many outputs before \(C\) stabilizes. If, on the other
hand, \(C\) is output-oblivious then \(C'\)
may consume \(C\)'s output as soon as it is available. In this work
we prove that a semilinear function \(f : \mathbb{N}^2\to\mathbb{N}\)
is stably computable by an output-oblivious CRN
with a leader if and only if it is both increasing and either grid-affine (intuitively, its domains
are congruence classes), or the minimum of a finite set of fissure functions (intuitively, functions
behaving like the min function).
Theses
The Graph-Simplex Correspondence and its Algorithmic Foundations. [pdf]
M.Sc. Thesis.
We present and study the graph-simplex correspondence—a tool providing a series of relationships between weighted, undirected graphs on \(n\) vertices and simplices in \((n-1)\)-dimensional
Euclidean space. The core of the correspondence is a bijection between graphs and hyperacute simplices, first uncovered by Miroslav Fiedler. We consolidate Fiedler's work on the
subject and expand on it in several ways.
The first relates purely to the mathematical properties of the correspondence. Among
other things, we extend the correspondence to the normalized Laplacian matrix \(\widehat{L}_G\) (whereas
previously only the combinatorial Laplacian, \(L_G\), had been used), develop new equations
and inequalities relating aspects of the simplex to those of the graph, and give an isometry
between a graph's "inverse combinatorial simplex" and an \(n\)-dimensional polytope arising
from the Laplacian's pseudoinverse.
Secondly, we examine the algorithmic underpinnings and consequences of the correspondence. We begin by demonstrating that it can be used to draw conclusions about the computational complexity of various geometric problems. We then provide lower bounds on
the complexity of transitioning between graphs and simplices, and end by studying low dimensional representations of the simplices. This provides theoretical justification for recent
empirical work on Laplacian eigenmaps.
Of possible independent interest, we provide a formula for the non-zero eigenvalues of
\(\widehat{L}_G\) in terms of the total weight of spanning trees in the graph \(G\), relate the volume of an
arbitrary simplex to the eigenvalues of the Gram matrix of its dual simplex (an object we
introduce), and give an equation for the adjugate of \(\widehat{L}_G\) in terms of the weights of the vertices
in \(G\).
A Model for Computing in Dynamic, Resource-Limited Environments.
B.Sc. Thesis.