Select a publication 
Show 
Title 
Venue 
Rating 
Date 

Conference paper
Kenneth L. Clarkson, David P. Woodruff.
LowRank PSD Approximation in InputSparsity Time.

Proceedings of the TwentyEighth Annual ACMSIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 1619 2017 
(0)

2017 

Conference paper
Haim Avron, Kenneth L. Clarkson, David P. Woodruff.
Sharper Bounds for Regularized Data Fitting.

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2017, August 1618, 2017, Berkeley, CA, USA 2017 
(0)

2017 

Conference paper
Kenneth L. Clarkson, János Pach, Günter M. Ziegler.
Thirtieth Anniversary Note from the Editors in Chief.

Discrete Computational Geometry 2016, Volume 55 
(0)

2016 

Conference paper
Kenneth L. Clarkson, Petros Drineas, Malik MagdonIsmail, Michael W. Mahoney, Xiangrui Meng, David P. Woodruff.
The Fast Cauchy Transform and Faster Robust Linear Regression.

SIAM J. Comput. 2016, Volume 45 
(0)

2016 

Conference paper
Haim Avron, Kenneth L. Clarkson, David P. Woodruff.
Faster Kernel Ridge Regression Using Sketching and Preconditioning.

CoRR 2016, Volume 0 
(0)

2016 

Conference paper
Haim Avron, Kenneth L. Clarkson, David P. Woodruff.
Sharper Bounds for Regression and LowRank Approximation with Regularization.

CoRR 2016, Volume 0 
(0)

2016 

Conference paper
Kenneth L. Clarkson, David P. Woodruff.
Sketching for

Proceedings of the TwentySixth Annual ACMSIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 46, 2015 2015 
(0)

2015 

Conference paper
Kenneth L. Clarkson, David P. Woodruff.
Input Sparsity and Hardness for Robust Subspace Approximation.

CoRR 2015, Volume 0 
(0)

2015 

Conference paper
Kenneth L. Clarkson, David P. Woodruff.
Input Sparsity and Hardness for Robust Subspace Approximation.

IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 1720 October, 2015 2015 
(0)

2015 

Conference paper
Kenneth L. Clarkson, Wolfgang Mulzer, Seshadhri Comandur.
SelfImproving Algorithms for Coordinatewise Maxima and Convex Hulls.

SIAM J. Comput. 2014, Volume 43 
(0)

2014 

Conference paper
Kenneth L. Clarkson, Petros Drineas, Malik MagdonIsmail, Michael W. Mahoney, Xiangrui Meng, David P. Woodruff.
The Fast Cauchy Transform and Faster Robust Linear Regression.

Proceedings of the TwentyFourth Annual ACMSIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 68, 2013 2013 
(0)

2013 

Conference paper
Kenneth L. Clarkson, David P. Woodruff.
Low rank approximation and regression in input sparsity time.

Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 14, 2013 2013 
(0)

2013 

Conference paper
Jingjing Zheng, Steven L. Mielke, Kenneth L. Clarkson, Donald G. Truhlar.
MSTor: A program for calculating partition functions, free energies, enthalpies, entropies, and heat capacities of complex molecules including torsional anharmonicity.

Computer Physics Communications 2012, Volume 183 
(0)

2012 

Conference paper
Kenneth L. Clarkson, Wolfgang Mulzer, Seshadhri Comandur.
Selfimproving algorithms for coordinatewise maxima.

Symposuim on Computational Geometry 2012, SoCG '12, Chapel Hill, NC, USA, June 1720, 2012 2012 
(0)

2012 

Conference paper
Kenneth L. Clarkson, Petros Drineas, Malik MagdonIsmail, Michael W. Mahoney, Xiangrui Meng, David P. Woodruff.
The Fast Cauchy Transform: with Applications to Basis Construction, Regression, and Subspace Approximation in L1

CoRR 2012, Volume 0 
(0)

2012 

Conference paper
Kenneth L. Clarkson, Wolfgang Mulzer, Seshadhri Comandur.
Selfimproving Algorithms for Coordinatewise Maxima

