UVa VLSI CAD Group
VLSI CAD Research Group

Department of Computer Science
School of Engineering and Applied Science
University of Virginia

Research Summary

Recent trends in deep-submicron very large-scale integration (VLSI) circuit technology have resulted in new requirements for algorithms in integrated circuit layout. Much of my work centers on new formulations that capture performance and density criteria in the physical layout phases of computer-aided design (CAD). Our results include near-optimal approximation algorithms for such computationally difficult problems as minimum-cost Steiner tree routing, low-skew clock networks, cost-radius tradeoffs, bounded-density trees, circuit probe testing, high-performing Elmore-based constructions, layout density control, and improved manufacturability. Our methods address not only traditional and leading-edge integrated circuit (IC) technologies, but also alternate design styles such as field-programmable gate arrays (FPGAs) and multi-chip modules (MCMs). We have also investigated topics in discrete algorithms, computational geometry, and computational biology.

We address real-life practical problems from industry, while at the same time we strive to develop solutions of substantial theoretical significance. For example, in the early 1990s we predicted the increasing significance of performance-driven interconnect synthesis. This area indeed became very critical in recent years as semiconductor feature sizes continued to shrink, since faster transistor switching speeds and larger chip dimensions imply that interconnects now dominate logic gates as the determinants of circuit delay and overall system performance. Our early work in this area helped usher in a new-generation of tools for "ultra-deep submicron" design that address exactly these issues.

Our code distributions have been regularly requested by numerous research groups around the world, and have formed the basis of implementations in both academic and commercial settings. For example, the ISI Grapher tool that I developed for the pictorial display of graphs was marketed commercially by ExperTelligence, Inc., and enjoyed a large user base worldwide. The manual accompanying this commercial tool was based on one of my papers, and an 18-page chapter was devoted to describing this software tool in the book "Multicomputer Vision" (Academic Press, 204 pages). Additional examples of the impact of our research and codes are detailed below.

Our papers and results are now cited in every textbook in our area. For example, the basic VLSI CAD textbook "An Introduction to VLSI Physical Design" (McGraw Hill, 334 pages) devotes six pages to describing our bounded-radius bounded-cost routing methodology, and uses several additional pages to explain our Iterated 1-Steiner, clock routing, and Elmore-based methods. The textbook "Algorithms for VLSI Design Automation" (John Wiley & Sons, 326 pages) spends six pages on discussing our Iterated 1-Steiner routing algorithm, including our fast spanning-tree update technique; this textbook also discusses our algorithms for timing-driven routing, and refers to our original journal publication on this topic as "a key paper". The VLSI CAD textbook "Algorithms for VLSI Physical Design Automation" (Kluwer Academic Publishers, 538 pages) by Naveed Sherwani of Intel devotes three pages to discussing our matching-based techniques for clock routing. The textbook "VLSI Physical Design Automation" (IEEE Press, 426 pages) discusses our Iterated 1-Steiner algorithm, as well as our bounded-radius bounded-cost approach. The recent book "On Chip Inductance in High Speed Integrated Circuits" (Kluwer Academic Publishers, 303 pages) cites several of our papers on Elmore-based algorithms for high-performance routing. Our pattern-detection algorithms are described over the span of three pages in the recent textbook "Algorithms Sequential & Parallel" (Prentice Hall, 330 pages).

We developed new best-known provably-good results for most of the NP-complete (i.e., computationally intractable) problems listed above. For example, we showed that, surprisingly, previous published rectilinear Steiner tree heuristics perform quite poorly on certain pathological examples, despite published claims to the contrary. On the positive side, we have proposed the best-performing rectilinear Steiner tree heuristics to date. Our 1-Steiner -based algorithms produce solutions with average cost around 11% better than minimum spanning trees, and less than 0.25% away from optimal; moreover our algorithms actually find optimal solutions for about 90% of typical inputs. The definitive book on this topic, namely "The Steiner Tree Problem" (North Holland, 339 pages) authored researchers at Lucent / Bell Labs, George Mason University, and the University of Copenhagen, devotes two pages to discussing our techniques, and this book refers to the performance of our Steiner tree algorithms as "the best for any heuristic discussed so far." Our Iterated 1-Steiner technique is also described over several pages in the book "Steiner Minimal Trees" authored by Professor Dietmar Cieslik from Ernst-Moritz-Arndt University in Germany. Our Steiner tree codes and routing algorithms were incorporated into commercial tools such as the popular Timberwolf CAD system, marketed by InternetCAD.com and Timberwolf Systems Inc. Our Steiner tree codes were also used by groups at UC San Diego, UC Santa Cruz, University of Illinois, Cadence Design Systems, LSI Logic Corporation, and Emergent Information Technologies, Inc., among others.

For the more general (and even more difficult) group Steiner problem in graphs, where the objective is to interconnect groups of nodes (rather than individual nodes), we developed algorithms with new, best-known bounds. Whereas the best previous algorithm had a solution performance ratio of k times the optimal, where k is the number of groups, we proved that solutions produced by our new polynomial-time heuristics never cost more than k^e times the optimal in the worst case, for any user-fixed arbitrarily small e>0. This was a considerable improvement over the state-of-the-art and solved a long-standing open problem. We also proved an impossibility result, showing that it is not feasible to approximate the group Steiner problem in polynomial time to within less than a logarithmic factor. Aside from its theoretical significance, this algorithm found practical applications in industrial settings, e.g., in the routing of nets with multi-terminal ports (where each pin may contain multiple electically-equivalent terminals), and in placement (where modules may be rotated or flipped).

Our research on the Steiner problem has led us to discover other interesting results, such as bounds on the maximum degree of minimum spanning trees in arbitrary dimensions and under several metrics, resolving several long-standing open problems. For example, we have invented a perturbation-based proof technique to show that every pointset in the Manhattan plane has a minimum spanning tree with maximum degree of at most 4, and that every pointset in three-dimensional Manhattan space has a minimum spanning tree with maximum degree of at most 14 (the best previously known upper bounds were 6 and 26, respectively). We also showed how to compute such trees in polynomial time (previously to our work, this was assumed to be an intractable problem). Our perturbation-based proof techniques and minimum spanning tree bounds were the basis for follow-up research at e.g., Georgia Institute of Technology and Simplex Solutions, Inc. Our theorems and proofs regarding low-degree minimum spanning trees are now also described in books such as "Steiner Minimal Trees" (Kluwer Academic Publishers, 319 pages).

