Principal Investigator…

                                               Principal Investigator/Program Director (last, first, middle):          Dr. Gabriel Robins
                                                                 BIOGRAPHICAL SKETCH
                                        Provide the following information for the key personnel in the order listed on Form Page 2.
                                              Follow the sample format for each person. DO NOT EXCEED FOUR PAGES.


 NAME                                                                                    POSITION TITLE

  Robins, Gabriel                                                                        Professor of Computer Science
                                                                                         Department of Computer Science, UVA
EDUCATION/TRAINING (Begin with baccalaureate or other initial professional education, such as nursing, and include postdoctoral training.)
  INSTITUTION AND LOCATION                                                DEGREE                      YEAR(s)                          FIELD OF STUDY

  UCLA, Los Angeles, CA                                                    B.S.                        1983                     Math & Computer Science
  Princeton University, Princeton, NJ                                     M.S.E.                       1985                         Computer Science
  UCLA, Los Angeles, CA                                                   Ph.D.                        1992                         Computer Science
  A. Positions,         Employment and Honors
  1985-1989             Researcher, USC Information Sciences Institute, Marina Del Rey, CA
  1989-1992             Research Associate, UCLA
  1992-1996             Assistant Professor, Department of Computer Science, University of Virginia
  1996-1997             Associate Professor (tenured), Department of Computer Science, University of Virginia
  1997-2002             Walter N. Munster (Endowed Chair) Associate Professor of Computer Science (tenured), UVa
  2002-Present          Professor (tenured), Department of Computer Science, University of Virginia
  Professional Memberships
  1985-Present Association for Computing Machinery (ACM)
  1985-Present Institute of Electrical and Electronics Engineering (IEEE)
  1985-Present ACM Special Interest Group on Design Automation (SIGDA)
  1985-Present ACM Special Interest Group on Automata and Comp. Theory (SIGACT)
  Honors and Awards
  1995-2001 Packard Foundation Fellowship ($550,000) (first one ever awarded in the state of Virginia)
  1994-1999 National Science Foundation Young Investigator Award (NSF NYI) ($312,500)
  1998-2001 Member of the U.S. Army Science Board, U.S. Department of Defense
  1994-1995 Member of the Defense Sc ience Study Group, U.S. Department of Defense
  1996-1997 Member of the Navy Future Study (National Academy of Sciences)
  1997-2002 Walter N. Munster Endowed Chair, University of Virginia
  1999-2002 Member of the Faculty Senate, University of Virginia
  1999-2002 Member of the Faculty Council, School of Engineering, University of Virginia
  2000-2002 Associate Editor, IEEE Transactions on Very Large Scale Integration (VLSI) Systems
  1996-     Expert Witness in several major intellectual property (IP) civil and criminal litigations
  1997-     Member of the Editorial Board, IEEE Book Series
  1996      Two-year early promotion to Associate Professor (with tenure)
  1993      NSF Research Initiation Award, U.S. National Science Foundation
  1994      All-University Outstanding Teaching Award, University of Virginia
  1995      University Teaching Fellowship, University of Virginia
  1998      Faculty Mentor Award, School of Engineering, University of Virginia
  1998      Faculty Appreciation Award, Virginia Engineering Foundation
  2001      Web Team Award, Department of Computer Science, University of Virginia
  1990      Distinguished Paper Award, IEEE International Conference on Computer-Aided Design
  1989      Distinguished Teaching Award, University of California, Los Angeles
  1991      IBM Graduate Fellowship, University of California, Los Angeles & IBM Corp.
  1996      General Chair of the ACM Physical Design Workshop
  1997      Founder of the ACM International Symposium on Physical Design
  Other:    18 invited talks and presentations; 17 newspaper and magazine articles; 1 patent.
            Directed 16 graduate students, 19 undergraduates, and 2 postdocs.
            Refereed for 27 journals, conferences, publishers, and government agencies.

  PHS 398/2590 (Rev. 05/01)                                                Page      1                                            Biographical Sketch Format Page
