Kevin Woods
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
Research Subjects
Kevin Woods has a total of 22 co-authors. Here are the top co-authors by number of shared publications:
- Bjarke Hammersholt Roune
Department of Mathematics, Cornell University, New York, USA
2 shared publications - David Liben-Nowell
Carleton College
2 shared publications Mark E. Stout
2 shared publications- Sergi Elizalde
Department of Mathematics, Dartmouth College, Hanover, USA
2 shared publications - Steven V. Sam
University of California, San Diego, La Jolla, USA
2 shared publications - Tristram Bogart
Departamento de Matemáticas, Universidad de los Andes, Bogotá, Colombia
2 shared publications
Latest Publications
- Open Access
The generalized Frobenius problem via restricted partition functions
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 AccessThe generalized Frobenius problem via restricted partition functions
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
- 31 January 2022
- Published by Taylor & Francis in The American Mathematical Monthly
- Vol. 129 (3) , 203-222
A Plethora of Polynomials: A Toolbox for Counting Problems
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 . 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.- 31 January 2022
- Published by Taylor & Francis in The American Mathematical Monthly
- Vol. 129 (3) , 203-222
Open AccessA Plethora of Polynomials: A Toolbox for Counting Problems
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 . 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. - 10 February 2021
- Published by Springer Nature in Semigroup Forum
- Vol. 102 (2) , 340-356
Periodic behavior in families of numerical and affine semigroups via parametric Presburger arithmetic
- 10 February 2021
- Published by Springer Nature in Semigroup Forum
- Vol. 102 (2) , 340-356
Periodic behavior in families of numerical and affine semigroups via parametric Presburger arithmetic
- Open Access
- 24 January 2019
- Published by Ubiquity Press, Ltd. in Journal of Cognition
- Vol. 2 (1) , 2
The Danger of Testing by Selecting Controlled Subsets, with Applications to Spoken-Word Recognition
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.
- 24 January 2019
- Published by Ubiquity Press, Ltd. in Journal of Cognition
- Vol. 2 (1) , 2
Open AccessThe Danger of Testing by Selecting Controlled Subsets, with Applications to Spoken-Word Recognition
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
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 AccessThe Parametric Frobenius Problem
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
- 14 April 2015
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 22 (2) , P2.36
The Parametric Frobenius Problem
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.- 14 April 2015
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 22 (2) , P2.36
Open AccessThe Parametric Frobenius Problem
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
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 AccessThe unreasonable ubiquitousness of quasi-polynomials
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
- 13 January 2014
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 21 (1) , P1.44
The Unreasonable Ubiquitousness of Quasi-Polynomials
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''.- 13 January 2014
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 21 (1) , P1.44
Open AccessThe Unreasonable Ubiquitousness of Quasi-Polynomials
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''. - 1 January 2012
- Published by Springer Nature
- p. 568-579
Computing Shapley Value in Supermodular Coalitional Games
- 1 January 2012
- Published by Springer Nature
- p. 568-579
Computing Shapley Value in Supermodular Coalitional Games
- 26 September 2011
- Published by Cambridge University Press (CUP)
- p. 126-164
Qadisiyyah Saddam (The Iran-Iraq War)
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.
- 26 September 2011
- Published by Cambridge University Press (CUP)
- p. 126-164
Qadisiyyah Saddam (The Iran-Iraq War)
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.