We addressed the problem of bounded-skew clock routing, which arises in performance-driven applications. We pioneered a recursive geometric matching-based approach, and applied it to both cell-based and building-block designs. Our methods achieve near-zero clock skew while maintaining reasonable total wirelength. Numerous research groups, both in academia and in industry (e.g., UCLA, UC San Diego, Cadence Design Systems), have since used our bottom-up recursive matching techniques as the basis of their research or implementations. The book "Clock Distribution Networks in VLSI Circuits and Systems" (IEEE Press, 525 pages) devotes 13 pages to reprinting our seminal paper on clock routing.

We proposed the first general formulation of performance-driven global routing for both general cell and block-based designs. Our algorithm smoothly trades off wirelength for tree radius based on a user-controlled parameter, and has a constant-factor worst-case performance ratio with respect to both tree cost and tree radius, simultaneously. This was the first such result in the CAD literature, and this work has opened the door for subsequent works in this area (e.g., the AHHK bounded-radius algorithm of Alpert et al.). Retrospectively, cost/radius tradeoffs were shown to reflect the evolution of an important parameter of the underlying VLSI process technology, namely the "resistance ratio" governing driver on-resistance and per-unit interconnect resistance. It is now an accepted precept that a routing construction must flexibly allow engineering tradeoffs of sink delay and routing cost (wiring area), and our work in this area has formed the basis of Ph.D. dissertations elsewhere (e.g., the Ph.D. thesis of Dr. Charles Chiang at Northwestern University).

One area of research strives to unify some of the above constructions in solving a minimum-density routing tree formulation; here, the objective is to reduce crosstalk in circuits by minimizing the maximum amount of routing resources used in any region of the layout. Our novel proof techniques yielded provably-good bounds as well as enabled an efficient algorithm that produces routings with average density within a constant factor of optimal. This work has also led to a general multi-objective minimization formulation.

We developed a new methodology for constructing Elmore-based high-performance interconnection topologies that accommodate sink priorities derived from static timing analysis. This approach successfully sidesteps delay modeling inaccuracies inherent in previous methods, and instead builds low delay trees by directly optimizing the relevant criterion (e.g., the Elmore delay formula). This methodology also extends to critical sink formulations, as well as other delay models. Extensive testing has shown that this new delay optimization scheme significantly outperforms all previous strategies, yielding up to 70% average reduction in delay for typical nets, depending on the technology parameters. We have also proved a decomposition theorem for optimal Elmore-based constructions, the first result of its kind in the CAD literature. We also generalized Hanan's classical Steiner tree characterization to Elmore delay-optimal trees. Our algorithms and codes have been benchmarked extensively by other researchers (e.g., a CAD group at the University of Illinois states in one of their papers that our high-performance routing algorithm "has produced some of the best delay figures reported in the literature.") This line of research has proved to be crucial in today's deep-submicron design methodologies. Indeed, our underlying ideas such as using a more accurate delay function like Elmore's formula, as well as exploiting its convexity in driving the routing process, have since been used by a number of other groups in industry (e.g., at the IBM Austin Research Laboratory, InternetCAD.com, and the LSI Logic Corporation), as well as in academia (e.g., UC San Diego, University of Washington, Professor Sachin Sapatnekar's group at the University of Minnesota, and the research group of Professor Ernest Kuh, former EECS Chair and former Dean of Engineering at UC Berkeley).

An implicit premise of previous routing methods is that the routing topology must correspond to a tree (i.e., it does not contain cycles). We investigated the consequences of abandoning this basic axiom and instead allowing routing topologies to correspond to arbitrary graphs (i.e., where cycles are allowed). We have shown that adding extra wires to an existing routing tree can often significantly improve signal propagation delay and skew, by exploiting a tradeoff between circuit capacitance and resistance. We developed a new routing algorithm based on this phenomenon, and explored the synergy inherent in combining this with other optimizations, such as wiresizing. Whereas previous wiresizing methods are static in that they wiresize a given fixed topology, we have used wiresizing considerations to drive the routing construction process itself. This enabled routings with improved delay as well as skew. Our non-tree routing methodology has been used at e.g., Berkeley and at the Hewlett-Packard Corporation, among others.

We have developed the first general architecture-independent framework for field-programmable gate array (FPGA) routing, where multiple competing objectives can be optimized simultaneously under a smooth designer-controlled tradeoff. Our approach is the first to unify the global and detailed routing phases in FPGA's, and significantly outperformed all previous routers on standard industry benchmarks. This method is based on a general multi-weighted graph formulation which we invented, a framework that proved to be of independent theoretical interest (e.g., researchers at Cadence Design Systems have built upon our ideas regarding multi-weighted graphs). Our multi-weighted graph methodology also has applications in many other combinatorial optimization problems, such as traveling salesman, graph matching, partitioning, and vehicle routing problems.

In the area of circuit testing, we investigated new problems that arise in multi-chip module packaging technology. We formulated the problem of multi-chip module substrate testing as a metric traveling salesman scheduling of an optimal set of tree "probes", and proposed an efficient provably-good heuristic. Our algorithm produces (in optimal time) the optimal number of probes necessary to completely test an MCM substrate. We also proved that in terms of scheduling these test probes, our solution to this NP-complete (i.e., computationally intractable) problem never exceeds the theoretically best possible by more than 50%. This methodology was adopted by the Alcoa Corporation in their manufacturing process.

