Papers and Talks

# Ken Clarkson

## contact information

Kenneth L. Clarkson

Research Group Lead, Principles and Methodologies Group

Room B2-310, IBM Almaden Research Center, 650 Harry Road, San Jose, CA 95120

+14089271009

Research Group Lead, Principles and Methodologies Group

Room B2-310, IBM Almaden Research Center, 650 Harry Road, San Jose, CA 95120

+14089271009

## links

### Professional Associations

**Professional Associations:**ACM | IEEE | Society for Industrial and Applied Mathematics

### more information

**More information:**Papers and Talks | Journal of Computational Geometry | compgeom-announce mailing list | Journal of Discrete & Computational Geometry

## profile

My Papers and Talks.

My work has mainly been on geometric algorithms, and in particular on algorithms that have provable properties, but are relatively simple. Randomization is quite useful for this, whether via the Vapnik-Chervonenkis dimension, or using the general framework I introduced here. See, for example, a (somewhat dated) survey on randomized geometric algorithms.

I've also worked on randomized numerical linear algebra (see link at right).

My data structure for nearest neighbor searching (named *SB* after Sam * and Becky *): click the green square.

Some of my work:

- An improved algorithm for separable non-negative matrix factorization (and an approximation algorithm for the small-dimensional case);
- The first provably good algorithms for nearest-neighbor searching in metric spaces of bounded doubling dimension (I called it a "sphere-packing bound");
- The first sampling algorithm based on (
*L*_{1}) leverage scores with low relative residual error for (*L*_{1}) regression; - The first near-linear randomized simple polygon triangulation algorithm (with a simplified and generalized version as well);
- The first simple randomized small-dimensional exact linear programming algorithm.
- A provably good algorithm for determinants of integer matrices that effectively intermingles exact and floating-point arithmetic;
- The first algorithmic use of range-space epsilon-nets, with a generalization here.
- The introduction to computational geometry of Dudley's approximation result for convex bodies.

Sadly, I have *not* managed to:

- Be a former agent of the spider-aliens
- Play the banjo in
*Jimmy Chickenpants* - Be a bashful crooner whose career succeeds using the contributions of his girlfriend, who had received a million dollars from a mysterious reclusive billionaire, and who becomes afraid she has lost him, and to whom he at last returns
- Be an alter ego of Superman,or of an
*imaginary*Superman

And finally: sometimes we must bite the bull by the horns.