CoRR 2012, Volume 0 
(0)

2012 

Conference paper
Kenneth L. Clarkson, David P. Woodruff.
Low Rank Approximation and Regression in Input Sparsity Time

CoRR 2012, Volume 0 
(0)

2012 

Conference paper
Kenneth L. Clarkson, Elad Hazan, David P. Woodruff.
Sublinear optimization for machine learning.

J. ACM 2012, Volume 59 
(0)

2012 

Journal article
Kenneth L. Clarkson, Wolfgang Mulzer, Seshadhri Comandur.
Selfimproving Algorithms for CoordinateWise Maxima and Convex Hulls

CoRR 2012, Volume 0 
(0)

2012 

Journal article
Chandra Chekuri, Kenneth L. Clarkson, Sariel HarPeled.
On the set multicover problem in geometric settings.

ACM Transactions on Algorithms 2012, Volume 9 
(0)

2012 

Conference paper
Nir Ailon, Bernard Chazelle, Kenneth L. Clarkson, Ding Liu, Wolfgang Mulzer, C. Seshadhri.
SelfImproving Algorithms.

SIAM J. Comput. 2011, Volume 40 
(0)

2011 

Conference paper
Kenneth L. Clarkson, Wolfgang Mulzer, C. Seshadhri.
Selfimproving Algorithms for Convex Hulls.

Proceedings of the TwentyFirst Annual ACMSIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 1719, 2010 2010 
(0)

2010 

Conference paper
Kenneth L. Clarkson.
Coresets, sparse greedy approximation, and the FrankWolfe algorithm.

ACM Transactions on Algorithms 2009, Volume 6 
(0)

2010 

Journal article
Kenneth L. Clarkson, Elad Hazan, David P. Woodruff.
Sublinear Optimization for Machine Learning

CoRR 2010, Volume 0 
(0)

2010 

Conference paper
Kenneth L. Clarkson, Elad Hazan, David P. Woodruff.
Sublinear Optimization for Machine Learning.

51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 2326, 2010, Las Vegas, Nevada, USA 2010 
(0)

2010 

Journal article
Kenneth L. Clarkson, Günter Rote.
Welcome from the EditorsinChief.

JoCG 2010, Volume 1 
(0)

2010 

Conference paper
Barna Saha, Ioana Stanoi, Kenneth L. Clarkson.
Schema covering: a step towards enabling reuse in information integration.

Proceedings of the 26th International Conference on Data Engineering, ICDE 2010, March 16, 2010, Long Beach, California, USA 2010 
(0)

2010 

Conference paper
Chandra Chekuri, Kenneth L. Clarkson, Sariel HarPeled.
On the set multicover problem in geometric settings.

Proceedings of the 25th ACM Symposium on Computational Geometry, Aarhus, Denmark, June 810, 2009 2009 
(0)

2009 

Conference paper
Kenneth L. Clarkson, David P. Woodruff.
Numerical linear algebra in the streaming model.

Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31  June 2, 2009 2009 
(0)

2009 

Conference paper
Nir Ailon, Bernard Chazelle, Kenneth L. Clarkson, Ding Liu, Wolfgang Mulzer, C. Seshadhri.
SelfImproving Algorithms

CoRR 2009, Volume 0 
(0)

2009 

Conference paper
Chandra Chekuri, Kenneth L. Clarkson, Sariel HarPeled.
On the Set MultiCover Problem in Geometric Settings

CoRR 2009, Volume 0 
(0)

2009 

Conference paper
Kenneth L. Clarkson.
Geometry is everywhere, part XLVII: metrics, nets, dimensions, and measures.

Proceedings of the 24th ACM Symposium on Computational Geometry, College Park, MD, USA, June 911, 2008 2008 
(0)

2008 

Conference paper
Kenneth L. Clarkson.
Tighter bounds for random projections of manifolds.

Proceedings of the 24th ACM Symposium on Computational Geometry, College Park, MD, USA, June 911, 2008 2008 
(0)

2008 

