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 Publications

• 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]
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.