We investigated new approaches to reduce VLSI manufacturing variation and improve performance predictability and yield, by making layouts uniform with respect to certain density criteria that arise during chemical-mechanical polishing (CMP). We developed several techniques for density analyses and control, including linear-programming, multi-level, and hierarchical based approaches. This line of research yielded the first realistic formulations of the layout filling problems that arise in optimization for manufacturability, and provided a new unification between manufacturing and physical design. Whereas previously only foundries and special mask data processing tools performed layout post-processing for density control, we enabled a convergence where performance verification flows can rely on such layout manipulations being embedded within the layout synthesis (place-and-route) flow. Our results in this area have been used by leading companies such as MicroUnity Systems Engineering, Inc. and Cadence Design Systems, as well as by startup companies (notably CMP Technology, Inc.). Actual production flows at Motorola Inc. have used our density control algorithms, and our approaches have formed the foundation for follow-up academic research in this area at UCLA and by Professor Martin Wong's lab at UT Austin.

On the multidisciplinary front, we have found that much of our expertise and techniques from VLSI CAD transfer to problem-solving in other, seemingly unrelated fields. Such excursions into other areas offer very fertile opportunities for "technology transfer"; for example, we have successfully explored such diverse research areas as landmine detection, motion planning, minimal surfaces, and computational biology, as described below.

We have proposed a simple optimal algorithm for determining all maximal equally-spaced collinear subsets of a pointset. Our algorithm generalizes to finding two-dimensional spatial regularities, as well as to inexact cases where a specified location drift can be accommodated in the patterns, as may be the case in real scenarios. There are many practical pattern-detection applications to this work, including finding rows of landmines in infrared images, and these results have drawn considerable interest from, e.g., the U.S. Army, which used our code for landmine detection at its Fort Belvoir research labs. Our pattern-detection algorithms have also served as the basis for several parallel implementations at the SUNY Buffalo's Center for Computational Research.

We have investigated robust motion planning, where we seek a minimum-cost path for a mobile agent subject to a minimum-width constraint. We used a network flow based transformation of this problem to obtain the first known polynomial-time algorithm for robust motion planning. We extended our motion planning formulation into a related result of independent interest: the first optimal algorithm for the discrete Plateau problem of minimum surfaces; our solution was published in the Proceedings of the National Academy of Sciences, and has attracted considerable attention from the national media (news articles about this work appeared in the Los Angeles Times, the Washington Post, the Boston Globe, and the San Diego Union-Tribune).

We also addressed important problems in computational biology, such as the construction of evolutionary trees over a given set of taxa (e.g., organisms, DNA molecules, etc.), where the optimization objective entails the best-fit of tree topologies under some criteria (e.g., least-squares). Another problem in computational biology that we investigated is the primer selection problem, which arises in polymerase chain reaction (PCR) experiments (i.e., DNA cloning). Here, given a set of DNA strands and a cost criterion, we seek to find a minimal covering set of compatible DNA subsequences (primers) with least cost. We have shown that this problem is NP-complete, and proposed several heuristics with provable near-optimal performance. Our algorithm has been used by biochemists to try to discover new proteins.

Additional problems we have researched include a new practical time-dependent variant of the classical Traveling Salesman Problem, called Moving-Target TSP. Here the objective is to span, using a tour, a given set of targets which move with constant velocities in arbitrary directions. In addition to pioneering this new formulation which directly generalizes TSP, we proved several interesting theorems regarding moving-target TSP tours, and we developed algorithms with the best-known performance bounds in terms of solution quality for this computationally difficult problem.

We have compiled some of our research in VLSI CAD into a book published by Kluwer Academic Publishers. Articles about our research have appeared in a number of national and international newspapers. The impact of our work has been substantial, in that it triggered or influenced many other research projects elsewhere in academia and in industry. Our work is described in textbooks, and is regularly cited by papers at major conferences and journals (e.g., the bibliographic search engine "Cite Seer" ranks me in the top one percent of all cited authors in that database).

My research efforts have been recognized with honors such as an invitation to become a member of the Defense Science Study Group in 1993, a National Science Foundation Young Investigator Award ($312K) in 1994, and a Packard Foundation Fellowship ($550K) in 1995, the latter being the first one at the University of Virginia, and still the only Packard Fellowship ever awarded to any researcher in my area. In 1996 I served as General Chair of the ACM/SIGDA Physical Design Workshop, and in 1997 I co-founded the ACM/SIGDA/IEEE International Symposium on Physical Design (ISPD), which has quickly evolved into the leading conference in the field of physical design. In 1997 I was awarded the Walter N. Munster Endowed Chair at UVa, and in 1998 I was invited to join the Army Science Board, the highest-level scientific advisory board to the U.S. Army. In 1999 I was asked by the U.S. National Academy of Engineering to co-organize the German-American Frontiers of Engineering Symposium, where top young engineers and scientists from the U.S. and Germany met in order to foster research collaborations. In 2000 I was asked to serve as Associate Editor of IEEE Transactions on Very Large Integration Systems, a flagship journal in our area. Over the years I was invited to serve as a member on a number of scientific boards and panels organized by the National Academy of Sciences (e.g., the 1997 Navy Future Study).

I plan to continue to pursue research that is both theoretically significant and practically relevant. I truly enjoy solving difficult problems and contributing to the state-of-the-art of scientific and engineering knowledge. I also derive genuine satisfaction from teaching, mentoring, and from seeing my students mature and succeed with respect to their own professional goals. In summary, I love research and academia, and I have no doubt whatsoever that this is indeed my life's calling.


Teaching Philosophy

I have always loved teaching, and this has been a crucial factor in my choice of an academic career. Over the years I have developed active-learning techniques for motivating students and for explaining difficult concepts in terms that are easy to grasp. I try to employ a proactive teaching style that incorporates student participation, humor, showmanship, and a constant search for ways to improve.

Good teaching is essential to molding top-notch future scientists and engineers out of young, impressionable minds. Teaching should therefore not take a back-seat to research, especially at the undergraduate level. I strongly believe that teaching and research are not independent endeavors, but rather are synergetic processes: my experience has shown that teaching can lead to good research topics, and conversely, research often provides new ways of explaining and teaching. Moreover, in my view teachers are much more than information sources: they also serve as mentors and role models to their students. Indeed, a good teacher can have a tremendous long-term impact on a student's life. I therefore resolved very early in my career to try to excel not only as a researcher, but also as a teacher, as an educator, and as a role model.