CONTINUATION PAGE                   Principal Investigator/Program Director    Dr. Gabriel Robins
                                    (Last, first, middle):

B. Selected peer-reviewed publications:
Note: my publication policy is to always order co-author names alphabetically.
1.    Robins, G., The ISI Grapher: a Portable Tool for Displaying Graphs Pictorially, Multicomputer Vision, Levialdi, S.,
      Chapter 12, Academic Press, London, 1988, pp. 185-202.
2.    Kahng, A. B. and Robins, G., On Optimal Interconnections for VLSI, Kluwer Academic Publishers, Boston, MA, 1995,
      304 pages.
3.    Kahng, A. B., Robins, G., and Walkup, E. A., Optimal Algorithms for Substrate Testing in Multi-Chip Modules, in High
      Performance Design Automation for Munti-Chip Modules and Packages, J. -D. Cho and P. D. Franzon, Editors, World
      Scientific Publishing Co., 1996, pp. 181-198.
4.    Foster, L., and Robins, G., Solution to a Number Theory Problem, American Mathematical Monthly, Vol. 89, No. 7,
      Aug-Sep, 1982, pp. 499-500.
5.    Kahng, A. B., and Robins, G., Optimal Algorithms for Extracting Spatial Regularity in Images, Pattern Recognition
      Letters, 12, December 1991, pp. 757-764.
6.    Cong, J., Kahng A. B., Robins, G., Sarrafzadeh, M., and Wong, C. K., Provably-Good Performance-Driven Global
      Routing, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 11, No. 6, June
      1992, pp. 739-752.
7.    Kahng, A. B., and Robins, G., A N      ew Class of Iterative Steiner Tree Heuristics With Good Performance, IEEE
      Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 11, No. 7, July 1992, pp. 893-902.
8.    Hu, T. C., Kahng, A. B., and Robins, G., Solution of the Discrete Plateau Problem, Proceedings of the National
      Academy of Sciences, Vol. 89, October 1992, pp. 9235-9236.
9.    Kahng, A. B., and Robins, G., On Performance Bounds for a Class of Rectilinear Steiner Tree Heuristics in Arbitrary
      Dimension, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 11, No. 11,
      November 1992, pp. 1462-1465.
10.   Cong, J., Kahng A. B., and Robins, G., Matching-Based Methods for High-Performance Clock Routing, IEEE Trans.
      on Computer-Aided Design of Integrated Circuits and Systems, Vol. 12, No. 8, August 1993, pp. 1157-1169.
11.   Hu, T. C., Kahng, A. B., and Robins, G., Optimal Robust Path Planning in General Environments, IEEE Transactions
      on Robotics and Automation, Vol. 9, No. 6, December 1993, pp. 775-784.
12.   Alpert, C., Cong, J., Kahng, A. B., Robins, G., and M. Sarrafzadeh, On the Minimum Density Interconnection Tree
      Problem, VLSI Design: an International Journal of Custom-Chip Design, Simulation, and Testing, Vol. 2, No. 2,
      February 1994, pp. 157-169.
13.   Boese, K., Kahng, A. B., McCoy, B. A., and Robins, G., Near-Optimal Critical Sink Routing Tree Constructions, IEEE
      Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 14, No. 12, December 1995, pp.
      1417-1436.
14.   Griffith, J., Robins, G., Salowe, J. S., and Zhang, T., Closing the Gap: Near-Optimal Steiner Trees in Polynomial
      Time, IEEE Trans. on Comp.-Aided Design of Integrated Circuits and Sys., Vol. 13, No. 11, Nov 1994, pp. 1351-1365.
15.   Robins, G., and Salowe, J. S., Low-Degree Minimum Spanning Trees, Discrete and Computational Geometry, Vol.
      14, September 1995, pp. 151-165.
16.   McCoy, B. A., and Robins, G., Non-Tree Routing, IEEE Transactions on Computer-Aided Design of Integrated
      Circuits and Systems, Vol. 14, No. 6, June 1995, pp. 780-784.
