
Xi Chen, Yaonan Jin, Tim Randolph, and Rocco Servedio.
"AverageCase Subset Balancing Problems." SODA 2022. arXiv version
Given a set of \(n\) input integers, the Equal Subset Sum problem asks us to find two distinct subsets with the same sum. In this paper we present an algorithm that runs in time \(O^*(3^{0.387n})\) in the~average case, significantly improving over the \(O^*(3^{0.488n})\) running time of the best known worstcase algorithm and the MeetintheMiddle benchmark of \(O^*(3^{0.5n})\).
Our algorithm generalizes to a number of related problems, such as the Generalized Equal Subset Sum problem, which asks us to assign a coefficient \(c_i\) from a set \(C\) to each input number \(x_i\) such that \(\sum_{i} c_i x_i = 0\). Our algorithm for the averagecase version of this problem runs in~time \(C^{(0.5c_0/C)n}\) for some positive constant \(c_0\), whenever \(C=\{0, \pm 1, \dots, \pm d\}\) or \(\{\pm 1, \dots, \pm d\}\) for some positive integer \(d\) (with \(O^*(C^{0.45n})\) when \(C<10\)).
Our results extend to the~problem of finding "nearly balanced" solutions in which the target is a nottoolarge nonzero offset \(\tau\).
Our approach relies on new structural results that characterize the probability that \(\sum_{i} c_i x_i =\tau\) has a solution \(c \in C^n\) when \(x_i\)'s are chosen randomly; these results may be of independent interest. Our algorithm is inspired by the "representation technique" introduced by HowgraveGraham and Joux. This requires several new ideas to overcome preprocessing hurdles that arise in the representation framework, as well as a novel application of dynamic programming in the solution recovery phase of the algorithm.

Nick Arnosti and Tim Randolph.
"Parallel Lotteries: Insights from Alaskan Hunting Permit Allocation." Management Science 2021; EC 2021.
SSRN version
We analyze the \(k\)ticket lottery, which is used to allocate hunting permits in the state of Alaska. Each participant is given \(k\) tickets to distribute among lotteries for different types of items. Participants who win multiple items receive their favorite, and new winners are drawn from the lotteries with unclaimed items.
When supply is scarce, equilibrium outcomes of the \(k\)ticket lottery approximate a competitive equilibrium from equal incomes (CEEI), which is Pareto efficient. When supply is moderate, \(k\)ticket lotteries exhibit two sources of inefficiency. First, some agents may benefit from trading probability shares. Second, outcomes may be "wasteful": agents may receive nothing even if acceptable items remain unallocated. We bound both sources of inefficiency, and show that each is eliminated by a suitable choice of \(k\): trades are never beneficial when \(k=1\), and waste is eliminated as \(k\) approaches infinity.
The wastefulness of the \(k\)ticket lottery has some benefits: agents with strong preferences may prefer \(k\)ticket lottery outcomes to those of any nonwasteful envyfree mechanism. These agents prefer small values of \(k\), while agents with weak preferences prefer large values of \(k\). Together, these results suggest that the \(k\)ticket lottery performs well under most circumstances, and may be suitable for other settings where items are rationed.

Xi Chen, Tim Randolph, Rocco Servedio, and Tim Sun.
"A Lower Bound on Cycle Finding in Sparse Digraphs." SODA 2020.
arXiv version
We consider the problem of finding a cycle in a sparse directed graph \(G\) that is promised to be far from acyclic, meaning that the smallest feedback arc set in \(G\) is large. We prove an informationtheoretic lower bound, showing that for \(N\)vertex graphs with constant outdegree any algorithm for this problem must make \(\tilde{\Omega}(N^{5/9})\) queries to an adjacency list representation of \(G\). In the language of property testing, our result is an \(\tilde{\Omega}(N^{5/9})\) lower bound on the query complexity of onesided algorithms for testing whether sparse digraphs with constant outdegree are far from acyclic. This is the first improvement on the \(\tilde{\Omega}(\sqrt{N})\) lower bound, implicit in Bender and Ron, which follows from a simple birthday paradox argument.

Marshall Ball and Tim Randolph.
"Communication Lower Bounds for ManyParty PSM." 2020.

Emilio Di Giacomo, William J. Lenhart, Giuseppe Liotta, Timothy W. Randolph and Alessandra Tappini.
"(k,p)Planarity: A Relaxation of Hybrid Planarity." WALCOM 2019.
arXiv version
We present a new model for hybrid planarity that relaxes existing hybrid representations. A graph \(G=(V,E)\) is \((k,p)\)planar if \(V\) can be partitioned into clusters of size at most \(k\) such that \(G\) admits a drawing where: (i) each cluster is associated with a closed, bounded planar region, called a cluster region; (ii) cluster regions are pairwise disjoint, (iii) each vertex \(v \in V\) is identified with at most \(p\) distinct points, called ports, on the boundary of its cluster region; (iv) each intercluster edge \((u,v)\in E\) is identified with a Jordan arc connecting a port of \(u\) to a port of \(v\); (v) intercluster edges do not cross or intersect cluster regions except at their endpoints. We first tightly bound the number of edges in a \((k,p)\)planar graph with \(p<k\). We then prove that \((4,1)\)planarity testing and \((2,2)\)planarity testing are NPcomplete problems. Finally, we prove that neither the class of \((2,2)\)planar graphs nor the class of \(1\)planar graphs contains the other, indicating that the \((k,p)\)planar graphs are a large and novel class.

