Jie Gao

1415 Computer Science Building

Stony Brook University

Stony Brook, NY 11794
Phone: 631-6329169

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 since 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, Networking, Computational geometry

  • Geometric algorithms for wireless sensor networks: location based algorithms for a number of important network architectural components including network localization, geometric routing, spatial gossip, data aggregation, and data-centric routing.

  • Topological methods in wireless sensor networks: the study of the morphology of a large sensor field, including the discovery and representation of non-trivial topological features (e.g., holes) of such a field, and applications in fundamental network operations; and the study of the structure of signal landscapes sampled by a field of distributed sensors, including the distributed processing (e.g., the topology extraction) and compact representation of the topological features embedded in the raw sensor readings, and applications in real-time monitoring, situation understanding and response.

  • Social networks and applications in peer-to-peer systems: the study of the social aspect in P2P systems for file sharing through the Internet and P2P interactions between mobile wireless phones. The focus is to analyze through online social communities and mobility/contact patterns the level of homophily (that friends often have similar interests or behaviors) in a social community for improving system performance and enabling innovative tools/applications that best serve people's communication needs.

    For more information, here is a short research statement.

    Students:

      My office hour for Fall 2008 is Tuesday 4-6pm. 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:

    Fall 2008 CSE548 (cross-listed as AMS542) Analysis of Algorithms
    Fall 2008 CSE642 Algorithm 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, 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, Proc. of the 27th Annual IEEE Conference on Computer Communications (INFOCOM'08), 960-967, May, 2008. Bibtex. Slides. Also presented in the 17th Fall Workshop on Computational and Combinatorial Geometry, Nov, 9-10, 2007.

    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, Proc. of the 27th Annual IEEE Conference on Computer Communications (INFOCOM'08), 1175-1183, May, 2008. Bibtex. Slides. Also presented in the 17th Fall Workshop on Computational and Combinatorial Geometry, Nov, 9-10, 2007.

    4. Anand Prabhu Subramanian, Pralhad Deshpande, Jie Gao, Samir R. Das, Drive-by Localization of Roadside WiFi Networks , 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, Proc. of the 27th Annual IEEE Conference on Computer Communications (INFOCOM'08), 789-797, May, 2008. Bibtex. Slides. Journal version accepted and to appear in ACM Transactions on Sensor Networks, 2008.

    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 to appear in ACM Transactions on Sensor Networks, 5(1), February, 2009. 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. Journal version accepted to Discrete and Computational Geometry, 2008.

    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: 8/25/2008

    •