# Tim Randolph

As of Fall 2024, I'm an Assistant Professor in the Department of Computer Science at Harvey Mudd College. I recently completed a PhD in the Theory of Computation Group at Columbia University, advised by Rocco Servedio and Xi Chen.

I'm interested in efficient algorithms, chance, and the ways in which analytic thinking can solve everyday problems. My non-research interests include trail running, reading, and exploring the natural world.

• Faster exact and parameterized algorithms for hard computational problems
• Applications of additive structure in computer science
• Grading for equity and student agency in the CS classroom

Interested in pursuing a PhD in (theoretical) computer science? Here's a talk (slides) I gave for Columbia's Demystifying the Dissertation series on the experience of doing research in theory and PhD life more generally, and here's one (slides) from a later iteration of the series that discusses the application process in a little more detail. If you're ready to explore the possibilities of a PhD in CS, here's some advice on considering and applying to grad school that I wrote shortly after deciding to join Columbia.

If you'd like to chat, please email me at the address at the bottom of the page. I'll answer if time permits and I'm well-positioned to give you a helpful response.

## Research

• Tim Randolph. "Exact and Parameterized Algorithms for Subset Sum Problems." PhD Thesis, 2024. PDF
• We present a variety of exact and parameterized algorithms for Subset Sum and other related problems. The major contributions of this thesis include:

• 1. Average-case algorithms for Generalized Subset Sum, the problem that generalizes both Subset Sum and Equal Subset Sum, as well as structural results describing the parameter regime in which solutions exist. These results extend the application of the "Representation Method" and are the fastest known in this setting.
• 2. A proof that Either-Or Subset Sum, the problem of solving either Subset Sum or Equal Subset Sum, can be solved exponentially faster than time $$2^{0.5n}$$ in the worst case. In our view, this result illustrates the potential of the "structure vs. randomness" approach for Subset Sum.
• 3. Algorithms that solve worst-case Subset Sum faster than time $$2^{0.5n}$$ by a polynomial factor. These improvements on the best known exact algorithms for Subset Sum represent the successful application of "log shaving" techniques to the problem.
• 4. Algorithms for Subset Sum and $$k$$-SUM with constant doubling. When considered in terms of a novel parameterization in the doubling constant, Subset Sum admits an XP-algorithm, while $$k$$-SUM is Fixed-Parameter Tractable. We also show that Subset Sum is FPT in the doubling constant if and only if an instance $$\mathcal{I}$$ of Hyperplane-Constrained Integer Linear Programming with $$n$$ variables, $$m$$ constraints, and constraint matrix entries bounded by $$\Delta$$ can be solved in time $$\Delta^{O(m)} \cdot poly(|\mathcal{I}|)$$.
• Tim Randolph and Karol Węgrzycki. "Parameterized Algorithms on Integer Sets with Small Doubling: Freiman’s Theorem, Subset Sum and k-Sum." Preprint, 2024.
• Tim Randolph. "Participatory Governance in the Computer Science Theory Classroom." SIGCSE Technical Symposium 2024. ACM Digital Library
• We implemented pedagogical strategies designed to give students greater control over the use of class time and grading methods in a major-required computer science theory (CST) course. Our methodology addresses the challenges inherent in transferring more power to students in a lecture-based class with a curriculum that requires the sequential mastery of formal mathematical concepts.

We offered students increased control over four classroom variables: the degree of interactivity, the selection of in-class activities , increased emphasis on standards-based outcomes as opposed to averaging over all coursework, and the granularity of the grading schema used by TAs. In this experience report, we present our methodology, report on our classroom experience, and conclude that increasing student control over the undergraduate CST classroom via participatory governance can increase student motivation and encourage critical reflection in budding computer scientists.

• Xi Chen, Shivam Nadimpalli, Tim Randolph, Rocco Servedio, and Or Zamir. "Testing Sumsets is Hard." Preprint, 2024.
• Tim Randolph. "Exact Algorithms for Finding Sumsets." Preprint, 2023.
• Xi Chen, Yaonan Jin, Tim Randolph, and Rocco Servedio. "Subset Sum in time $$2^{n/2} / poly(n)$$." RANDOM/APPROX 2023. arXiv version
• A major goal in the area of exact exponential algorithms is to give an algorithm for the (worst-case) n-input Subset Sum problem that runs in time $$2^{(1/2−c)n}$$ for some constant $$c>0$$. In this paper we give a Subset Sum algorithm with worst-case running time $$O(2^{n/2⋅n−γ})$$ for a constant $$γ>0.5023$$ in standard word RAM or circuit RAM models. To the best of our knowledge, this is the first improvement on the classical "meet-in-the-middle" algorithm for worst-case Subset Sum, due to Horowitz and Sahni, which can be implemented in time $$O(2^{n/2})$$ in these memory models.

Our algorithm combines a number of different techniques, including the "representation method" introduced by Howgrave-Graham and Joux and subsequent adaptations of the method in Austrin, Kaski, Koivisto, and Nederlof, and Nederlof and Wegrzycki, and "bit-packing" techniques used in the work of Baran, Demaine, and Patrascu on subquadratic algorithms for 3SUM.

