Jie Gao

1415 Computer Science Building

Stony Brook University

Stony Brook, NY 11794

Phone: (631) 632-9169

jgao at cs dot sunysb dot edu

 

 

Short Bio:

I am an assistant professor at Department of Computer Science, State University of New York, Stony Brook starting from Fall 2005. I obtained my Ph.D degree from Department of Computer Science, Stanford University in 2004 and my B.S. degree from the Special Class for the Gifted Young at University of Science and Technology of China in 1999. I spent the academic year 2004-2005 at Center for the Mathematics of Information, California Institute of Technology. I received NSF CAREER award in 2006.

Research Interests:

Algorithms, Ad hoc communication and sensor networks, Computational geometry

Sensor networks have a unique geometric character as sensor nodes are embedded in, and designed to monitor, the physical environment. Thus the physical locations of sensor nodes have a fundamental influence of the system design in all aspects from low-level networking and organization to high-level information processing and applications. In my recent work I take a geometric approach to study algorithms in sensor networks, for a number of important architecture components including network topology discovery, network localization, geometric routing, information brokerage and retrieval. For all these problems geometric ideas play an important role.

For more information, here is a short research statement.

Students:

  My office hour for Spring 2008 is Tuesday, Thursday 11:20-12:30pm. If you want to work with me on an independent study project, or you have an interesting problem to discuss, or simply chat a bit, please drop by my office. If you need a substantial chunk of my time, email me for an appointment.

If you have questions about graduate student admission, proficiency in algorithms, please read this.

Teaching:

Spring 2008 CSE548 (cross-listed as AMS542) Analysis of Algorithms
Spring 2008 CSE642 Algorithm Seminar
Spring 2008 CSE658 Wireless Networking Seminar

Past teaching

Professional Activities:

Program Committee:

Publications: By topic | By date

