Mihai Badoiu

I have graduated! I was a member of the theory of computation group, in the algorithms subgroup. I have been working mainly on high-dimensional computational geometry under the supervision of my advisor, Piotr Indyk. Some of my ''theory'' interests include combinatorial optimizations, and approximation algorithms. My PhD thesis was on Algorithmic Embeddings. My masters thesis was on Clustering in High Dimensions.

In the past I've taught 6.856J/18.416J - Randomized Algorithms, and 6.046 - Introduction to Algorithms

Before grad school, I double-majored in Computer Science and Mathematics. Before coming to MIT, I have graduated from Informatics High School, in Bucharest, Romania.

Papers:

• "Approximate Clustering via Core-Sets" (with Sariel Har-Peled and Piotr Indyk), in the Proceedings of the 34th Symposium on Theory of Computing (STOC 02).
• "Approximation Algorithm for Embedding Metrics into a Two-dimensional Space" ,in the Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'03)
• "Smaller Core-Sets for Balls" (with Ken Clarkson), in the Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'03)
• "Fast Approximation Algorithms for the Hyperplane Fitting Problem" (with Piotr Indyk), manuscript
• "Optimal Core-Sets for Balls" (with Ken Clarkson), manuscript
• "Clustering in High Dimensions" (Masters Thesis)
• "A Simplified and Dynamic Unified Structure" (with Erik Demaine), In Proc. of LATIN '04 (also invited to TCS journal)
• "Fast Approximation Pattern Matching with Few Indels via Embeddings" (with Piotr Indyk), In Proc. of the ACM-SIAM Symposium on Discrete Algorithms (SODA '05).
• "Embedding with Extra Information" (with Erik Demaine, MohammadTaghi Hajiaghayi, and Piotr Indyk), In Proc. of the ACM-SIAM Symposium on Computational Geometry (SoCG '04).
• "Ordinal Embeddings of Minimum Relaxation: General Properties, Trees, and Ultrametrics" (with Noga Alon, Erik Demaine, Martin Farach-Colton, MohammadTaghi Hajiaghayi, and Anastasios Sidiropoulos), In Proc. of the ACM-SIAM Symposium on Discrete Algorithms (SODA '05).
• "Approximation Algorithms for Low-Distortion Embeddings Into Low-Dimensional Spaces"
  (with Kedar Dhamdhere, Anupam Gupta, Yuri Rabinovich, Harald Raecke, R. Ravi, and Anastasios Sidiropoulos) In Proc. of the ACM-SIAM Symposium on Discrete Algorithms (SODA '05).
• "Low-Distortion Embeddings of General Metrics Into the Line"
  (with Julia Chuzhoy, Piotr Indyk, and Anastasios Sidiropoulos) in the Proceedings of the 37th Symposium on Theory of Computing (STOC 05).
• "Embedding Ultrametrics Into Low-Dimensional Spaces"
  (with Julia Chuzhoy, Piotr Indyk, and Anastasios Sidiropoulos) in the Proceedings of the ACM-SIAM Symposium on Computational Geometry (SoCG '06).
• "Approximation Algorithms for Embedding General Metrics Into Trees"
  (with Piotr Indyk, and Anastasios Sidiropoulos) In Proc. of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA 2007).
• "Ordinal Embedding: Approximation Algorithms and Dimensionality Reduction"
  (with Erik Demaine, MohammadTaghi Hajiaghayi, Anastasios Sidiropoulos, and Morteza Zadimoghaddam) In RANDOM'08.