Home Bookmarks Papers Blog


The following is a collection of results/observations/etc and from some reason they were written down. There are no plans to publish those results anywhere. If you refer to them, pleaee refer to this webpage (or even better - the arxiv version if it is available).
  1. Some Geometric Applications of Anti-Chains, with M. Jones
  2. A simple algorithm for computing a cycle separator, with A. Nayyeri.
  3. Approximately: Independence Implies Vertex Cover.
  4. Two (known) results about graphs with no short odd cycles, with R. Saladi.
  5. A Proof of Dudley's Convex Approximation, with M. Jones.
  6. LSH on the Hypercube Revisited, with S. Mahabadi.
  7. Cheat Sheet: Chernoff Type Inequalities [full treatment].
  8. A Simple Algorithm for Maximum Margin Classification, Revisited.
  9. Computing the $k$ nearest neighbors for all vertices via Dijkstra.
  10. $\varepsilon$-Nets for Halfspaces Revisited, with Haim Kaplan, Micha Sharir, and Shakhar Smorodinsky.
  11. A More Intuitive Proof of Chernoff's Inequality?
  12. Fast Clustering with Lower Bounds: No Customer too Far, No Shop too Small, with with A. Ene and B. Raichel.
  13. A Simple Proof of the Existence of a Planar Separator.
  14. Being Fat and Friendly is Not Enough.
  15. Approximating Spanning Trees with Low Crossing Number.
  16. Randomized Incremental Construction of Compressed Quadtrees (5-July-09).
  17. A Note of Fractional Independent Segments.
  18. Carnival of Samplings: Nets, Approximations, Relative and Sensitive.
  19. Covering by translated intervals is NP-Hard, with Chandra Chekuri.
  20. Low Rank Matrix Approximation in Linear Time.
  21. A Comment on Pseudo-Triangulation in Three Dimensions.
  22. On the Expected Complexity of Random Convex Hulls.
  23. On the height of arrangmeent.
  24. Two randomized incramental algorithms for planar arrangements, with a twist, with P. K. Agarwal.

Last modified: Wed Sep 30 15:49:32 CDT 2015