KWKevin Woods

Kevin Woods

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Kevin Woods has a total of 22 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    The generalized Frobenius problem via restricted partition functions

    by Kevin Woods

    Given relatively prime positive integers, $a_1,\ldots,a_n$, the Frobenius number is the largest integer with no representations of the form $a_1x_1+\cdots+a_nx_n$ with nonnegative integers $x_i$. This classical value has recently been generalized: given a nonnegative integer $k$, what is the largest integer with at most $k$ such representations? Other classical values can be generalized too: for example, how many nonnegative integers are representable in at most $k$ ways? For sufficiently large $k$, we give formulas for these values by understanding the level sets of the restricted partition function (the function $f(t)$ giving the number of representations of $t$). Furthermore, we give the full asymptotics of all of these values, as well as reprove formulas for some special cases (such as the $n=2$ case and a certain extremal family from the literature). Finally, we obtain the first two leading terms of the restricted partition function as a so-called quasi-polynomial.

  • Open Access

    A Plethora of Polynomials: A Toolbox for Counting Problems

    by Tristram Bogart, Kevin Woods

    A wide variety of problems in combinatorics and discrete optimization depend on counting the set S of integer points in a polytope, or in some more general object constructed via discrete geometry and first-order logic. We take a tour through numerous problems of this type. In particular, we consider families of such sets St depending on one or more integer parameters t, and analyze the behavior of the function f(t)=|St|. In the examples that we investigate, this function exhibits surprising polynomial-like behavior. We end with two broad theorems detailing settings where this polynomial-like behavior must hold. The plethora of examples illustrates the framework in which this behavior occurs and also gives an intuition for many of the proofs, helping us create a toolbox for counting problems like these.

  • Open Access

    The Danger of Testing by Selecting Controlled Subsets, with Applications to Spoken-Word Recognition

    by David Liben-Nowell, Julia Strand, Alexa Sharp, Tom Wexler, Kevin Woods

    When examining the effects of a continuous variable x on an outcome y, a researcher might choose to dichotomize on x, dividing the population into two sets-low x and high x-and testing whether these two subpopulations differ with respect to y. Dichotomization has long been known to incur a cost in statistical power, but there remain circumstances in which it is appealing: an experimenter might use it to control for confounding covariates through subset selection, by carefully choosing a subpopulation of Low and a corresponding subpopulation of High that are balanced with respect to a list of control variables, and then comparing the subpopulations' y values. This "divide, select, and test" approach is used in many papers throughout the psycholinguistics literature, and elsewhere. Here we show that, despite the apparent innocuousness, these methodological choices can lead to erroneous results, in two ways. First, if the balanced subsets of Low and High are selected in certain ways, it is possible to conclude a relationship between x and y not present in the full population. Specifically, we show that previously published conclusions drawn from this methodology-about the effect of a particular lexical property on spoken-word recognition-do not in fact appear to hold. Second, if the balanced subsets of Low and High are selected randomly, this methodology frequently fails to show a relationship between x and y that is present in the full population. Our work uncovers a new facet of an ongoing research effort: to identify and reveal the implicit freedoms of experimental design that can lead to false conclusions.


  • Open Access

    The Parametric Frobenius Problem

    by Bjarke Hammersholt Roune, Kevin Woods

    Given relatively prime positive integers a_1,...,a_n, the Frobenius number is the largest integer that cannot be written as a nonnegative integer combination of the a_i. We examine the parametric version of this problem: given a_i=a_i(t) as functions of t, compute the Frobenius number as a function of t. A function f is a quasi-polynomial if there exists a period m and polynomials f_0,...,f_{m-1} such that f(t)=f_{t mod m}(t) for all positive integers t. We conjecture that, if the a_i(t) are polynomials (or quasi-polynomials) in t, then the Frobenius number agrees with a quasi-polynomial, for sufficiently large t. We prove this in the case where the a_i(t) are linear functions, and also prove it in the case where n (the number of generators) is at most 3.

  • Open Access

    The Parametric Frobenius Problem

    by Bjarke Hammersholt Roune, Kevin Woods

    Given relatively prime positive integers $a_1,\ldots,a_n$, the Frobenius number is the largest integer that cannot be written as a nonnegative integer combination of the $a_i$. We examine the parametric version of this problem: given $a_i=a_i(t)$ as functions of $t$, compute the Frobenius number as a function of $t$. A function $f:\mathbb{Z}_+\rightarrow\mathbb{Z}$ is a quasi-polynomial if there exists a period $m$ and polynomials $f_0,\ldots,f_{m-1}$ such that $f(t)=f_{t\bmod m}(t)$ for all $t$. We conjecture that, if the $a_i(t)$ are polynomials (or quasi-polynomials) in $t$, then the Frobenius number agrees with a quasi-polynomial, for sufficiently large $t$. We prove this in the case where the $a_i(t)$ are linear functions, and also prove it in the case where $n$ (the number of generators) is at most 3.


  • Open Access

    The unreasonable ubiquitousness of quasi-polynomials

    by Kevin Woods

    A function g, with domain the natural numbers, is a quasi-polynomial if there exists a period m and polynomials p_0,p_1,...,p_{m-1} such that g(t)=p_i(t) for t=i mod m. Quasi-polynomials classically -- and "reasonably" -- appear in Ehrhart theory and in other contexts where one examines a family of polyhedra, parametrized by a variable t, and defined by linear inequalities of the form a_1x_1+...+a_dx_d <= b(t). Recent results of Chen, Li, Sam; Calegari, Walker; and Roune, Woods show a quasi-polynomial structure in several problems where the a_i are also allowed to vary with t. We discuss these "unreasonable" results and conjecture a general class of sets that exhibit various (eventual) quasi-polynomial behaviors: sets S_t of d-tuples of natural numbers that are defined with quantifiers ("for all", "there exists"), boolean operations (and, or, not), and statements of the form a_1(t)x_1+...+a_d(t)x_d <= b(t), where a_i(t) and b(t) are polynomials in t. These sets are a generalization of sets defined in the Presburger arithmetic. We prove several relationships between our conjectures, and we prove several special cases of the conjectures. The title is a play on Eugene Wigner's "The unreasonable effectiveness of mathematics in the natural sciences''.

  • Open Access

    The Unreasonable Ubiquitousness of Quasi-Polynomials

    by Kevin Woods

    A function $g$, with domain the natural numbers, is a quasi-polynomial if there exists a period $m$ and polynomials $p_0,p_1,\ldots,p_{m-1}$ such that $g(t)=p_i(t)$ for $t\equiv i\bmod m$. Quasi-polynomials classically - and "reasonably'' - appear in Ehrhart theory and in other contexts where one examines a family of polyhedra, parametrized by a variable $t$, and defined by linear inequalities of the form $a_1x_1+\cdots+a_dx_d\le b(t)$. Recent results of Chen, Li, Sam; Calegari, Walker; and Roune, Woods show a quasi-polynomial structure in several problems where the $a_i$ are also allowed to vary with $t$. We discuss these "unreasonable'' results and conjecture a general class of sets that exhibit various (eventual) quasi-polynomial behaviors: sets $S_t\subseteq\mathbb{N}^d$ that are defined with quantifiers ($\forall$, $\exists$), boolean operations (and, or, not), and statements of the form $a_1(t)x_1+\cdots+a_d(t)x_d \le b(t)$, where $a_i(t)$ and $b(t)$ are polynomials in $t$. These sets are a generalization of sets defined in the Presburger arithmetic. We prove several relationships between our conjectures, and we prove several special cases of the conjectures. The title is a play on Eugene Wigner's "The unreasonable effectiveness of mathematics in the natural sciences''.


  • Computing Shapley Value in Supermodular Coalitional Games

    by David Liben-Nowell, Alexa Sharp, Tom Wexler, Kevin Woods


  • Qadisiyyah Saddam (The Iran-Iraq War)

    by Kevin M. Woods, David D. Palkki, Mark E. Stout

    Iran has planned animosity for us from the beginning, as if the change [Revolution] that took place in Iran was designed with the intention to be against the interest of Iraq…[W]e have treated them more kindly than they deserve. – Saddam Hussein, November 1979 On 22 September 1980, after months of border skirmishes, Saddam's army streamed into Iran. Though hoping for a quick victory, Saddam soon found himself mired in an ill-conceived conflict against a powerful and motivated opponent. For eight long years, hundreds of thousands of soldiers fought in the marshes, mountains, and deserts dividing the two countries. As the conflict wore on, Saddam's desperate military employed chemical weapons, bombarded Iranian cities, and brutalized ethnic minorities. Iran responded by sending human waves of teenage zealots storming across Iraqi minefields and targeting neutral shipping in the Gulf. By the time both sides accepted a UN cease-fire in August 1988, the fighting had led to nearly a million casualties, thousands more sat in prison camps, and the region was poorer by billions of dollars. Saddam's glib conversations in this chapter belie the terrible suffering his words inflicted.