The quality of undergraduate education at the University of Virginia is superb. I truly enjoy teaching our talented undergraduates, and I always try to challenge them with interesting problems. Aside from the traditional classroom-centered teaching setting, I have found that an excellent, albeit less traditional way to teach students about a field is to expose them to current research in that area. I therefore also actively involve bright undergraduates in research; for example, seven of my co-authors on refereed research papers over the years were undergraduates, and I am currently working with additional undergraduates. This not only enhances the students' undergraduate educational experience, but also better prepares them for a more productive graduate school or industry career. One of the undergraduates that I advised won the Louis T. Rader Award (given yearly to two UVa undergraduates for research excellence) and gave a presentation at the historical UVa Rotunda. Most of the undergraduates that I supervised went on to do Ph.D. work at top universities (e.g., UC Berkeley, UIUC, CMU, and Duke). Occasionally one of my former students returns to visit me and mentions how helpful their training with me was in their career and in their life in general: hearing these success stories always brings tremendous joy to my heart!

Another non-traditional teaching mechanism that I use to teach students practical skills is the Web Team, which I founded at UVa when the Web was born in 1994. The Web Team is a group of highly motivated undergraduates which help numerous faculty, departments, and offices around the University with all Web-related projects, including creating and maintaining Web sites, designing and implementing databases, programming and scripting, automating office work flow, operating digital cameras and video equipment, giving Web-based presentations and demos, designing and producing brochures, posters and newsletters, etc. In short, the Web Team is a highly effective, all-purpose group that is ready and eager to help any faculty or administrator with technical issues. Examples of Web sites created from scratch by the Web Team are those of the School of Engineering, the Office of the Vice Provost for Research, the Virginia Engineering Foundation, the Gateway Project, the Renaissance School, the Packard Foundation, among many other offices and organizations. Another major project undertaken by the Web Team is the creation of the CS department brochure, a comprehensive full-color publication which was mailed to thousands of faculty, deans, provosts, and companies around the world. This brochure has garnered much praise from universities around the world, and has helped enhance the image and reputation of our own Department and School.

The Web Team has proved to be a tremendously useful and effective teaching tool. The undergraduates that rotated through the Web Team have learned not only useful technical skills such as programming, scripting, writing, typesetting, Web site creation, image manipulation, networking principles, and system administration, but they also acquired very valuable "life skills" with respect to issues such as organization, prioritization, time management, public relations, user support, quality control, proofreading, presentation, responsibility, meeting deadlines, and team work. Students who spent time on the Web Team have been rapidly hired by technology companies at consistently high salaries. Thus, the Web Team provides a wonderful vehicle for students to learn very important skills in a "real life" setting, as well as offers an indispensable resource to faculty and administrators around our University, a true win-win situation. Former Web Team members often contact or visit me, and corroborate the above observations. For example, one former Web Team member, Daryoush Mansouri, who now works at a New York company called Grey Interactive, has sent me an unsolicited Email last April saying "it's amazing how much of what I do today I learned while working with the webteam... It's certainly paid off." I consider such feedback an excellent metric of teaching success.

Regarding the more traditional teaching mechanism, namely the classroom, over the years I have developed and taught numerous courses (both undergraduate and graduate) on topics such as VLSI CAD, algorithms, discrete mathematics, computational geometry, and theoretical computer science. I have also developed a seminar where students practiced the art of performing effective research, identifying important problems, and solving them successfully. Since 1993 I have organized and conducted a yearly "orientation" seminar (CS696) for all our incoming computer science graduate students, which rapidly brings our incoming students up to speed with respect to graduate school life, our computing infrastructure, and most importantly, instills in the students the motivation to quickly get involved in active research. I strongly believe that in addition to the traditional job of transmitting information to students, my responsibilities as an educator include enhancing the students' drive and motivation, encouraging them to excel, showing them how to become more productive, and helping them reach their full potential.

My teaching reviews have been consistently high, and my teaching efforts over the years have been recognized with several honors, including a Distinguished Teaching Award, an All-University Outstanding Teaching Award, and a University Teaching Fellowship. However, despite these successes, I feel that I will always have much left to learn about the art of teaching. I therefore regularly poll my students for feedback using mid-semester teaching evaluations. I also became heavily involved in the activities of the University of Virginia's Teaching Resource Center (TRC). I have regularly participated in teaching workshops and seminars given by world-renown educators, and I also actively encourage my colleagues to attend these meetings (e.g., announcement packets from the Teaching Resource Center regarding University Teaching Fellowships include a cover letter from me explaining the tremendous benefits of these programs; in fact, I was so impressed with the Teaching Resource Center that I took it upon myself to augment their meager budget with a significant amount of my own funds in order to help support their activities). I welcome such opportunities to meet with colleagues from other disciplines who share a genuine interest in teaching excellence. Such exciting interactions have broadened my horizons and afforded me many new and fresh perspectives on the art of teaching. In summary, I view excellence in teaching as a continually evolving process of constant improvement, rather than a fixed goal. I will continue to actively improve my effectiveness as an educator, and to encourage others to do the same. It is my hope that my efforts to improve the quality of education will one day have a substantial impact not only at UVa, but also at the national level as well.


Service and Leadership Summary

Over the years I have performed extensive service to the Department, to the University, and to my professional area, examples of which are described below. In all of my service activities, I have always tried to exercise the leadership to search for, and indeed sometimes altogether invent, non-obvious ways in which the standards may be raised, or some significant impact can be created. Of course I am also engaged in plenty of the traditional faculty service activities, such as various departmental committees, journal refereeing, editorship activities, conference organization, hosting meetings, serving on the UVa Faculty Senate, serving on the School of Engineering Faculty Council, chairing the Dean's Research Advisory Council, membership in a number of NSF, DoD, NAS, and NAE boards and panels, etc. but I will not dwell on these activities here. Rather, I would like to describe some of my non-conventional, high-impact service activities, which I view as particularly significant.

