Author name cluster

David Kirkpatrick

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

1 author row

JMLR Journal 2023 Journal Article

On Batch Teaching Without Collusion

Shaun Fallat
David Kirkpatrick
Hans U. Simon
Abolghasem Soltani
Sandra Zilles

Formal models of learning from teachers need to respect certain criteria to avoid collusion. The most commonly accepted notion of collusion-avoidance was proposed by Goldman and Mathias (1996), and various teaching models obeying their criterion have been studied. For each model $M$ and each concept class $\mathcal{C}$, a parameter $M$-TD$(\mathcal{C})$ refers to the teaching dimension of concept class $\mathcal{C}$ in model $M$---defined to be the number of examples required for teaching a concept, in the worst case over all concepts in $\mathcal{C}$. This paper introduces a new model of teaching, called no-clash teaching, together with the corresponding parameter NCTD$(\mathcal{C})$. No-clash teaching is provably optimal in the strong sense that, given any concept class $\mathcal{C}$ and any model $M$ obeying Goldman and Mathias's collusion-avoidance criterion, one obtains NCTD$(\mathcal{C})\le M$-TD$(\mathcal{C})$. We also study a corresponding notion NCTD$^+$ for the case of learning from positive data only, establish useful bounds on NCTD and NCTD$^+$, and discuss relations of these parameters to other complexity parameters of interest in computational learning theory. We further argue that Goldman and Mathias's collusion-avoidance criterion may in some settings be too weak in that it admits certain forms of interaction between teacher and learner that could be considered collusion in practice. Therefore, we introduce a strictly stronger notion of collusion-avoidance and demonstrate that the well-studied notion of Preference-based Teaching is optimal among all teaching schemes that are strongly collusion-avoiding on all finite subsets of a given concept class. [abs] [ pdf ][ bib ] &copy JMLR 2023. ( edit, beta )

PDF Details

TCS Journal 2018 Journal Article

Swapping colored tokens on graphs

Katsuhisa Yamanaka
Takashi Horiyama
J. Mark Keil
David Kirkpatrick
Yota Otachi
Toshiki Saitoh
Ryuhei Uehara
Yushi Uno

We investigate the computational complexity of the following problem. We are given a graph in which each vertex has an initial and a target color. Each pair of adjacent vertices can swap their current colors. Our goal is to perform the minimum number of swaps so that the current and target colors agree at each vertex. When the colors are chosen from { 1, 2, …, c }, we call this problem c -Colored Token Swapping since the current color of a vertex can be seen as a colored token placed on the vertex. We show that c -Colored Token Swapping is NP-complete for c = 3 even if input graphs are restricted to connected planar bipartite graphs of maximum degree 3. We then show that 2-Colored Token Swapping can be solved in polynomial time for general graphs and in linear time for trees. Besides, we show that, the problem for complete graphs is fixed-parameter tractable when parameterized by the number of colors, while it is known to be NP-complete when the number of colors is unbounded.

Details DOI

TCS Journal 2014 Journal Article

Multi-Path Algorithms for minimum-colour path problems with applications to approximating barrier resilience

David Yu Cheng Chan
David Kirkpatrick

Let G be a graph with zero or more colours assigned to its vertices, and let v s and v t be two vertices of G. The minimum-colour path problem is to determine the minimum over all v s – v t paths of the number of colours used, where a colour is considered used if it is assigned to any vertex in the path. Although this problem is NP-hard with strong hardness of approximation results, many problems can be formulated as instances of the minimum-colour path problem with additional constraints which may be exploited to allow polynomial-time solutions or close approximations. We introduce a family of approximation algorithms, referred to as the Multi-Path Algorithms, for minimum-colour path problems, and go on to show examples of constraints which would allow polynomial-time solutions or constant factor approximations. In particular, we describe applications to variants of the barrier resilience problem: given a pair of points s and t and an arrangement A of n regions in the plane, the problem is to determine the minimum over all s – t paths of the number of regions intersected. We show how to reduce the barrier resilience problem to the minimum-colour path problem, and go on to show that the Multi-Path Algorithms guarantee a 1. 5 approximation when regions are unit disks and s, t are separated by at least 2 3.

Details DOI

TCS Journal 1983 Journal Article

Upper bounds for sorting integers on random access machines

David Kirkpatrick
Stefan Reisch

The complexity of integer sorting is investigated on two random access machine (RAM) models. The main results show that (i) on a RAM with addition, subtraction, multiplication and integer division, n integers in the range [0, 2 cn ) can be sorted in O(n(1 + log c)) steps, (ii) on a RAM with addition, subtraction, and left and right shifts, n integers in any range can be sorted in linear time, and (iii) on either of the above models, n integers in the range [0, nc can be sorted in O(n(1 + log c)) steps, even if all register addresses and capacities are bounded above by nc.

Details DOI