Conference paper
Kenneth L. Clarkson, C. Seshadhri.
Selfimproving algorithms for delaunay triangulations.

Proceedings of the 24th ACM Symposium on Computational Geometry, College Park, MD, USA, June 911, 2008 2008 
(0)

2008 

Conference paper
Kenneth L. Clarkson.
Coresets, sparse greedy approximation, and the FrankWolfe algorithm.

Proceedings of the Nineteenth Annual ACMSIAM Symposium on Discrete Algorithms, SODA 2008, San Francisco, California, USA, January 2022, 2008 2008 
(0)

2008 

Conference paper
Mihai Badoiu, Kenneth L. Clarkson.
Optimal coresets for balls.

Comput. Geom. 2008, Volume 40 
(0)

2008 

Conference paper
Kenneth L. Clarkson, K. Georg Hampel, John D. Hobby.
Modeling UpLink Power Control with Outage Probabilities.

Proceedings of the 66th IEEE Vehicular Technology Conference, VTC Fall 2007, 30 September  3 October 2007, Baltimore, MD, USA 2007 
(0)

2007 

Conference paper
Kenneth L. Clarkson, John D. Hobby.
Ocelot's Knapsack Calculations for Modeling Power Amplifier and Walsh Code Limits.

Proceedings of the 66th IEEE Vehicular Technology Conference, VTC Fall 2007, 30 September  3 October 2007, Baltimore, MD, USA 2007 
(0)

2007 

Conference paper
Kenneth L. Clarkson, Kasturi R. Varadarajan.
Improved Approximation Algorithms for Geometric Set Cover.

Discrete Computational Geometry 2007, Volume 37 
(0)

2007 

Conference paper
Kenneth L. Clarkson.
Building triangulations using epsilonnets.

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, May 2123, 2006 2006 
(0)

2006 

Conference paper
Kenneth L. Clarkson, Kasturi R. Varadarajan.
Improved approximation algorithms for geometric set cover.

Proceedings of the 21st ACM Symposium on Computational Geometry, Pisa, Italy, June 68, 2005 2005 
(0)

2005 

Conference paper
Kenneth L. Clarkson, Kasturi R. Varadarajan.
Improved Approximation Algorithms for Geometric Set Cover

CoRR 2005, Volume 0 
(0)

2005 

Conference paper
Mihai Badoiu, Kenneth L. Clarkson.
Smaller coresets for balls.

SODA 2003 
(0)

2003 

Conference paper
Sem C. Borst, Kenneth L. Clarkson, John M. Graybeal, Harish Viswanathan, Philip A. Whiting.
Userlevel QoS and traffic engineering for 3G wireless 1xEVDO systems.

Bell Labs Technical Journal 2003, Volume 8 
(0)

2003 

Journal article
Kenneth L. Clarkson, Wim Sweldens, Alice Zheng.
Fast multipleantenna differential decoding.

IEEE Transactions on Communications 2001, Volume 49 
(0)

2001 

Conference paper
Kenneth L. Clarkson.
Nearest Neighbor Queries in Metric Spaces.

Discrete Computational Geometry 1999, Volume 22 
(0)

1999 

Conference paper
Kenneth L. Clarkson.
Guest Editor's Foreword.

Discrete Computational Geometry 1999, Volume 22 
(0)

1999 

Conference paper
Kenneth L. Clarkson.
SODA '95 Papers.

J. Algorithms 1998, Volume 29 
(0)

1998 

Conference paper
Kenneth L. Clarkson.
Nearest Neighbor Queries in Metric Spaces.

STOC 1997 
(0)

1997 

Conference paper
Kenneth L. Clarkson, David Eppstein, Gary L. Miller, Carl Sturtivant, ShangHua Teng.
Approximating center points with iterative Radon points.

Int. J. Comput. Geometry Appl. 1996, Volume 6 
(0)

1996 

Conference paper
Kenneth L. Clarkson.
Las Vegas Algorithms for Linear and Integer Programming when the Dimension is Small.

J. ACM 1995, Volume 42 
(0)