For example, when the Web was born in 1994 I immediately realized that it would have a tremendous global impact on the world. I therefore created in that same year the CS Web Team, a group of top-notch motivated undergraduates that assisted all faculty and administrators with any Web-related tasks. Due to the creation of the Web Team, our department soon became the first at UVa to have a Web site, and our School of Engineering became one of the first in the country that could boast a Web presence. (Note: that a department or a school has a Web site is of course tautological these days, but back in 1994 when the Web was in its infancy, having a Web site was quite rare and novel). When funding for this enterprise was not always available, I often funded these activities out of my own grants (and indeed sometimes I financed Web Team operations out of my own pocket). However, I viewed this as an excellent investment in the future of our Department and our University, and indeed I was not disappointed: the Web Team has acted as an early catalyst to usher the rest of the University into the Information Age, and our collective efforts along these lines have been widely recognized. For example, in 2000 Yahoo!'s Internet Life magazine ranked the University of Virginia as number eight in the country in their annual rankings of "America's Most Wired Colleges". And due to our early web presence head-start, our Department's Web server now receives over one hundred thousand "hits" per day (i.e., more than a hit per second around the clock).

Another major service project which I personally spearheaded was the creation of our Department's brochure, a full-color glossy 64-page professional-looking publication which describes in detail our research activities, faculty backgrounds, funding track record, and our departmental environment and atmosphere. I then personally oversaw the mass-mailing of our brochure to every computer science faculty member in the country, as well as to all engineering deans, and to selected provosts and companies. We also targeted many foreign universities in addition to domestic institutions. Over five thousand copies of our brochure were mailed in all (in a time-staggered manner over a six-month period, in order to maximize the PR impact). This massive PR blitz has proved highly effective: aside from receiving kudos from many of our colleagues around the world (indeed some departments have even adopted our brochure format and style in their own brochures), a number of our incoming graduate students have named our brochure when asked what attracted them to apply to our department. In addition, the new brochure has been instrumental in our faculty recruiting efforts. In retrospect, the brochure's great success was well worth the (hundreds of hours of my) time that I invested in this project. Indeed, some other departments and universities have modeled their own brochures after ours in terms of style, format, and scope.

One service activity that I am particularly fond of is our Department's poster drive. After I received my Packard Fellowship in 1995, one of the first things I did was purchase a large-format (i.e., 3-foot wide continuous paper roll) full-color postscript poster printer. Shortly thereafter, I created a set of five large (3'x4') posters that describe in detail our Department's research projects, our faculty, and our accomplishments on various fronts. These posters still hang in our Department's hallways, and have received very positive comments from visitors, parents, and faculty candidates (a copy of this set of posters was displayed at Thornton Hall, and a third set of these posters was created in a portable format that can be displayed at conferences on easels). Next, I created research-related posters, first for my own research projects (in order to provide examples to others), and then for other research projects. Other faculty have quickly followed suit, and today our Department's hallways are full of large colorful posters that beautifully present our research to visitors. Indeed, other departments around the School (e.g., EE and MSE) who have seen our posters have followed suit and started to create their own hallway posters (in the same style and format as ours, and often using our poster printer for production - we are always very glad to assist). We have also placed copies of these posters on the Web and we received a number of inquiries about our posters from other universities.

Another project that I am proud of is our computer museum. I first got the idea for this museum when I noticed that some of the more senior faculty members had in their possession historic computer artifacts, taken from long-obsolete machines (e.g., the Burroughs B205, the Burroughs 5000, the IBM 704, the CDC6600, etc.). Such artifacts always fascinate computing practitioners, as they very vividly illustrate the rate of progress of our field (e.g., a four-bit accumulator from the Burroughs B205 is the size of a lunchbox!). However, having these artifacts sit on individual faculty office shelves was wasteful, since that severely limited public access to them. I therefore commissioned the construction and installation of several large hallway display cases, created appropriate captions, and today those historical computer artifacts are available for everyone to enjoy. A web version of our computer museum draws many hits each day from around the world. Indeed we often receive unsolicited offers for artifact donations into our museum from people around the world who have seen our computer museum on the Web and would like to contribute to our collection.

One final example of what I consider high-impact service is the Computer Science Department Lounge, which I created a few years ago, after noticing that our Department lacked a "social hub". I commandeered a spare room, and furnished it with comfortable furniture, plants, soft lighting, coffee and tea makers, a large commercial-style sliding-door refrigerator, microwave and toaster ovens, and other conveniences. The CS Lounge features a continuous service of gourmet coffees, flavored teas, and various snacks, available to all visitors, and the refrigerator is always well-stocked with a large variety of soft drinks and juices (see www.cs.virginia.edu/lounge). I also stocked the lounge with dozens of challenging games and mind-stimulating puzzles, as well as a wall display showcasing recently-published research papers co-authored by our students, in order to encourage our students to publish more papers. The CS Lounge has quickly become an established (and self-sustaining) departmental fixture and a social hub where people congregate over coffee and snacks for lively research discussions or a friendly board game. Indeed, visitors from other departments and universities often praise the CS Lounge, and some of them have created a similar enterprise in their our department or institution.

Each of the service projects discussed above was unusual in some ways, either because it was unprecedented, or because it did not fit the normal funding mechanisms (indeed I sometime had to resort to funding some of these service projects myself, a leadership role that I welcome when the outcome so obviously benefits such a large number of people). None of the projects listed above were dictated by any existing policy or convention; rather, I had to muster the leadership to identify a basic need, invent or define a solution mechanism from scratch, and then follow through and nurture the plan to a successful conclusion, despite any potential obstacles. I really do enjoy this process! With each of the service projects such as the ones detailed above, my goals were to improve our Department's culture and collegiality, to make our Department and our School even more conducive to research, and to improve our overall visibility and external image. I believe that we have achieved considerable success towards these goals, and I plan on continuing to perform such service in the years to come.