17.   Kahng, A. B., Robins, G., and Walkup, E. A., Optimal Algorithms for Substrate Testing in Multi-Chip Modules,
      International Journal on High-Speed Electronics and Systems, Vol. 6, No. 4, December 1995, pp 595-612.
18.   Alexander, M. J., Cohoon, J. P., Ganley, J. L., Robins, G., Placement and Routing for Performance-Oriented FPGA
      Layout, VLSI Design: an International Journal of Custom-Chip Design, Simulation, and Testing, Vol. 7, No. 1, 1998.
19.   Alexander, M. J., and Robins, G., New Performance-Driven FPGA Routing Algorithms, IEEE Transactions on
      Computer-Aided Design of Integrated Circuits and Systems, Vol. 15, No. 12, December 1996, pp. 1505-1517.
20.   Kahng, A. B., Robins, G., and Walkup, E. A., How to Test a Tree, Networks, 32, 1998, pp. 189-197.
21.   Pearson, W. R., Robins, G., Wrege, D. E., and Zhang, T., On the Primer Selection Problem for Polymerase Chain
      Reaction Experiments, Discrete and Applied Mathematics, Vol. 71, 1996, pp. 231-246.
22.   Pearson, W. R., Robins, G., and Zhang, T., Generalized Neighbor-Joining: More Reliable Phylogenetic Tree
      Reconstruction, Journal of Molecular Biology and Evolution, Vol. 16, No. 6, pp. 806-816, 1999.
23.   Kahng, A. B., Robins, G., Singh, A., and Zelikovsky, A., Filling Algorithms and Analyses for Layout Density Control,
      IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, Vol. 18, No. 4, April 1999, pp. 445-462.
24.   Robins, G., Robinson, B. L., and Sethi, B. S., On Detecting Spatial Regularity in Noisy Images, Information
      Processing Letters, No. 69, 1999, pp. 189-195.
25.   Helvig, C. S., Robins, G., and Zelikovsky, A., New Approximation Algorithms for Routing with Multi-Port Terminals,
      IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, Vol 19, No. 10, Oct 2000, pp. 1118-1128.
26.   Helvig, C. S., Robins, G., and Zelikovsky, A., An Improved Approximation Scheme for the Group Steiner Problem,
      Networks, Vol. 37, No. 1, January 2001, pp. 8-20.
27.   Chen, Y., Kahng, A. B., Robins, G., and Zelikovsky, A., Area Fill Synthesis for Uniform Layout Density, IEEE Trans.
      on Computer-Aided Design of Integrated Circuits and Systems, Vol. 21, No. 10, October, 2002, pp. 1132-1147.
28.   Helvig, C. S., Robins, G., and Zelikovsky, A., The Moving-Target Traveling Salesman Problem, Journal of Algorithms,
      Vol. 49, No. 1, October 2003, pp. 153-174.
PHS 398/2590 (Rev. 05/01)                             Page    2                              Continuation Page Format Page
CONTINUATION PAGE                   Principal Investigator/Program Director      Dr. Gabriel Robins
                                    (Last, first, middle):
31. Kaczmarek, T., Bates, R., and Robins, G., Recent Developments in NIKL, American Association of Artificial
    Intelligence, Proc. Fifth National Conf. on Artificial Intelligence, Philadelphia, Pennsylvania, August 1986, pp. 978-985.
32. Robins, G., The ISI Grapher: a Portable Tool for Displaying Graphs Pictorially, Proc. Symboliikka '87, Helsinki,
    Finland, August 17-18, 1987, pp. 44-60.
33. Robins, G., Applications of The ISI Grapher, Proc. Fourth Annual Artificial Intelligence and Advanced Computer
    Conference, Long Beach, California, May 1988, pp. 105-130.
34. Robins, G., Signal Constellation Design Tool: A Case Study in User Interface Synthesis, Proc. Second International
    Conference on Computer-Assisted Learning, Dallas, Texas, May 1989, pp. 452-467.
