James King

PhD Student
  McGill University
    School of Computer Science

Contact Info

Email: jking@cs.mcgill.ca

At McGill:

Office: McConnell 109

Fax: (514) 398-3883
Office Phone: (514) 398-5485

James King
School of Computer Science
McGill University
3480 University Street
McConnell Engineering Building, Room 318
Montreal, Quebec, Canada
H3A 2A7

See this on Google Maps.

Welcome to my home page.  Since September 2005 I have been a PhD student in the Computer Science department at McGill University.  I do research in various theoretical areas under the guidance of my supervisor Luc Devroye.  I am sometimes mistaken for my twin brother Andrew.  Feel free to contact me if you need anything or if you're interested in working together.

Research Interests

I am primarily interested in computational geometry, especially guarding problems. I'm also interested in data structures & algorithms and several other areas of theory. At McGill I'm doing a fair amount of probabilistic analysis of algorithms and randomized algorithms, and I am starting to dabble in combinatorial geometry.

Publications

Fast Motif Recognition via Application of Statistical Thresholds
Christina Boucher and James King
Accepted to APBC 2010.
Terrain Guarding is NP-Hard
James King and Erik Krohn
Accepted to SODA10.
Random Hyperplane Search Trees
Luc Devroye, James King, and Colin McDiarmid.
SIAM Journal on Computing, Volume 38, Issue 6, pp. 2411-2425 (2009).
VC-Dimension of Visibility on Terrains
James King
In proceedings of CCCG 2008, pp. 27-30.
Neighbourhood Thresholding for Projection-Based Motif Discovery
James King, Warren Cheung, and Holger H. Hoos
Accepted to Bioinformatics pending revisions.
Realization of Degree 10 Minimum Weight Spanning Trees in 3-Space
James King
In proceedings of CCCG 2006, pp. 39-42. (Full version )
Minimizing the Number of Arcs Linking a Permutation of Points in the Plane
Stéphane Durocher, Chris Gray, and James King
In proceedings of CCCG 2006, pp. 181-184.
A 4-Approximation Algorithm for Guarding 1.5-Dimensional Terrains
James King
Lecture Notes in Computer Science (3887), pp. 629-640, 2006.
Fun-Sort--or the Chaos of Unordered Binary Search
Therese Biedl, Timothy Chan, Erik D. Demaine, Rudolf Fleischer, Mordecai Golin, James A. King, and J. Ian Munro
Discrete Applied Mathematics, volume 144, number 3, December 2004, pages 231-236.

Conference Talks

VC-Dimension of Visibility on Terrains
CCCG 2008: 20th Canadian Conference on Computational Geometry, Montreal, Canada, August 13-15, 2008.
Realization of Degree 10 Minimum Spanning Trees in 3-Space
CCCG 2006: 18th Canadian Conference on Computational Geometry, Kingston, Canada, August 14-16, 2006.
A 4-Approximation Algorithm for Guarding 1.5-Dimensional Terrains
LATIN 2006: Theoretical Informatics: 7th Latin American Symposium, Valdivia, Chile, March 20-24, 2006.

Unpublished Projects

[2005/08]Approximation Algorithms for Guarding 1.5-Dimensional Terrains (Master's Thesis)
[2004/12]Origami-Constructible Numbers (survey paper)
[2004/04]Succinct Data Structures for Tree Adjoining Grammars
[2003/12]A Survey of 3SUM-Hard Problems (survey paper)
[2003/04]Conductance and Rapidly Mixing Markov Chains (survey paper)

Curriculum Vitae

An HTML version of my CV is here. It was last updated October 2008.

Stuff