Books and Book Chapters

  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 Multi-Chip Modules and Packages, J.-D. Cho and P. D. Franzon, Editors, World Scientific Publishing Co., 1996, pp. 181-198.

  4. Robins, G. and Zelikovsky, A. Minimum Steiner Tree Construction, in The Handbook of Algorithms for VLSI Physical Design Automation, C. J. Alpert, D. P. Mehta, and S. S. Sapatnekar (editors), CRC Press, 2009, Chapter 24, pp. 487-508.

  5. Hu, J., Robins, G, and Sze C. N., Timing-Driven Interconnect Synthesis, in The Handbook of Algorithms for VLSI Physical Design Automation, C. J. Alpert, D. P. Mehta, and S. S. Sapatnekar (editors), CRC Press, 2009, Chapter 25, pp. 509-534.

  6. Bolotnyy, L, and Robins, G., Multi-tag RFID systems, in the book "Security in RFID and Sensor Networks", Auerbach Publications, CRC Press, Taylor & Francis Group, 2009.

  7. Bolotnyy, L, and Robins, G., Physical Privacy and Security in RFID Systems, in the book "Security in RFID and Sensor Networks", Auerbach Publications, CRC Press, Taylor & Francis Group, 2009.

  8. Bolotnyy, L, and Robins, G., "Generalized and Inter-Tag Communication", in the book "Development and Implementation of RFID Technology", In-Tech Publishers, Vienna, Austria, 2009.

  9. Java Program Design: Third Edition, J.P. Cohoon and J. W. Davidson, McGraw-Hill, 2006. Seeks to attract a diverse audience to computing through motivating examples.

  10. Cohoon J. P., and Davidson, J. W., C++ Program Design: An Introduction to Programming and Object-Oriented Design, Third Edition, McGraw-Hill, 2002

  11. Cohoon, J. P., and Davidson, J. W., Laboratory Manual for C++ Program Design, WCB/McGraw-Hill, 1998.

  12. Varanelli, J. M., Cohoon, J. P., and Martin, W. N., , Population-oriented Simulated Annealing: an evolutionary thermodynamic hybrid approach to Very Large-Scale Integration Network Partitioning, Handbook of Evolutionary Computation, Oxford University Press, to appear.

  13. Martin, W. N., Lienig, J., and Cohoon, J. P., Parallel Genetic Algorithms Based on Punctuated Equilibria, Handbook of Evolutionary Computation, Oxford University Press, to appear.

  14. Cohoon, J. P., and Ganley, J. L., Rectilinear Interconnections In the Presence of Obstacles, in Routing in Electronic Modules, Y. T. Wong and M. Pecht (Editors), CRC Press, New York, NY, March 1996.

Journal Papers

  1. Foster, L., and Robins, G., Solution to a Number Theory Problem, American Mathematical Monthly, Vol. 89, No. 7, Aug-Sep, 1982, pp. 499-500.

  2. Robins, G., On Style, Expressibility, and Efficiency in Functional Programming Languages, UCLA Computer Science Department Quarterly, Fall 1987, pp. 105-121.

  3. Kahng, A. B., and Robins, G., Optimal Algorithms for Extracting Spatial Regularity in Images, Pattern Recognition Letters, 12, December 1991, pp. 757-764.

  4. 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.

  5. Kahng, A. B., and Robins, G., A New 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.

  6. 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.

  7. 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.

  8. Cong, J., Kahng A. B., and Robins, G., Matching-Based Methods for High-Performance Clock Routing, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 12, No. 8, August 1993, pp. 1157-1169.

  9. 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.

  10. 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.

  11. 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. Final journal submission version

  12. Griffith, J., Robins, G., Salowe, J. S., and Zhang, T., Closing the Gap: Near-Optimal Steiner Trees in Polynomial Time, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 13, No. 11, November 1994, pp. 1351-1365. Journal scanned/OCRed version and Steiner code (UNIX tar format)

  13. Robins, G., and Salowe, J. S., Low-Degree Minimum Spanning Trees, Discrete and Computational Geometry, Vol. 14, September 1995, pp. 151-165.

  14. 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. Journal scanned/OCRed version

  15. 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.

  16. 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.

  17. 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. FPGA benchmarks and routings

  18. Kahng, A. B., Robins, G., and Walkup, E. A., How to Test a Tree, Networks, 32, 1998, pp. 189-197.

  19. 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.

  20. 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.

  21. Kahng, A. B., Robins, G., Singh, A., and Zelikovsky, A., Filling Algorithms and Analyses for Layout Density Control, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 18, No. 4, April 1999, pp. 445-462.

  22. 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. Final journal submission version

  23. Helvig, C. S., Robins, G., and Zelikovsky, A., New Approximation Algorithms for Routing with Multi-Port Terminals, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol 19, No. 10, October 2000, pp. 1118-1128.

  24. Hu, T. C., Kahng, A. B., and Robins, G., Optimal Minimum-Surface Computations Using Network Flow, to appear in Mathematical Programming.

  25. 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.

  26. Chen, Y., Kahng, A. B., Robins, G., and Zelikovsky, A., Area Fill Synthesis for Uniform Layout Density, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 21, No. 10, October 2002, pp. 1132-1147.

  27. 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. Final journal submission version

  28. Haspel, D., Robins, G., and Street, B., A New Generalized Authority-Based Framework for Web Page Discovery, Undergraduate Research Journal.

  29. Robins, G. and Zelikovsky, A., Tighter Bounds for Graph Steiner Tree Approximation, SIAM Journal on Discrete Mathematics, Vol. 19, No. 1, 2005, pp. 122-134. This paper won the SIAM Outstanding Paper Prize in 2007

  30. Chen, Y., Kahng, A. B., Robins, G., Zelikovsky, A., and Zheng, Y., Compressible Area Fill Synthesis, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 24, No. 8, pp. 1169-1187, 2005.

  31. ..., Dutta, A., Kamani, N., Taylor, C. M., Kim, H. K., Robins, G., et al., The Encode (Encyclopedia of DNA Elements) Project, Science, Vol 306, No. 5696, October 2004, pp. 636-640.

  32. Chen, Y., Kahng, A. B., Robins, G., Zelikovsky, A., and Zheng, Y., Closing the Smoothness and Uniformity Gap in Area Fill Synthesis, to appear in ACM Transactions on Design Automation of Electronic Systems.

  33. Bolotnyy, L. and Robins, G., Multi-Tag RFID Systems, International Journal of Internet Protocol Technology, special issue on RFID: Technologies, Applications, and Trends, Vol 2, No 3/4, December, 2007, pp. 218-231. Invited paper
  34. A Fast Method for Generalized Starting Temperature Determination in Homogeneous Two-Stage Simulated Annealing Systems, J. M. Varanelli and J. P. Cohoon, Computers and Operations Research, pp. 481-503, 1999.

  35. Distributed Genetic Algorithms for the Floorplan Design Problem, J. P. Cohoon, S. U. Hegde, W. N. Martin, and D. S. Richards, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, April 1991, pp. 483-492.

  36. An Optimal Steiner Tree Algorithm for a Net Whose Terminals Lie on the Perimeter of a Rectangle, J. P. Cohoon, J. S. Salowe, and D. S. Richards, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, April 1990, pp. 398-407.

  37. Beaver: A Computational-Geometry-Based Tool for Switchbox Routing, J. P. Cohoon and P. L. Heck, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, June 1988, pp. 684-697.

