How do we help undergraduates master the rigorous material of Theory of Computing and Algorithms courses while keeping them engaged and confident, especially in the era of Generative AI? Additionally, what goals do educators of these courses believe are important? This panel's goal is to further the discussion of these questions. The panel consists of four educators from distinct institution types who will share evidence-based, classroom-tested strategies for these courses. After the panel gives their position statements, the moderator will guide a structured discussion on motivating abstract topics, assessment and feedback at scale, integrating contemporary tools, and aligning theory/algorithms courses with varied curricula. Specifically, the panel will discuss Generative AI and Large Language Models' place within these courses, the pedagogical implications of autograder usage in these courses, and broader learning goals educators should strive for in these courses.

We consider exact algorithms for Subset Balancing, a family of related problems that generalizes Subset Sum, Partition, and Equal Subset Sum. Specifically, given as input an integer vector x→ ∈ ℤn and a constant-size coefficient set C ⊂ ℤ, we seek a nonzero solution vector c→ ∈ Cn satisfying c→ · x→ = 0.

A subset S of the Boolean hypercube 𝔽₂ⁿ is a sumset if S = {a + b : a, b ∈ A} for some A ⊆ 𝔽₂ⁿ. Sumsets are central objects of study in additive combinatorics, where they play a role in several of the field’s most important results. We prove a lower bound of Ω(2^{n/2}) for the number of queries needed to test whether a Boolean function f:𝔽₂ⁿ → {0,1} is the indicator function of a sumset, ruling out an efficient testing algorithm for sumsets. Our lower bound for testing sumsets follows from sharp bounds on the related problem of shift testing, which may be of independent interest. We also give a near-optimal {2^{n/2} ⋅ poly(n)}-query algorithm for a smoothed analysis formulation of the sumset refutation problem. Finally, we include a simple proof that the number of different sumsets in 𝔽₂ⁿ is 2^{(1±o(1))2^{n-1}}.

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.

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} \cdot 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.

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∗(30.387n) in the average case, significantly improving over the O∗(30.488n) running time of the best known worst-case algorithm [MNPW19] and the Meet-in-the-Middle benchmark of O∗(30.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 ci from a set C to each input number xi such that Σi cixi = 0. Our algorithm for the average-case version of this problem runs in time for some positive constant c0, whenever C = {0, ± 1, …, ± d} or {±1, …,±d} for some positive integer d (with runtime 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 τ. Our approach relies on new structural results that characterize the probability that Σi cixi = τ has a solution c ∊ Cn when xi'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 [HGJ10]. 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.

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 , i.e., a subset of edges whose deletion results in an acyclic graph, 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 Ω̄(N 5/9 ) queries to an adjacency list representation of G . In the language of property testing, our result is an Ω̄(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 Ω (√ N ) lower bound, implicit in the work of Bender and Ron, which follows from a simple birthday paradox argument.

We analyze the parallel lottery, which is used to allocate hunting permits in the state of Alaska. Each participant is given 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 parallel lotteries approximate a competitive equilibrium from equal incomes (CEEI), which is Pareto efficient. When supply is moderate, parallel 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 giving applicants a suitable number of tickets k: trades are never beneficial when $k = 1$, and waste is eliminated as k approaches infinity.

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 (N5/9) queries to an adjacency list representation of G. In the language of property testing, our result is an (N5/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 lower bound, implicit in Bender and Ron [BR02], which follows from a simple birthday paradox argument.