• Xi Chen, Yaonan Jin, Tim Randolph, and Rocco Servedio. "Average-Case 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 worst-case algorithm and the Meet-in-the-Middle 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 average-case version of this problem runs in~time $$|C|^{(0.5-c_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 not-too-large 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 Howgrave-Graham 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.

• Marshall Ball and Tim Randolph. "Communication Lower Bounds for Many-Party PSM." ITC 2022. Conference version
• 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 envy-free 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 information-theoretic 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 one-sided 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.

• 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 inter-cluster edge $$(u,v)\in E$$ is identified with a Jordan arc connecting a port of $$u$$ to a port of $$v$$; (v) inter-cluster 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 NP-complete 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." Rose-Hulman 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

## Teaching

• Instructor for Columbia COMS W3261: Computer Science Theory. Summer 2023. Course webpage
• My third time teaching of COMS W3261 focused on participatory governance in the CS classroom. See my Teaching Portfolio for more details.

• Teaching Development Program Advanced Track CTL TDP webpage
• The Teaching Development Program is a multiyear teaching certification in association with Columbia's Center for Teaching and Learning (CTL). It focuses on cultivating, documenting, and reflecting upon evidence-based, student-centered teaching. The TDP Advanced Track is the highest level teaching certification offered by the CTL.

• Instructor for Columbia COMS W3261: Computer Science Theory. Summer 2022. Course webpage
• My second time teaching COMS W3261, I focused on accessibility, effective use of virtual resources, and equity in grading. See my Teaching Portfolio for more details.

• Instructor for Columbia COMS W3261: Computer Science Theory. Summer 2021. Course webpage
• Mathematics teaches us to ask questions like "What is the value of f(x)?", "Do any objects of type Y exist?", and "Is Z true?" Theoretical computer science builds on this tradition, expanding our field of inquiry to include questions like "How much time (and other limited resources) does it take to evaluate f(x)?", "Can I write down formal instructions for finding a Y?", and "Can the truth of Z be computed?" In theoretical computer science, we define problems formally and think about how hard they are to solve under various models of computation.

• Peer lectures in Columbia CSCI 6261: Advanced Cryptography. 2/5/2020; 2/11/2020.
• Guest lecture in Columbia CSCI 4236: Computational Complexity. 11/1/2019.
• Substitute for Columbia CSOR 4231: Analysis of Algorithms. 10/24/19.
• TA for Columbia CSOR 4231: Analysis of Algorithms. Fall 2019.
• 2019-2020 Teaching Observation Fellowship. CTL TOF webpage
• Teaching Observation Fellows are Columbia University doctoral students who work closely with the Center for Teaching and Learning and with each other on a range of supportive, formative, peer-to-peer teaching observation activities.

-Columbia CTL
• Innovative Teaching Summer Institute (ITSI) Certification. CTL ITSI webpage
• The Innovative Teaching Summer Institute (ITSI) is a four-day series of collaborative workshops, discussions, and shared reflections all centered on the use of emerging teaching practices and technologies to support effective teaching. ITSI is a unique opportunity for graduate student instructors to work with peers from a variety of disciplines, discuss pedagogical priorities, connect with resources and support, and develop themselves as innovative teachers.

-Columbia CTL
• TA for Columbia COMS 3261: Computer Science Theory. Summer 2019.
• TA for Columbia COMS 6998-06: Computation and the Brain. Fall 2018.

## Service

• PhD Student Representative CS@CU
• Along with Clayton Sanford, I was the Computer Science PhD Student Representative at Columbia University from 2022-2024. We worked to make the department more transparent and accessible to PhD students by building knowledge bases and creating structured channels for feedback to faculty and administration.

• Emerging Scholars Program Program website
• With Roland Maio, I coordinated the Emerging Scholars Program at Columbia University from 2019-2022. We worked to broaden the diversity of student perspectives in the department and give CS majors at Columbia the tools to reason ethically about Computer Science.

• Demystifying the PhD / Demystifying the Dissertation Dem. PhD Dem. Dissertation;
• At Columbia, I focused my outreach work on making the path to graduate education easier to understand and navigate. I spoke as part of the Demystifying the PhD and Demystifying the Dissertation outreach lecture series.

• Mentorship CU WISC  BEARS;
• I have participated in undergraduate mentorship as part of Women in Science at Columbia's mentorship program and the Barnard BEARS (Better, Enhance, & Advance Research Series) program. I've also mentored high schoolers in research with Lumiere Education and the Williams College Alumni Mentorship Program.

• Student Workers of Columbia SWC-UAW website
• In 2021-2022, I assisted in organizing the Student Workers of Columbia. Living wages, fair benefits, and discrimination recourses ensure that student workers can do their jobs without facing poverty and harassment. Moreover, they make work in academia accessible to those with fewer outside resources.

• Pre-Submission Application Review Program CUCS PhD application page
• I'm a proud participant in the ongoing struggle to create a just, antiracist Computer Science department at Columbia. In this context, I have worked on expanded outreach to broaden the pool of research applicants and improving admissions practices and oversight. (If you're interested in recieving feedback on your personal statement for a PhD program, check out CUCS' Pre-Submission Application Review program.)

• CUCS Graduate Student Theory Retreat 2021 2019;

• Along with Clayton Sanford, I organized Columbia's first two annual theory student retreats! I'm now an organizer emeritus.

CONTACT: [FIRST INITIAL][LAST NAME]@HMC.EDU.