1995 

Conference paper
Kenneth L. Clarkson.
An Algorithm for Approximate ClosestPoint Queries.

Symposium on Computational Geometry 1994 
(0)

1994 

Conference paper
Kenneth L. Clarkson.
More OutputSensitive Geometric Algorithms (Extended Abstract)

35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mexico, USA, 2022 November 1994 1994 
(0)

1994 

Conference paper
Kenneth L. Clarkson, David Eppstein, Gary L. Miller, Carl Sturtivant, ShangHua Teng.
Approximating Center Points with Iterated Radon Points.

Symposium on Computational Geometry 1993 
(0)

1993 

Conference paper
Kenneth L. Clarkson.
Algorithms for Polytope Covering and Approximation.

Algorithms and Data Structures, Third Workshop, WADS '93, Montréal, Canada, August 1113, 1993, Proceedings 1993 
(0)

1993 

Conference paper
Jon Louis Bentley, Kenneth L. Clarkson, David B. Levine.
Fast Linear ExpectedTime Algorithms for Computing Maxima and Convex Hulls.

Algorithmica 1993, Volume 9 
(0)

1993 

Conference paper
Kenneth L. Clarkson, Kurt Mehlhorn, Raimund Seidel.
Four Results on Randomized Incremental Constructions.

Comput. Geom. 1993, Volume 3 
(0)

1993 

Conference paper
Kenneth L. Clarkson.
A Bound on Local Minima of Arrangements that Implies the Upper Bound Theorem.

Discrete Computational Geometry 1993, Volume 10 
(0)

1993 

Conference paper
Kenneth L. Clarkson.
Safe and Effective Determinant Evaluation

33rd Annual Symposium on Foundations of Computer Science, Pittsburgh, Pennsylvania, USA, 2427 October 1992 1992 
(0)

1992 

Conference paper
Kenneth L. Clarkson, Kurt Mehlhorn, Raimund Seidel.
Four Results on Randomized Incremental Constructions.

STACS 92, 9th Annual Symposium on Theoretical Aspects of Computer Science, Cachan, France, February 1315, 1992, Proceedings 1992 
(0)

1992 

Conference paper
Kenneth L. Clarkson, Richard Cole, Robert E. Tarjan.
Randomized parallel algorithms for trapezoidal diagrams.

Int. J. Comput. Geometry Appl. 1992, Volume 2 
(0)

1992 

Conference paper
Kenneth L. Clarkson, Richard Cole, Robert E. Tarjan.
Erratum: Randomized parallel algorithms for trapezoidal diagrams.

Int. J. Comput. Geometry Appl. 1992, Volume 2 
(0)

1992 

Conference paper
Kenneth L. Clarkson, Richard Cole, Robert E. Tarjan.
Randomized Parallel Algorithms for Trapezoidal Diagrams.

Symposium on Computational Geometry 1991 
(0)

1991 

Conference paper
Kenneth L. Clarkson.
Approximation Algorithms for Planar Traveling Salesman Tours and MinimumLength Triangulations.

SODA 1991 
(0)

1991 

Conference paper
Kenneth L. Clarkson, Herbert Edelsbrunner, Leonidas J. Guibas, Micha Sharir, Emo Welzl.
Combinatorial Complexity Bounds for Arrangement of Curves and Spheres.

Discrete Computational Geometry 1990, Volume 5 
(0)

1990 

Conference paper
Jon Louis Bentley, Kenneth L. Clarkson, David B. Levine.
Fast Linear ExpectedTime Algorithms for Computing Maxima and Convex Hulls.

SODA 1990 
(0)

1990 

Conference paper
Kenneth L. Clarkson.
An Algorithm for Geometric Minimum Spanning Trees Requiring Nearly Linear Expected Time.

Algorithmica 1989, Volume 4 
(0)

1989 

Conference paper
Kenneth L. Clarkson, Peter W. Shor.
Application of Random Sampling in Computational Geometry, II.

Discrete Computational Geometry 1989, Volume 4 
(0)

1989 