Ad hoc communication and sensor networks

  1. Huijia Lin, Maohua Lu, Nikola Milosavljevic, Jie Gao, Leonidas J. Guibas, Composable Information Gradients in Wireless Sensor Networks, to appear in Proc. of the International Conference on Information Processing in Sensor Networks (IPSN'08), 121-132, April, 2008. Bibtex.

  2. Xianjin Zhu, Rik Sarkar, Jie Gao, Joseph S. B. Mitchell, Light-weight Contour Tracking in Wireless Sensor Networks, to appear in Proc. of the 27th Annual IEEE Conference on Computer Communications (INFOCOM'08), 960-967, May, 2008. Bibtex.

  3. Rik Sarkar, Xianjin Zhu, Jie Gao, Leonidas J. Guibas, Joseph S. B. Mitchell, Iso-Contour Queries and Gradient Descent with Guaranteed Delivery in Sensor Networks, to appear in Proc. of the 27th Annual IEEE Conference on Computer Communications (INFOCOM'08), 1175-1183, May, 2008. Bibtex.

  4. Anand Prabhu Subramanian, Pralhad Deshpande, Jie Gao, Samir R. Das, Drive-by Localization of Roadside WiFi Networks , to appear in Proc. of the 27th Annual IEEE Conference on Computer Communications (INFOCOM'08), 718-725, May, 2008. Bibtex.

  5. Sol Lederer, Yue Wang, Jie Gao, Connectivity-based Localization of Large Scale Sensor Networks with Complex Shape, to appear in Proc. of the 27th Annual IEEE Conference on Computer Communications (INFOCOM'08), 789-797, May, 2008. Bibtex.

  6. Jie Gao, Leonidas J. Guibas, John Hershberger, Nikola Milosavljevic, Sparse Data Aggregation in Sensor Networks, Proc. of the International Conference on Information Processing in Sensor Networks (IPSN'07), 430-439, April, 2007. Bibtex.

  7. Rik Sarkar, Xianjin Zhu, Jie Gao, Hierarchical Spatial Gossip for Multi-Resolution Representations in Sensor Networks, Proc. of the International Conference on Information Processing in Sensor Networks (IPSN'07), 420-429, April, 2007. Bibtex, Slides.

  8. Xianjin Zhu, Rik Sarkar, Jie Gao, Shape Segmentation and Applications in Sensor Networks, Proc. of the 26th Annual IEEE Conference on Computer Communications (INFOCOM'07), 1838-1846, May, 2007. Bibtex. Slides. Also presented in the 16th Fall Workshop on Computational and Combinatorial Geometry, Nov, 10-11, 2006. Journal version under the title Segmenting a Sensor Field: Algorithms and Applications in Network Design accepted to ACM Transactions on Sensor Networks, 2008.

  9. Ritesh Maheshwari, Jie Gao, Samir R. Das, Detecting Wormhole Attacks in Wireless Networks Using Connectivity Information, Proc. of the 26th Annual IEEE Conference on Computer Communications (INFOCOM'07), 107-115, May, 2007. Bibtex. Poster presented at IEEE SECON 2006, Sep, 2006.

  10. An Nguyen, Nikola Milosavljevic, Qing Fang, Jie Gao, Leonidas J. Guibas, Landmark Selection and Greedy Landmark-descent Routing for Sensor Networks, Proc. of the 26th Annual IEEE Conference on Computer Communications (INFOCOM'07), 661-669, May, 2007. Bibtex.

  11. Rik Sarkar, Xianjin Zhu, Jie Gao, Double Rulings for Information Brokerage in Sensor Networks, The 12th Annual International Conference on Mobile Computing and Networking (MobiCom'06), 286-297, September, 2006. Bibtex. Slides.

  12. Yue Wang, Jie Gao, Joseph S.B. Mitchell, Boundary Recognition in Sensor Networks by Topological Methods, The 12th Annual International Conference on Mobile Computing and Networking (MobiCom'06), 122-133, September, 2006. Bibtex, Slides.

  13. Amitabh Basu, Jie Gao, Joseph S.B. Mitchell, Girishkumar Sabhnani, Distributed Localization by Noisy Distance and Angle Information, Proc. of the Seventh ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc'06), 262-273, May, 2006. Bibtex.

  14. Qing Fang, Jie Gao, Leonidas J. Guibas, Landmark-Based Information Storage and Retrieval in Sensor Networks, The 25th Conference of the IEEE Communication Society (INFOCOM'06), April, 2006. Bibtex. 

  15. Jehoshua Bruck, Jie Gao, Anxiao Jiang, MAP: Medial Axis Based Geometric Routing in Sensor Networks, Proc. of the 11th Annual International Conference on Mobile Computing and Networking (MobiCom’05), 88-102, August, 2005. Journal version invited to Wireless Networks (WINET) special issue from MobiCom'05. Slides. Bibtex.

  16. Jehoshua Bruck, Jie Gao, Anxiao Jiang, Localization and Routing in Sensor Networks by Local Angle Information, Proc. of the Sixth ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc'05), 181-192, May, 2005. Journal version accepted to ACM Transactions on Sensor Networks, 2008. Slides. Bibtex.

  17. Jie Gao, Leonidas J. Guibas, An Nguyen, Distributed Proximity Maintenance in Ad Hoc Mobile Networks, Proc. of the IEEE International Conference on Distributed Computing in Sensor Systems (DCOSS'05), 4-19, June, 2005. Here is the full version. Slides. Bibtex.

  18. Qing Fang, Jie Gao, Leonidas J. Guibas, Vin de Silva, Li Zhang, GLIDER: Gradient Landmark-Based Distributed Routing for Sensor Networks, Proc. of the 24th Conference of the IEEE Communication Society (INFOCOM'05), volume 1, pages 339-350, March, 2005. Slides. Bibtex.

  19. Jie Gao, Li Zhang, Tradeoffs between Stretch Factor and Load Balancing Ratio in Routing on Growth Restricted Graphs, Proc. of the 23rd ACM Symposium on Principles of Distributed Computing (PODC'04), 189-196, July, 2004. Journal version accepted to IEEE Transactions on Parallel and Distributed Systems, 2008. Slides. Bibtex.

  20. Jie Gao, Leonidas J. Guibas, John Hershberger, Li Zhang, Fractionally Cascaded Information in a Sensor Network, Proc. of the 3rd International Symposium on Information Processing in Sensor Networks (IPSN'04), 311-319, April, 2004. Bibtex.

  21. Jie Gao, Li Zhang, Load Balanced Short Path Routing in Wireless Networks, The 23rd Conference of the IEEE Communications Society (INFOCOM), vol. 23, no. 1, 1099-1108, March, 2004. Journal version in IEEE Transactions on Parallel and Distributed Systems, Special Issue on Localized Communication, vol. 17, no. 4, 377-388, April, 2006. Slides. Bibtex.

  22. Qing Fang, Jie Gao, Leonidas J. Guibas, Locating and Bypassing Routing Holes in Sensor Networks, The 23rd Conference of the IEEE Communications Society (INFOCOM), vol. 23, no. 1, 2458-2468, March 2004. Journal version in MONET Special Issue on Foundations of Mobile Computing, 11, 187-200, 2006. Bibtex.

  23. Jie Gao, Leonidas J. Guibas, John Hershberger, Li Zhang, An Zhu, Geometric Spanner for Routing in Mobile Networks, Proc. of the 2nd ACM Symposium on Mobile Ad Hoc Networking & Computing (MobiHoc'01), 45-55, October 2001. Journal version in IEEE Journal on Selected Areas in Communications Wireless Ad Hoc Networks (J-SAC), 23(1), 174-185, January, 2005. Bibtex.

Computational Geometry, Data Structures, Algorithms

  1. Jie Gao, Leonidas J. Guibas, Steve Y. Oudot, Yue Wang, Geodesic Delaunay Triangulation and Witness Complex in the Plane, Proc. of ACM-SIAM Symposium on Discrete Algorithms (SODA'08), 571-580, January, 2008. Bibtex.

  2. Jehoshua Bruck, Jie Gao, Anxiao Jiang, Weighted Bloom Filter, 2006 IEEE International Symposium on Information Theory (ISIT'06), July, 2006. Bibtex.

  3. Jie Gao, Michael Langberg, Leonard Schulman, Analysis of Incomplete Data and an Intrinsic-Dimension Helly Theorem, Proc. of ACM-SIAM Symposium on Discrete Algorithms (SODA'06), 464-473, January, 2006. Slides. Bibtex.

  4. Pankaj K. Agarwal, Mark de Berg, Jie Gao, Leonidas J. Guibas, Sariel Har-Peled, Staying in the Middle: Exact and Approximate Medians in R1 and R2 for Moving Points, Proc. of the 17th Canadian Conference on Computational Geometry (CCCG'05), 42-45, August, 2005. Here is the full version. Slides. Bibtex.

  5. Jie Gao, Leonidas J. Guibas, An Nguyen, Deformable Spanners and Applications, Proc. of the 20th ACM Symposium on Computational Geometry (SoCG'04), 190-199, June, 2004. Journal version invited to Computational Geometry : Theory and Applications, 35, 2-19, 2006. Slides. Bibtex.

  6. Jie Gao, Li Zhang, Well-Separated Pair Decomposition for the Unit-Disk Graph Metric and its Applications, Proc. the 35th ACM Symposium on Theory of Computing (STOC'03), 483-492, June, 2003. Journal version appeared in SIAM J. Computing, 35(1), 151-169, 2005. Slides. Bibtex.

  7. Pankaj K. Agarwal, Jie Gao, Leonidas J. Guibas, Kinetic Medians and kd-trees, Proc. of the 10th Annual European Symposium on Algorithms (ESA'02), Lecture Notes in Computer Science 2461, 5-16, September 2002. Bibtex.

  8. Jie Gao, Leonidas J. Guibas, John Hershberger, Li Zhang, An Zhu, Discrete Mobile Centers, Proc. of the 17th ACM Symposium on Computational Geometry (SoCG'01), 188-196, June 2001. Journal version invited to Discrete and Computational Geometry, 30(1), 45-65, 2003. Bibtex.

Thesis

  1. Jie Gao, Hierarchical Data Structures for Mobile Networks, Ph.D dissertation, Stanford University, August 2004. Bibtex.

Disclaimer: The materials published on this site are for non-commercial use such as research and teaching. They are under various copyright. Please refer to ACM copyright policy for an example.

Last updated: 1/31/2007