Conference Papers

  1. Kaczmarek, T., Bates, R., and Robins, G., Recent Developments in NIKL, American Association of Artificial Intelligence, Proc. Fifth National Conference on Artificial Intelligence, Philadelphia, Pennsylvania, August 1986, pp. 978-985.

  2. Robins, G., The ISI Grapher: a Portable Tool for Displaying Graphs Pictorially, Proc. Symboliikka '87, Helsinki, Finland, August 17-18, 1987, pp. 44-60.

  3. Robins, G., Applications of The ISI Grapher, Proc. Fourth Annual Artificial Intelligence and Advanced Computer Conference, Long Beach, California, May 1988, pp. 105-130.

  4. 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.

  5. 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.

  6. Kahng, A. B., and Robins, G., A New Class of Steiner Tree Heuristics with Good Performance: The Iterated 1-Steiner Approach, Distinguished Paper, Proc. IEEE International Conference on Computer-Aided Design, Santa Clara, November 1990, pp. 428-431.

  7. 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.

  8. 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.

  9. 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.

  10. 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.

  11. Cong, J., Kahng, A. B., Robins, G., M. Sarrafzadeh and C. K. Wong, Provably-Good Algorithms for Performance-Driven Global Routing, Proc. IEEE International Symposium on Circuits and Systems, San Diego, May 1992, pp. 2240-2243.

  12. 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.

  13. 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.

  14. 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. Steiner code (UNIX tar format)

  15. 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.

  16. 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.

  17. 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. Steiner code (UNIX tar format)

  18. 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.

  19. McCoy, B. A., and Robins, G., Non-Tree Routing, Proc. European Design Automation Conference, Paris, France, February 1994, pp. 430-434.

  20. 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.

  21. 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.

  22. 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.

  23. 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.

  24. 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.

  25. 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.

  26. 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.

  27. 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. FPGA benchmarks and routings

  28. Alexander, M. J., Cohoon, J. P., Colflesh, J. L., Karro, J., and Robins, G., Three-Dimensional Field Programmable Gate Arrays, Proc. IEEE International ASIC Conference, Austin, TX, September 1995, pp. 253-256.

  29. 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.

  30. 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.

  31. 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.

  32. Alexander, M. J., Cohoon, J. P., Colflesh, J. L., Karro, J., Peters, E. L. and Robins, G., Placement and Routing for Three-Dimensional FPGAs, Fourth Canadian Workshop on Field-Programmable Devices, Toronto, Canada, May, 1996, pp. 11-18.

  33. 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. group Steiner code (Java)

  34. 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. group Steiner code (Java)

  35. 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.

  36. Helvig, C. S., Robins, G., and Zelikovsky, A., Moving-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.

  37. 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.

  38. 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

  39. 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.

  40. 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.

  41. 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.

  42. 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.

  43. 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.

  44. 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.

  45. 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, pp. 421-432.

  46. 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.

  47. ..., Robins, G. et al., Intelligence and Planning, Proceedings of the Conference on Interagency Requirements for Regional Stability / Capacity Building Research and Development, sponsored by the White House Office of Science and Technology Policy, the U.S. State Department, and the U.S. Department of Defense, Washington D.C., December 2004.

  48. Chen, Y., Kahng, A. B., Robins, G., Zelikovsky, A., and Zheng, Y., Evaluation of the New OASIS Format for Layout Fill Compression, Proc. IEEE International Conference on Electronics, Circuits and Systems, Israel, December 2004, pp. 377-382.

  49. Bolotnyy, L., and Robins, G., Multi-Tag Radio Frequency Identification Systems, Proc. IEEE Workshop on Automatic Identification Advanced Technologies, October, 2005, pp. 83-88.

  50. Bolotnyy, L., and Robins, G., Randomized Pseudo-Random Function Tree Walking Algorithm for Secure Radio-Frequency Identification, Proc. IEEE Workshop on Automatic Identification Advanced Technologies, October, 2005, pp. 43-48.

  51. Bolotnyy, L., and Robins, G., Generalized 'Yoking Proofs' for a Group of Radio Frequency Identification Tags, Proc. International Conference on Mobile and Ubiquitous Systems: Networks and Services (MOBIQUITOUS 2006), San Jose, CA, July, 2006.

  52. Bolotnyy, L., and Robins, G., Physically Unclonable Function -Based Security and Privacy in RFID Systems, Proc. IEEE International Conference on Pervasive Computing and Communications (PerCom 2007), New York, March, 2007, pp. 211-218.

  53. Bolotnyy, L., Krize, S., and Robins, G., The Practicality of Multi-Tag RFID Systems, Proc. International Conference on Enterprise Information System (ICEIS 2007), International Workshop on RFID Technology - Concepts, Applications, Challenges (IWRT 2007), Funchal, Portugal, June 2007.

  54. Bolotnyy, L. and Robins, G., The Case for Multi-Tag RFID Systems, Proc. International Conference on Wireless Algorithms, Systems and Applications (WASA 2007), Chicago, August 2007.

  55. Dutta, A., Karnani, N., Malhotra, A., Robins, G., and Taylor, C. M., Extraction of Human DNA Replication Timing Patterns from Discrete Microarray Data, IAPR International Conference on Pattern Recognition in Bioinformatics (PRIB 2008), Melbourne, Autralia, October, 2008.

  56. Ganely, L. J., and Cohoon, J. P., A Provably Good Moat Routing Algorithm, Proc. Sixth Great Lakes Symposium on VLSI, pp. 86-91, 1996.

  57. Ganely, L. J., and Cohoon, J. P., Optimal Rectilinear Steiner Minimal Trees in O(n^2 2.62^n) Time, Proc. Sixth Canadian Conference on Computational Geometry, pp. 308-313, 1994.

  58. Ganely, L. J., and Cohoon, J. P., Routing a Multi-Terminal Critical Net: Steiner Tree Construction in the Presence of Obstacles, Proc. IEEE International Symposium on Circuits and Systems, London, pp. 113-116, 1994.

  59. A. Sarkhar, R. Waxman, and J. P. Cohoon, System Design Utilizing Integrated Specification and Performance Models, ACM-IEEE VHDL International Users Forum, Oakland, CA, May 1994, pp. 90-100.

  60. J. C. Prey, J. P. Cohoon, and G. Fife, Software Engineering Beginning in the First Computer Science Course, SEI Conference on Software Engineering Education, San Antonio, TX, December 1993.

  61. J. Varanelli and J. P. Cohoon, Two-Stage Simulated Annealing, ACM Physical Design Workshop, Lake Arrowhead, CA, April 1993.

  62. Ganely, L. J., and Cohoon, J. P., A Faster Dynamic Programming Algorithm for Exact Rectilinear Steiner Minimal Trees, Proc. Fourth Great Lakes Symposium on VLSI, pp. 238-241, 1994.

  63. Ganely, L. J., and Cohoon, J. P., Thumbnail Rectilinear Steiner Trees, Proc. Fifth Great Lakes Symposium on VLSI, pp. 46-49, 1995.

