Lisa Zhang

   600 Mountain Avenue, 2A-442 
   Murray Hill, NJ 07974 

   Tel.: +1 (908) 582-5281 
   Fax: +1 (908) 582-6228
   E-mail: ylz@research.bell-labs.com

Current and Past Affiliations

  • Computing Sciences Principals Research at Bell Laboratories, Alcatel-Lucent, 1997-Present.
  • Massachusetts Institute of Technology.  PhD in Applied Mathematics, 1993-1997.

    •     Advisor: Professor Tom Leighton.
        Thesis: An Analysis of Network Routing and Communication Latency. ps.gz
     
  • Wellesley College. summa cum laude, BA in Mathematics and Computer Science, 1989-1993.

    • Short bio

                I was born and brought up in Shanghai, China. I spent eight years of my childhood in Jing'an District Primary School and Kindergarten, and six years of my adolescence in Yucai High School. I arrived in America in the summer of 1989 and spent the next eight years in the Boston area, first studying at Wellesley College then at MIT. In 1997, after my Ph.D, I landed a research position at Bell Labs in Murray Hill, NJ, and it remains the only job I have had. At the time Bell Labs was the research arm of Lucent Technologies. It was spun off from AT&T in 1996 and merged with Alcatel in 2006.
                My research broadly concerns algorithmic and complexity issues of networking, which includes network planning and optimization, routing and scheduling protocols, and stability and Quality-of-Service analysis. My work is interdisciplinary, covering topics in theoretical computer science, applied mathematics, operations research and electrical engineering. More details of my work can be found in my curriculum vitae.

    Papers



    2009

  • Multiserver Scheduling with Contiguity Constraints. IEEE INFOCOM 2009. Coauthored with M. Andrews.

  • Approximation Algorithms for Grooming in Optical Network Design. IEEE INFOCOM 2009. Coauthored with S. Antonakopoulos.

  • Complexity of Wavelength Assignment in Optical Network Optimization. IEEE/ACM Transactions on Networks, 17(2):646-657, 2009. Coauthored with M. Andrews

  • A Note on Generalized Rank Aggregation. Information Processing Letters, 109(13):647-651, 2009. Coauthored with H. Shachnai and T. Matsui.


    • 2008

  • Efficient Scheduling Algorithms for Real-Time Multicast Services in Wireless LANs. IEEE INFOCOM Mini Symposium 2008. Coauthored with Y. Bejerano, D. Lee and P. Sinha.

  • Satisfying Arbitrary Delay Requirements in Multihop Networks. IEEE INFOCOM 2008. Coauthored with M. Andrews.

  • Creating Templates to Achieve Low Delay in Multi-Carrier Frame-Based Wireless Data Systems. IEEE INFOCOM 2008. Coauthored with M. Andrews.

  • The Effect of Bridge-and-Roll on Minimizing Wavelength Conversion for Dynamic Traffic. ECOC 2008. Coauthored with S. Fortune.

  • Wavelength Assignment in Optical Network Design. Mathematics-in-Industry Case Studies Journal, 1:49-65, 2008. Coauthored with B. Farrell, Y. Huang, M. Iwen, T. Wang and J. Zheng.

  • Path Decomposition under a New Cost Metric with Applications to Optical Network Design. ACM Transactions on Algorithms. 4(1):Article 15, 2008. Coauthored with E. Anshelevich.

  • Designing Multihop Wireless Backhaul Networks with Delay Guarantees. Springer Wireless Networks, published online, August 2008. Coauthored with G. Narlikar and G. Wilfong.

  • Almost-Tight Hardness of Directed Congestion Minimization. Journal of the ACM, 55(6): article 27, 2008. Coauthored with M. Andrews.

  • Exact Algorithms for the Master Ring Problem. Networks, 52(2):98-107, 2008. Coauthored with H. Shachnai and T. Matsui.


    • 2007

  • Buy-at-Bulk Network Design with Protection. IEEE FOCS 2007. Coauthored with S. Antonakopoulos, C. Chekuri and B. Shepherd. pdf.

  • Scheduling Algorithms for Multi-Carrier Wireless Data Systems. ACM Mobicom 2007. Coauthored with M. Andrews. pdf.

  • Heuristics for Fiber Installation in Optical Network Optimization. IEEE GLOBECOM 2007. Coauthored with S. Antonakopoulos.

  • Scheduling Algorithms for Single-Carrier and Multi-Carrier Wireless Data Systems. Allerton 2007, invited paper. Coauthored with M. Andrews.

  • A Note on Generalized Rank Aggregation. International Network Optimization Conference (INOC) 2007. Coauthored with H. Shachnai and T. Matsui.

  • Hardness of the Undirected Congestion Minimization Problem. SIAM Journal of Computing 37(1):112-131, 2007. Coauthored with M. Andrews.

  • Routing and Scheduling in Multihop Wireless Networks with Time-Varying Channels. ACM Transactions on Algorithms 3(3):Article 33, 2007. Coauthored with M. Andrews.


    • 2006

  • Logarithmic Hardness for the Directed Congestion Minimization Problem. ACM STOC, 2006. Coauthored with M. Andrews. pdf.

  • Admission Control for Multihop Wireless Backhaul Networks with QoS Support . IEEE Wireless Communications and Networking Conference, 2006. Coauthored with S. Lee, G. Narlikar, M. Pal and G. Wilfong.

  • Designing Multihop Wireless Backhaul Networks with Delay Guarantees . IEEE INFOCOM 2006. Coauthored with G. Narlikar and G. Wilfong. pdf.

  • Complexity of Wavelength Assignment in Optical Network Optimization. IEEE INFOCOM 2006. Coauthored with M. Andrews. pdf.

  • Minimizing Maximum Fiber Requirement in Optical Networks. Journal of Computer and Systems Sciences 72:118-131, 2006. Coauthored with M. Andrews. pdf.

  • Scheduling Over Non-Stationary Wireless Channels with Finite Rate Sets . IEEE/ACM TON 14(5):1067-1077, 2006. Coauthored with M. Andrews. pdf.

  • Logarithmic Hardness of the Undirected Edge-Disjoint Paths Problem. . JACM 53(5):745-761, 2006. Coauthored with M. Andrews.

  • Design Tools for Transparent Optical Networks . Bell Labs Technical Journal 11(2):129-143, 2006. Coauthored with C. Chekuri, P. Claisse, R. Essiambre, S. Fortune, D. Kilper, W. Lee, K. Nithi, I. Saniee, B. Shepherd, C. White and G. Wilfong. doc.

  • A Tool for CDMA Data Measurement and Analysis. The Second International Workshop On Wireless Network Measurement, 2006. Coauthored with M. Andrews.

    • 2005

  • Scheduling over a Time-Varying User-Dependent Channel with Applications to High Speed Wireless Data. Journal of the ACM 52(5): 809-834, 2005. Coauthored with M. Andrews. pdf.

  • Source Routing and Scheduling in Packet Networks. Journal of ACM 52(4): 582-601, 2005. Coauthored with M. Andrews, A. Fernandez and A. Goel. pdf.

  • Hardness of the Undirected Edge Disjoint Path Problem with Congestion. IEEE FOCS, 2005. Coauthored with M. Andrews, J. Chuzhoy and S. Khanna.

  • The Master Ring Problem. International Conference on Analysis of Algorithms, 2005. Coauthored with H. Shachnai. pdf.

  • Hardness of the Undirected Congestion Minimization Problem. ACM STOC, 2005. Coauthored with M. Andrews. pdf.

  • Hardness of the Undirected Edge Disjoint Paths Problem. ACM STOC, 2005. Coauthored with M. Andrews. pdf.

  • Bounds on Fiber Minimization in Optical Networks. IEEE INFOCOM 2005. Coauthored with M. Andrews. ps.

  • The New Paradigm for Wireless Network Optimization: A Synergy of Automated Processes and Human Intervention. . IEEE Communications Magazine 43(3), 2005. Coauthored with G. Hampel, D. Abush-Magder, A. Diaz, L. Drabeck, M. Flanagan, J. Graybeal, J. Hobby, M. MacDonald, P. Polakos, J. Srinivasan, H. Trickey and G. Rittenhouse.

    • 2004

  • Path Decomposition under a New Cost Measure. European Symposium on Algorithms (ESA). Bergen, Finland, September 2004. Coauthored with E. Anshelevich.

  • The Effects of Temporary Sessions on Network Performance. SIAM Journal on Computing 33(3): 659-673, 2004. Coauthored with M. Andrews.

  • Scheduling Protocols for Switches with Large Envelopes. Journal of Scheduling 7(3): 171-186, 2004. Coauthored with M. Andrews.

  • Minimizing End-to-End Delay in High-Speed Networks with a Simple Coordinated Schedule. Journal of Algorithms 52(1): 57-81, 2004. Coauthored with M. Andrews.

  • Wavelength Assignment in Optical Networks with Fixed Fiber Capacity. International Colloquium on Automata, Languages and Programming (ICALP). Turku, Finland, July 2004. Coauthored with M. Andrews.

  • Line System Design for DWDM Networks. International Telecommunications Network Strategy and Planning Symposium (Networks). Vienna, Austria, June 2004. Coauthored with S. Fortune and W. Sweldens.

  • DCM Selection on an Optical Line System. International Telecommunications Network Strategy and Planning Symposium (Networks). Vienna, Austria, June 2004. Coauthored with C. Chekuri and W. Lee.

  • Scheduling over Non-stationary Wireless Channels. IEEE INFOCOM 2004. Coauthored with M. Andrews.

  • Routing and Scheduling in Multihop Wireless Networks with Time-Varying Channels. ACM-SIAM Symposium on Discrete Algorithms (SODA) 2004. Coauthored with M. Andrews.

    • 2003

  • Optical Line System Configuration via Dynamic Programming. International Network Optimization Conference (INOC), 2003. Coauthored with C. Chekuri and W. Lee.

  • Achieving Stability in Networks of Input-Queued Switches. IEEE/ACM TON, 11(5):848 -- 857, 2003. Coauthored with M. Andrews.

  • Wavelength Assignment and Generalized Interval Graph Coloring. ACM-SIAM SODA, 2003. Coauthored with P. Winkler.

    • 2002

  • Fast Fair and Frugal Bandwidth Allocation in ATM Networks, Algorithmica special issue Internet Algorithms 33:272 -- 286, 2002. Coauthored with Y. Bartal, M. Farach-Colton and S. Yooseph.

  • New Algorithms for Disk Scheduling, Algorithmica 32:277-301 2002. Coauthored with M. Andrews and M. Bender.

  • Approximation Algorithms for Access Network Design, Algorithmica 34: 197 -- 215, 2002. Coauthored with M. Andrews.

  • Scheduling over a Time-Varying User-Dependent Channel with Applications to High Speed Wireless Data, IEEE FOCS, 2002. Coauthored with M. Andrews.

  • The Performance of GPS and EDF with Temporary Sessions, IEEE International Workshop on Quality of Service, 2002. Coauthored with M. Andrews.

  • Scheduling Protocols for Switches with Large Envelopes, ACM-SIAM SODA, 2002. Coauthored with M. Andrews.

  • An Improved FPTAS for Restricted Shortest Path, Information Processing Letters, September 2002. Coauthored with F. Ergun and R. Sinha.

    • 2001

  • An Augmentation Algorithm for Mincost Multicommodity Flow on a Ring, Discrete Applied Mathematics 110:301 -- 315, 2001. Coauthored with B. Shepherd.

  • Source Routing and Scheduling in Packet Networks, IEEE Symposium on Foundation of Computer Science (FOCS), 2002. Coauthored with M. Andrews, A. Fernandez and A. Goel.

  • Achieving Stability in Networks of Input-Queued Switches, IEEE INFOCOM 01. Coauthored with M. Andrews.

  • General Dynamic Routing with Per-Packet Delay Guarantees, SIAM Journal on Computing 30(5): 1594 -- 1623, 2002. Coauthored with M. Andrews, A. Fernandez, M. Harchol-Balter and T. Leighton.

    • 2000

  • Blocking Estimates in a Partitioned-Sector TDMA System, Dial M for Mobility 2000: The 4th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, pp. 28 -- 34, Boston MA, August 2000. Coauthored with C. Chekuri, K. Ramanan and P. Whiting.

  • QoS Routing with Performance-Dependent Costs, IEEE INFOCOM 2000. Coauthored with F. Ergun and R. Sinha.

  • The Effects of Temporary Sessions on Network Performance, ACM-SIAM Symposium on Discrete Algorithms (SODA) 2000. Coauthored with M. Andrews.

    • 1999

  • Improved Bounds for On-Line Load Balancing, Algorithmica 23(4):278-301 1999. Coauthored with M. Andrews and M. X. Goemans.

  • Automatic Methods for Hiding Latency for Parallel and Distributed Computing, SIAM Journal on Computing 29(2):615-647 1999, pp. 615 -- 647. Coauthored with M. Andrews, T. Leighton and P. T. Metaxas.

  • An Augmentation Algorithm for Mincost Multicommodity Flow on a Ring, IEEE GLOBECOM 1999. Coauthored with B. Shepherd.

  • Packet Routing with Arbitrary End-to-End Delay Requirements, ACM Symposium on Theory of Computation (STOC), 1999. Coauthored with M. Andrews.

  • Minimizing End-to-End Delay in High-Speed Networks with a Simple Coordinated Schedule, IEEE INFOCOM 1999. Coauthored with M. Andrews.

  • Fast Fair and Frugal Bandwidth Allocation in ATM Networks, ACM-SIAM Symposium on Discrete Algorithms (SODA), 1999. Coauthored with Y. Bartal, M. Farach-Colton and S. Yooseph.

    • 1998

  • The Access Network Design Problem, IEEE Symposium on Foundation of Computer Science (FOCS), 1998. Coauthored with M. Andrews.

  • Stability Results for Networks with Input and Output Blocking, ACM Symposium on Theory of Computation (STOC), 1998. Coauthored with M. Andrews.

    • 1997

  • Efficient Execution of Nondeterministic Parallel Programs on Asynchronous Systems, Information and Computation 139(1):1--16 25 November 1997. Coauthored with Y. Aumann and M. Bender.

  • General Dynamic Routing with Per-Packet Delay Guarantees, Symposium on Foundations of Computer Science (FOCS), 1997. Coauthored with M. Andrews, A. Fernandez, M. Harchol-Balter and T. Leighton.

  • A Performance Comparison of Competitive On-Line Routing and State-Dependent Routing, IEEE GLOBECOM 1997. Coauthored with W. Aiello, M. Andrews, S. Bhatt and K. R. Krishnan.

    • 1996

  • Improved Bounds for On-Line Load Balancing, International Conference on Computing and Combinatorics, 1996. Coauthored with M. Andrews and M. X. Goemans.

  • New Algorithms for the Disk Scheduling Problem, Symposium on Foundations of Computer Science (FOCS), 1996. Coauthored with M. Andrews and M. Bender.

  • Efficient Execution of Nondeterministic Parallel Programs on Asynchronous Systems, ACM Symposium on Parallel Algorithms and Architectures (SPAA), 1996. Coauthored with Y. Aumann and M. Bender.

  • Open Problems for Latency Hiding in High Bandwidth Networks, Australia Workshop on Combinatorial Algorithms, 1996. Coauthored with M. Andrews, T. Leighton and P. T. Metaxas.

  • Improved Methods for Hiding Latency in High Bandwidth Networks, ACM Symposium on Parallel Algorithms and Architectures (SPAA), 1996. Coauthored M. Andrews, T. Leighton and P. T. Metaxas.

  • Automatic Methods for Hiding Latency in High Bandwidth Networks, ACM Symposium on Theory of Computing (STOC), 1996. Coauthored M. Andrews, T. Leighton and P. T. Metaxas.

    • Sophie concert
    Russian music box
    Hotaka sunset
    Sleigh Ride (Mozart)
    Queen of Sheba