Research  Papers

I did my Ph.D. thesis research in algorithms (sublinear algorithms, computational geometry) under the supervision of Professor Bernard Chazelle. Here is a list of my papers.

• "Lower Bounds for Intersection Searching and Fractional Cascading in Higher Dimension", (with Bernard Chazelle), Proc. of the 33rd Annual ACM Symp. on Theory of Computing (STOC 2001), pp. 322-329. (Journal version in Journal of Computer System and Sciences, Volume 68, Issue 2, pp.269-284.)

• "Approximating the Smallest Grammar: Kolmogorov Complexity in Natural Models", (with Moses Charikar, Eric Lehman, Rina Panigrahy, Manoj Prabhakaran, April Rasala, Amit Sahai, abhi shelat), Proc. of the 34th Annual ACM Symp. on Theory of Computing (STOC 2002), pp. 792-801. (Journal version in IEEE Transactions on Information Theory, Volume 51, Issue 7, pp.2554-2576, July 2005.)

• "On Randomized Broadcasting and Gossiping in Radio Networks", (with Manoj Prabhakaran), Proc. of the 8th Annual International Computing and Combinatorics Conference (COCOON 2002), pp. 340-349. (Also in LNCS 2387, Springer-Verlag, 2002.)

• "Sublinear Geometric Algorithms", (with Bernard Chazelle, Avner Magen), Proc. of the 35th Annual ACM Symp. on Theory of Computing (STOC 2003), pp. 531-540. (Journal version in SIAM Journal on Computing, Volume 35, Issue 3, pp. 627-646.)

• " A Note on Point Location in Arrangements of Hyperplanes", Information Processing Letters, 90 (2004), pp. 93-95.

• "Approximate Range Searching in Higher Dimension", (with Bernard Chazelle, Avner Magen), Proc. of the 16th Canadian Conference on Computational Geometry (CCCG 2004), pp. 154-157. (Journal version in Computational Geometry: Theory and Applications, Volume 39, Issue 1, pp. 24-29.)

• "Estimating the Distance to a Monotone Function", (with Nir Ailon, Bernard Chazelle, Seshadhri Comandur), Proc. of the 8th International Workshop on Randomization and Computation (RANDOM 2004), pp. 229-236. (Journal version in Random Structures & Algorithms, Volume 31, Issue 3, pp. 371-383.)

• " A Strong Lower Bound for Approximate Nearest Neighbor Searching in the Cell Probe Model", Information Processing Letters, 92 (2004), pp. 23-29.

• "Property-Preserving Data Reconstruction", (with Nir Ailon, Bernard Chazelle, Seshadhri Comandur), Proc. of the 15th International Symposium on Algorithms and Computation (ISAAC 2004), pp. 16-27. (Journal version in Algorithmica, Volume 51, Number 2, pp. 160-182.)

• "Self-Improving Algorithms", (with Nir Ailon, Bernard Chazelle, Seshadhri Comandur), Proc. of the 17th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA 2006), pp. 261-270.

This paper was written for my senior project at college:

• "An Effective FP Algorithm with Fuzzy Criterion in Feedforward Neural Networks and Its Application in Noisy Pattern Classification", (with Yannan Zhao, Fajie Sun), Proceedings of The 2000 International Conference on Artificial Intelligence (IC'AI 2000), Las Vegas, NV, June 2000, pp. 909-914.