35. Robins, G., An Interactive Gate-Level Simulator of a Classical Von Neumann Architecture, as an Educational Aid for
    Introducing Novices to the Fundamentals of Computer Organization, Proc. Third International Conference on Human-
    Computer Interaction, Boston, Massachusetts, September 1989.
36. Kahng, A. B., and Robins, G., A New Family of Steiner Tree Heuristics with Good Performance: The Iterated 1-Steiner
    Approach, Proc. IEEE International Conference on Computer-Aided Design, Santa Clara, November 1990, pp. 428-
    431. Won a Distinguished Paper Award.
37. Kahng, A. B., Cong, J., and Robins, G., High-Performance Clock Routing Based on Recursive Geometric Matching,
    Proc. ACM/IEEE Design Automation Conference, San Francisco, June 1991, pp. 322-327.
38. Kahng, A. B., and Robins, G., Optimal Algorithms for Determining Regularity in Pointsets, Proc. Canadian Conference
    on Computational Geometry, Vancouver, August 1991, pp. 167-170.
39. Cong, J., Kahng, A. B., and Robins, G., On Clock Routing For General Cell Layouts, Proc. IEEE International ASIC
    Conference, Rochester, September 1991, pp. P14:5.1-P14:5.4.
40. Cong, J., Kahng, A. B., Robins, G., M. Sarrafzadeh and C. K. Wong, Performance-Driven Global Routing for Cell
    Based IC's, Proc. IEEE International Conference on Computer Design, Cambridge, October 1991, pp. 170-173.
41. Cong, J., Kahng, A. B., Robins, G., M. Sarrafzadeh and C. K. Wong, Provably-Good Algorithms for Performance-
    Driven Global Routing, Proc. IEEE Intl. Symp. on Circuits and Systems, San Diego, May 1992, pp. 2240-2243.
42. Kahng, A. B., Robins, G. and Walkup, E. A., New Results and Algorithms for MCM Substrate Testing, Proc. IEEE
    International Symposium on Circuits and Systems, San Diego, May 1992, pp. 1113-1116.
43. Alpert, C., Cong, J., Kahng, A. B., Robins, G., and Sarrafzadeh, M., Minimum Density Interconnection Trees, Proc.
    IEEE International Symposium on Circuits and Systems, Chicago, May 1993, pp. 1865-1868.
44. Barrera, T., Griffith, J., McKee, S. A., Robins, G., and Zhang, T., Toward a Steiner Engine: Enhanced Serial and
    Parallel Implementations of the Iterated 1-Steiner MRST Algorithm, Proc. Great Lakes Symposium on VLSI,
    Kalamazoo, MI, March 1993, pp. 90-94.
45. Boese, K. D., Kahng, A. B., and Robins, G., High Performance Routing Trees With Identified Critical Sinks, Proc.
    ACM/IEEE Design Automation Conference, Dallas, June 1993, pp. 182-187.
46. Boese, K. D., Kahng, A. B., McCoy, B. A. and Robins, G., Toward Optimal Routing Trees, Proc. ACM/SIGDA Physical
    Design Workshop, Lake Arrowhead, CA, April 1993, pp. 44-51.
47. Barrera, T Griffith, J., Robins, G., and Zhang, T., Narrowing the Gap: Near-Optimal Steiner Trees in Polynomial
               .,
    Time, Proc. IEEE International ASIC Conference, Rochester, September 1993, pp. 87-90.
48. Boese, K. D., Kahng, A. B., McCoy, B. A. and Robins, G., Fidelity and Near-Optimality of Elmore-Based Routing
    Constructions, Proc. IEEE International Conference on Computer Design, Cambridge, October 1993, pp. 81-84.
49. McCoy, B. A., and Robins, G., Non-Tree Routing, Proc. European Design Automation Conference, Paris, France,
    February 1994, pp. 430-434.
50. Alexander, M. J., and Robins, G., A Unified New Approach to FPGA Routing Based on Multi-Weighted Graphs, Proc.
    ACM/SIGDA International Workshop on Field-Programmable Gate Arrays, Berkeley, CA, February 1994.