Conference paper
Kenneth L. Clarkson, Robert E. Tarjan, Christopher J. Van Wyk.
A Fast Las Vegas Algorithm for Triangulating a Simple Polygon.

Discrete Computational Geometry 1989, Volume 4 
(0)

1989 

Conference paper
Kenneth L. Clarkson.
Applications of Random Sampling in Computational Geometry, II.

Symposium on Computational Geometry 1988 
(0)

1988 

Conference paper
Kenneth L. Clarkson, Peter W. Shor.
Algorithms for Diametral Pairs and Convex Hulls That Are Optimal, Randomized, and Incremental.

Symposium on Computational Geometry 1988 
(0)

1988 

Conference paper
Kenneth L. Clarkson, Robert E. Tarjan, Christopher J. Van Wyk.
A Fast Las Vegas Algorithm for Triangulating a Simple Polygon.

Symposium on Computational Geometry 1988 
(0)

1988 

Conference paper
Kenneth L. Clarkson.
A Las Vegas Algorithm for Linear Programming When the Dimension Is Small

29th Annual Symposium on Foundations of Computer Science, White Plains, New York, USA, 2426 October 1988 1988 
(0)

1988 

Conference paper
Kenneth L. Clarkson, Herbert Edelsbrunner, Leonidas J. Guibas, Micha Sharir, Emo Welzl.
Combinatorial Complexity Bounds for Arrangements of Curves and Surfaces

29th Annual Symposium on Foundations of Computer Science, White Plains, New York, USA, 2426 October 1988 1988 
(0)

1988 

Conference paper
Kenneth L. Clarkson.
A Randomized Algorithm for ClosestPoint Queries.

SIAM J. Comput. 1988, Volume 17 
(0)

1988 

Conference paper
Kenneth L. Clarkson, Sanjiv Kapoor, Pravin M. Vaidya.
Rectilinear Shortest Paths Through Polygonal Obstacles in O(n (log n)

Symposium on Computational Geometry 1987 
(0)

1987 

Conference paper
Kenneth L. Clarkson.
Approximation Algorithms for Shortest Path Motion Planning (Extended Abstract)

Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987, New York, New York, USA 1987 
(0)

1987 

Conference paper
Kenneth L. Clarkson.
New Applications of random Sampling in Computational Geometry.

Discrete Computational Geometry 1987, Volume 2 
(0)

1987 

Conference paper
Leonidas J. Guibas, Jorge Stolfi, Kenneth L. Clarkson.
Solving Related Twoand ThreeDimensional Linear Programming Problems in Logarithmic Time.

Theor. Comput. Sci. 1987, Volume 49 
(0)

1987 

Conference paper
Kenneth L. Clarkson.
Further Applications of Random Sampling to Computational Geometry

Proceedings of the 18th Annual ACM Symposium on Theory of Computing, May 2830, 1986, Berkeley, California, USA 1986 
(0)

1986 

Conference paper
Kenneth L. Clarkson.
Linear Programming in O(n * (3_d)_2) Time.

Inf. Process. Lett. 1986, Volume 22 
(0)

1986 

Conference paper
Kenneth L. Clarkson.
A Probabilistic Algorithm for the Post Office Problem

Proceedings of the 17th Annual ACM Symposium on Theory of Computing, May 68, 1985, Providence, Rhode Island, USA 1985 
(0)

1985 

Conference paper
Kenneth L. Clarkson.
Fast ExpectedTime and Approximation Algorithms for Geometric Minimum Spanning Trees (Extended Abstract)

Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30  May 2, 1984, Washington, DC, USA 1984 
(0)

1984 

Conference paper
Kenneth L. Clarkson.
Fast Algorithms for the All Nearest Neighbors Problem

24th Annual Symposium on Foundations of Computer Science, Tucson, Arizona, USA, 79 November 1983 1983 
(0)

1983 

Conference paper
Kenneth L. Clarkson.
A Modification of the Greedy Algorithm for Vertex Cover.

Inf. Process. Lett. 1983, Volume 16 
(0)

1983 