Timothy W. Randolph.
"Asymptotically Optimal Bounds for \((t,2)\) Broadcast Domination on Finite Grids."
RoseHulman Undergraduate Mathematics Journal 20, 2019.
arXiv version
Let \(G=(V,E)\) be a graph and \(t,r\) be positive integers. The signal that a tower vertex \(T\) of signal strength \(t\) supplies to a vertex \(v\) is defined as \(sig(T,v)=max(t−dist(T,v),0)\), where \(dist(T,v)\) denotes the distance between the vertices \(v\) and \(T\). In 2015 Blessing, Insko, Johnson, and Mauretour defined a \((t,r)\) broadcast dominating set, or simply a \((t,r)\) broadcast, on \(G\) as a set \(T \subseteq V\) such that the sum of all signals received at each vertex \(v\in V\) from the set of towers \(T\) is at least \(r\). The \((t,r)\) broadcast domination number of a finite graph \(G\), denoted \(\gamma_{t,r}(G)\), is the minimum cardinality over all \((t,r)\) broadcasts for \(G\).
Recent research has focused on bounding the \((t,r)\) broadcast domination number for the \(m \times n\) grid graph \(G_{m,n}\). In 2014, Grez and Farina bounded the \(k\)distance domination number for grid graphs, equivalent to bounding \(\gamma_{t,1}(G_{m,n})\). In 2015, Blessing et al. established bounds on \(\gamma_{2,2}(G_{m,n})\), \(\gamma_{3,2}(G_{m,n})\), and \(\gamma_{3,3}(G_{m,n})\). In this paper, we take the next step and provide a tight upper bound on \(\gamma_{t,2}(G_{m,n})\) for all \(t>2\). We also prove the conjecture of Blessing et al. that their bound on \(\gamma_{3,2}(G_{m,n})\) is tight for large values of \(m\) and \(n\).

Benjamin F. Drews, Pamela E. Harris, and Timothy W. Randolph.
"Optimal \((t,r)\) Broadcasts on the Infinite Grid."
Discrete Applied Mathematics 255, 2018.
arXiv version
Let \(G=(V,E)\) be a graph and \(t,r\) be positive integers. The signal that a tower vertex \(T\) of signal strength \(t\) supplies to a vertex \(v\) is defined as \(sig(T,v)=max(t−dist(T,v),0)\), where \(dist(T,v)\) denotes the distance between the vertices \(v\) and \(T\). In 2015 Blessing, Insko, Johnson, and Mauretour defined a \((t,r)\) broadcast dominating set, or simply a \((t,r)\) broadcast, on \(G\) as a set \(T \subseteq V\) such that the sum of all signals received at each vertex \(v\in V\) from the set of towers \(T\) is at least \(r\). We say that \(T\) is optimal if \(T\) is minimal among all such sets \(T\). The cardinality of an optimal \((t,r)\) broadcast on a finite graph \(G\) is called the \((t,r)\) broadcast domination number of \(G\). The concept of \((t,r)\) broadcast domination generalizes the classical problem of domination on graphs. In fact, the \((2,1)\) broadcasts on a graph G are exactly the dominating sets of \(G\).
In their paper, Blessing et al. considered \((t,r) \in \{(2,2),(3,1),(3,2),(3,3)\}\) and gave optimal \((t,r)\) broadcasts on \(G_{m,n}\), the grid graph of dimension \(m\times n\), for small values of \(m\) and \(n\). They also provided upper bounds on the optimal \((t,r)\) broadcast numbers for grid graphs of arbitrary dimensions. In this paper, we define the density of a \((t,r)\) broadcast, which allows us to provide optimal \((t,r)\) broadcasts on the infinite grid graph for all \(t \geq 2\) and \(r=1,2\), and bound the density of the optimal \((t,3)\) broadcast for all \(t \geq 2\). In addition, we give a family of counterexamples to the conjecture of Blessing et al. that the optimal \((t,r)\) and \((t+1,r+2)\) broadcasts are identical for all \(t \geq 1\) and \(r \geq 1\) on the infinite grid.

Timothy W. Randolph, advised by William J. Lenhart.
"\((k,p)\)Planar Graphs: A Generalization of Planar Representations for Cluster Graphs."
2018.
PDF version