51. Hodes, T. D., McCoy, B. A., and Robins, G., Dynamically-Wiresized Elmore-Based Routing Constructions, IEEE
    International Symposium on Circuits and Systems, London, England, May 1994, Volume I, pp. 463-466.
52. Robins, G., and Salowe, J. S., On the Maximum Degree of Minimum Spanning Trees, ACM Symposium on
    Computational Geometry, Stoney Brook, NY, June 1994, pp. 250-258.
53. Boese, K. D., Kahng, A. B., McCoy, B. A., and Robins, G., Rectilinear Steiner Trees with Minimum Elmore Delay,
    Proc. ACM/IEEE Design Automation Conference, San Diego, CA, June 1994, pp. 381-386.
54. Alexander, M. J., and Robins, G., High Performance Routing for Field-Programmable Gate Arrays, Proc. IEEE
    International ASIC Conference, Rochester, NY, September 1994, pp. 138-141.
55. Alexander, M. J., Cohoon, J. P., Ganley, J. L., and Robins, G., An Architecture -Independent Approach to FPGA
    Routing Based on Multi-Weighted Graphs, Proc. European Design Automation Conference, Grenoble, France,
    September, 1994, pp. 259-264.
56. Robins, G., and Robinson, B. L., Pattern Minefield Detection from Inexact Data, Proc. SPIE International Symposium
    on Aerospace/Defense Sensing and Dual-Use Photonics, Volume 2496, Orlando, FL, April 1995, pp. 568-574.
57. Alexander, M. J., and Robins, G., New Performance-Driven FPGA Routing Algorithms, Proc. ACM/IEEE Design
    Automation Conference, San Francisco, CA, June 1995, pp. 562-567. Three-Dimensional Field Programmable Gate
    Arrays, Proc. IEEE International ASIC Conference, Austin, TX, September 1995, pp. 253-256.
58. Pearson, W. R., Robins, G., Wrege, D. E., and Zhang, T., A New Approach to Primer Selection in Polymerase
    Chain Reaction Experiments, Proc. International Conference on Intelligent Systems for Molecular Biology,
    Cambridge, England, July, 1995, pp. 285-291.



PHS 398/2590 (Rev. 05/01)                             Page    3                                 Continuation Page Format Page
CONTINUATION PAGE                  Principal Investigator/Program Director     Dr. Gabriel Robins
                                   (Last, first, middle):
59. Alexander, M. J Cohoon, J. P., Ganley, J. L., and Robins, G., Performance-Oriented Placement and Routing for
                       .,
    Field-Programmable Gate Arrays, Proc. European Design Automation Conference, Brighton, England, September,
    1995, pp. 80-85.
60. Alexander, M. J., Cohoon, J. P., Colflesh, J. L., Karro, J., Peters, E. L. and Robins, G., Physical Layout for Three-
    Dimensional FPGAs, 1996 ACM/SIGDA Physical Design Workshop, Reston, VA, April, 1996, pp. 142-149.
61. Alexander, M. J., Cohoon, J. P., Colflesh, J. L., Karro, J., Peters, E. L. and Robins, G., Placement and Routing for
    Three-Dimensional FPGAs, Canadian Workshop on Field-Programmable Devices, Toronto, May, 1996, pp. 11-18.
62. Bateman, C. D., Helvig, C. S., Robins, G., and Zelikovsky, A., Provably-Good Routing Tree Construction with Multi-
    Port Terminals, ACM/SIGDA International Symposium on Physical Design, Napa Valley, CA, April, 1997, pp. 96-102.
63. Helvig, C. S., Robins, G., and Zelikovsky, A., Improved Approximation Bounds for the Group Steiner Problem, Proc.
    Conference on Design Automation and Test in Europe, Paris, France, February, 1998, pp. 406-413.