News Articles

  1. Famous Last Words, Perth Sunday Times, Australia, April 27, 2008

  2. Dying Professor Randy Pausch's Lecture Worldwide Sensation, Perth Now, Australia, April 26, 2008

  3. Perspective: "I'm Living My Life" - Randy Pausch's Lessons Touch Many, The University of Virginia Magazine, Spring 2008. (local copy)

  4. Time of Your Life, Cavalier Daily, Nov 28, 2007. (local copy)

  5. Professor with Terminal Cancer: There's Less Time Than You Think, Daily Progress, Nov 28, 2007. (local copy)

  6. Randy Pausch Delivers Lecture on Time Management at UVA, Draws Crowd of Hundreds, Virginia Sentinel, Nov 28, 2007. (local copy)

  7. Randy Pausch: Time is All That Matters, UVa Today, Nov 28, 2007. (local copy)

  8. Prognosis Prompts Professor's Tour, NBC 29 / WVIR-TV, Nov 27, 2007. (local copy)

  9. Former UVa Prof Giving His Last Lectures, 19 News / WCAV-TV, 16 ABC, FOX 27 / WAMU, Nov 27, 2007. (local copy)

  10. Lecture of a Lifetime: U.Va.'s School of Engineering and Applied Science Hosts Talk by Randy Pausch, UVa Today, Nov 12, 2007. (local copy)

  11. With his Death Looming, Randy Pausch Gives the Lecture of a Lifetime, UVa Today, Sept 25, 2007. (local copy)

  12. Astronomer Kelsey Johnson Named Packard Fellow, UVa Today, Oct 8, 2007. (local copy)

  13. The Perspiration of Patenthood, IEEE-USA Today's Engineer Online, March, 2007. (local copy)

  14. Forensic Engineering: On the Trail of Truth, IEEE-USA Today's Engineer Online, September, 2006. (local copy)

  15. Babbage Institute Records Computer Science History, The Minnesota Daily, October 12, 2005. (local copy)

  16. Focusing on Partnerships, Impact - Engineering That Makes a Difference, School of Engineering and Applies Science, UVa, Spring Issue, Volume 4, Number 3, March 2002, p. 1.

  17. Robins Tackles Computing Problems, Inside UVa, November 10, 2000. (local copy)

  18. Give this to Will Smith, National Post, September 5, 2000.

  19. Models Connect Technology, Biology, Cavalier Daily, February 24, 2000. (web copy) (local copy)

  20. Robins Receives Grant of $500,000 from Packard Foundation, The University Journal, Vol. XVIII, No. 30, October 13, 1995, p. 1

  21. Computer Whiz and then Some, Virginia Engineering, University of Virginia, Spring 1996, pp. 7-8.

  22. Computer Scientist Wins Top Fellowship, Virginia Engineering, Winter, 1996, p. 5

  23. Packard Award Given to Gabriel Robins in the School of Engineering and Applied Science, Opportunities, University of Virginia, June 17, 1996, p. 15

  24. Workshop: Physical Design not in Great Shape, Electronic Engineering Times, April 22, 1996.

  25. Robins Earns Young Investigator Award, Virginia Engineering, Fall 1994, p. 4

  26. Faculty Members Earn Recognition from University, Cavalier Daily, April 26, 1995, p. 1

  27. Award-Winning Teachers Help Students Make Their Own Discoveries, Inside UVa, Vol. 25, Issue 15, April 28, 1995, pp. 1-3

  28. Scientists Float a New Solution to Puzzling Bubble, Los Angeles Times, Oct 1, 1992, pp. A-2, B-1, B-3

  29. Floating an Answer to Bubble Riddle, Nora Zamichow, San Diego Union-Tribune, Oct 1, 1992, pp. B-1, B-8

  30. Mathematics: Bubble Problem's Practical Potential, Washington Post, Monday, October 5, 1992, p. A-2

  31. Associated Press, The Boston Globe, Thursday, October 1, 1992, p. A-3

  32. Notices also appeared in The San Francisco Examiner, and the World Journal


Email feedback to Gabriel Robins or Jim Cohoon