64. Kahng, A. B., Robins, G., Singh, A., Wang, H., and Zelikovsky, A., Filling and Slotting: Analysis and Algorithms, Proc.
    International Symposium on Physical Design, Monterey, California, April, 1998, pp. 95-102.
65. Helvig, C. S., Robins, G., and Zelikovsky, A., oving-Target TSP and Related Problems, Proc. European Symposium
    on Algorithms, Venice, Italy, August, 1998, pp. 453-464, published as Lecture Notes in Computer Science, 1461, G.
    Bilardi, G. F. Italiano, A. Pietracaprina and G. Pucci (eds.), 1998.
66. Kahng, A. B., Robins, G., Singh, A., and Zelikovsky, A., New and Exact Filling Algorithms for Layout Density Control,
    Proc. VLSI Design Conference, Goa, India, January 1999, pp. 106-110.
67. Kahng, A. B., Robins, G., Singh, A., and Zelikovsky, A., New Multi-Level and Hierarchical Algorithms for Layout
    Density Control, Proc. Asia and South Pacific Design Automation Conference, Hong Kong, China, January 1999, pp.
    221-224. Nominated for Best Paper Award.
68. Robins, G., and Zelikovsky, A., Improved Steiner Tree Approximation in Graphs, SIAM-ACM Symposium on Discrete
    Algorithms (SODA), San Francisco, CA, January 2000, pp. 770-779.
69. Chen, Y., Kahng, A. B., Robins, G., and Zelikovsky, A., Monte-Carlo Algorithms for Layout Density Control, Proc. Asia
    and South Pacific Design Automation Conference, Yokohama, Japan, January 2000, pp. 523-528.
70. Chen, Y., Kahng, A. B., Robins, G., and Zelikovsky, A., Practical Iterated Fill Synthesis for CMP Uniformity, Proc.
    Design Automation Conference, Los Angeles, June 2000, pp. 671-674.
71. Blair, D., and Robins, G., A New Distributed System for Large-Scale Sequence Analyses, International
    Conference on Intelligent Systems for Molecular Biology, San Diego, August 2000.
72. Chen, Y., Kahng, A. B., Robins, G., and Zelikovsky, A., Hierarchical Dummy Fill for Process Uniformity, Asia and
    South Pacific Design Automation Conference, Yokohama, Japan, January 2001, pp. 139-144.
73. Chen, Y., Kahng, A. B., Robins, G., and Zelikovsky, A., Closing the Smoothness and Uniformity Gap in Area Fill
    Synthesis, ACM/SIGDA International Symposium on Physical Design, Del Mar, CA, April 2002, pp. 137-142.
74. Chen, Y., Kahng, A. B., Robins, G., and Zelikovsky, A., Monte-Carlo Methods for Chemical-Mechanical Planarization
    on Multiple-Layer and Dual-Material Models, Proc. Microlithography 2002, International Society of Optical Engineering
    (SPIE), Santa Clara, CA, March 2002.
75. Chen, Y., Kahng, A. B., Robins, G., Zelikovsky, A., and Zheng, Y., Area Fill Generation With Inherent Data Volume
    Reduction, Proc. Design Automation and Testing in Europe, Munich, Germany, March 2003, pp. 868-873.
C. Research Support
Ongoing Research Support: None
Completed Research Support:

Robins (PI)                                     8/1999 - 8/2003            CCR-9988331
National Science Foundation                     $421,943
Research in Layout Optimization for Advanced Manufacturability Considerations

Robins (PI)                                                  9/1995 - 9/2003         1995
Packard Foundation Fellowship                                $550,000
Efficient Algorithms for Combinatorial Problems

Robins (PI)                                     9/1994 - 9/2000                      MIP-9457412
NSF Foundation Young Investigator Award         $312,500
New Directions in VLSI CAD and Computational Biology

Robins (Co-PI)                                 9/1994 - 9/2000                       LM04961
National Institute of Health / NLM             $1,175,000
New Approaches to Phylogeny, Alignment, and Sequence Matching

PHS 398/2590 (Rev. 05/01)                            Page    4                                Continuation Page Format Page