LCSR/DCS Explorer
Director's Message
by Dr. Barbera Ryder, Acting Director, LCSR
There has been much activity in LCSR during the past seven months. A new planning effort with respect to equipment and office infrastructure has started. We are seeking to improve our research environment by restructuring our current xeroxing facilities with more support from the university. This summer we are auditing our current space usage as well, to facilitate planning for 1996-97.
Recently, we were honored that Martin Farach, one of our junior faculty, was awarded one of the coveted Sloan Foundation Fellowships.
While many LCSR grant proposals are still pending, four researchers have recently received new grants. Both Miles Murdocca and Sven Dickenson have obtained AT&T Foundation Equipment grants for "Video Imaging Database by Query by Image Content" and "Laboratory for LAN/WAN Interconnetion", respectively. Miles also received funding from Wavefront Research, Inc. for "Reconfigurable Parallel Optical Memory Interface". Sven also received funding from NSF-Career for "Generic Object Recognition in a Dynamic Environment." Naftaly Minsky received funding from NSF for "Law-governed Coordination and Access Control in Distributed Systems". Barbara Ryder received funding from Hewlett-Packard Corporation for "Virtual Function Resolution in C++: A Foundation for Compile-time Optimization"; this grant includes equipment that will be used as a departmental resource, namely a new HP color laserprinter and upgrades for equipment essential to our local Ethernet. Barbara also received NSF funding for two supplemental grants to her current NSF grant (with co-PI Dr. William Landi of Siemens Corporate Research), Software Capitalization and Research Experiences for Undergraduates. Given these awards, we still have over $11.6 million in pending proposals.
DIMACS Special Year on Logic and Algorithms
By Dr. Eric Allender and Maryann Holtsclaw
A star-studded cast of distinguished lecturers, over 45 visitors, four postdoctoral fellows, and over a dozen conferences and workshops: these figures give a hint of the amount of activity underway as part of the current DIMACS Special Year on Logic and Algorithms. The organizers of the Special Year are Eric Allender (CS, Rutgers), Bob Kurshan (AT&T Bell Labs), and Moshe Vardi (CS, Rice). Included in the planning are a Publicity Chair, a Steering Committee, and an Industrial Advisory Board.
The Special Year focuses attention on three areas of theoretical computer science that are currently making rapid advancement: Computer-Aided Verification, Finite-Model Theory, and Proof Complexity. Computer-Aided Verification draws on many subfields of mathematics to develop tools that aid designers in building more reliable hardware and software systems.
Since the first DIMACS workshop in this area in 1990, interest in this field has grown enormously both in academia and in industry. Finite-Model Theory studies the surprisingly close connections between logical expressiblity and computational complexity. Proof Complexity exploits recent advances in circuit complexity to discover the limits of formal proof systems; recently surprising connections have arisen between this field and cryptography.
Two unifying threads connecting these three areas is that all are intimately connected with mathematical logic, and all of these areas serve to bridge what has come to be something of a dichotomy in theoretical computer science. This dichotomy is best demonstrated by looking at the 1994 Handbook of Theoretical Computer Science. Volume A discusses algorithms and complexity, while Volume B treats formal models and semantics. Theoretical computer science in the United States is largely "Vol. A"-ish, while European theoretical computer science is largely "Vol. B"-ish. One goal of the DIMACS Special Year on Logic and Algorithms, which began in the summer of 1995, is to help bridge the gap between the two branches.
The Special Year began in August, 1995, with a series of three tutorials. Allender says he "was thrilled at the response we got from the community. We had 50Ñ70 people attending each week, including graduate students, postdocs, and people from industry, from all across the country and from abroad. We were fortunate to get great lecturers for each week. A particular highlight to note was that many of the people who are leaders in one area showed up for tutorials which related to other areas." Lecture materials from the tutorials are available on the DIMACS website.
One especially nice benefit of the Special Year for DCS faculty and students is the Distinguished Lecture Series. This series brings to Rutgers distinguished scientists who work in the Special Year focus areas. Each lecturer usually gives one "official" lecture and then visits for a while to work with the postdocs and visitors. Some of these lectures have been incorporated with the Rutgers Computer Science Department Colloquium series, organized this year by Sven Dickinson and Alex Borgida. The DLS lectures have had an excellent turnout (with lots of Rutgers and Princeton CS faculty and students in attendance). The feedback has also been quite positive. So far, most of the lecturers have scheduled their DLS lectures close to a workshop and have also talked at the workshop. The speakers in the series are: Ed Clarke, Stephen Cook, Ronald Fagin, Neil Immerman, Vaughan Pratt, Alexander Razborov, and Joel Spencer.
There have been seven workshops thus far in the special year: on (1) Verification and Control of Hybrid Systems, (2) Logic and Random Structures, (3) Finite Models and Descriptive Complexity, (4) The Satisfiability Problem: Theory and Applications, (5) Computational and Complexity Issues in Automated Verification, (6) Feasible Arithmetics and Length of Proofs, and (7) Controllers for Manufacturing and Automation: Specification, Synthesis, and Verification Issues.
Increased interaction among scholars in different subfields has already borne fruit. An excellent example is provided by the collaboration between two postdocs, Kousha Etessami and Thomas Wilke. One works on finite model theory and the other in computer-aided verification, and they have recently completed a paper in which the techniques of one area were applied to solve open problems in the other area, thus pointing the way for further progress in this direction.
Says Eric: "Although I don't really work in either of the three focus areas, I have learned that there are even deeper connections than I thought there were, between my interests in computational complexity and the Special Year topics. The Special Year provides a a great opportunity for many of us who have only been peripherally involved in these topics previously."
As a grand finale to the Special Year, DIMACS will host a Federated Logic Conference (FLC) which is being modelled after the successful Federated Computer Research Conference (FCRC). Four individual conferences (CADE, CAV, LICS, RTA) will participate to bring together a synergetic mega-conference that applies logic to computer science.
URL:
http://dimacs.rutgers.edu/SpecialYears/1995_1996/index.html
contains complete lists of workshops, DLS lectures, etc.
Observations and thoughts on Java
By Dr. Donald Smith
Java is an object-oriented programming language that after some initial experimentation looks very much like "Lisp in C clothing". It has primitives (e.g., int, float, etc.) which are the atoms of the language and objects (e.g., everything else) which are the structures. Java emphasizes the fact that it is "pointer free"; however, it is also "call by reference" (only primitives are "call by value"). It provides "first class" constructs (i.e., catch, throw) for exception handling and is designed to avoid some classic problems such as out-of-bounds indices and "buggy pointer" settings.
Java uses a "front-end/back-end" approach to compile Java source into "byte-code" which is then interpreted using Java's run time system. The Java run time system issues the necessary "native" instructions for the platform/OS on which the application is run. This approach makes Java less platform/OS dependent than most other languages but it comes at a performance price. Web browsers are being adapted to include Java interpreters and to recognize Java directives thus enabling the "downloading" and execution of Java program within the context of a browser.
Java seems to be targeted for "networked GUI" programming which is supported by an extensive set of class libraries handling everything from spawning a child (UNIX operating system calls) to programming pull down menus (X windows interfaces), to locating urls on the net, to managing multiple threads. The language, as opposed to the class library, is easy to use and once you adopt the "call by reference" perspective easy to debug. Its class libraries seem fairly complete but documentation is more suited for those intimately familiar with the language/environment than to those using it for the first time.
Based on my experiences, Java has the potential to be the lingua-franca of a CS curriculum. The language itself provide a clean framework for implementing fundamental representations/algorithms and the class libraries provide interfaces that implement many of the topics presented in upper level courses. A fully tested development/debugging environment won't be available for several months but given the current environment and interest I expect that Java will be "ready for prime time" by the fall of 1997.
A Farmer's Daughter in Our Midst
An Interview with Vasek Chvatal
The traveling salesman problem, or TSP for short, is easy to state: given a finite number of "cities" along with the cost of travel between each pair of them, find the cheapest way of visiting all the cities and returning to your starting point. The origins of the TSP are obscure. A charming book with the crisp title Der Handlungsreisende, wie er sein soll und was er zu thun hat, um Auftrage zu erhalten und eines glucklichen Erfolgs in seinen Geschiften gewisszu sein, published in 1831, touches on the subject but offers no advice beyond the observation that "By a proper choice and scheduling of the tour, one can often gain much time". In the 1920's, the mathematician/economist Karl Menger publicized the problem among his colleagues in Vienna; in the 1930's, it reappeared in the mathematical circles of Princeton; in the late 1940's, the mathematician Merill Flood popularized it among his colleagues at the RAND Corporation. Eventually, the TSP gained notoriety as the prototype of a hard problem in combinatorial optimization.
A number of TSP instances have been used for years as standard test problems for computer algorithms; in 1991, Gerhard Reinelt collected around a hundred of them, with sizes ranging from 17 to 85,900 cities, in a library called TSPLIB. At that time, thirty of the TSPLIB instances were unsolved; in the following four years, their number was reduced to ten by a team consisting of David Applegate, Bob Bixby, Bill Cook, and our own Vasek Chvatal. Their work has attracted considerable publicity. The New York Times ("Baffling Math Problem Slowly Yields", March 12, 1991) called them "the winning team" even before their first real success, which was the solution of a 3,038-city problem; this was reported in the New Scientist (27 June 1992) and in the special issue "1992 The Year In Science" of Discover (January 1993). The next rung on this ladder of fame is The Explorer. Here is our interview with Vasek.
Q: So who is the leader of the team?
A: Who was the leader of the Beatles?
Q: Surely you would not compare yourselves with them?
A: We can't sing quite as well, but our synergy and the fun we have together feel a lot like what theirs must have been.
Q: What is the largest problem you have solved?
A: People tend to forget that size is not important. At least in this context it is not. On the one hand, any idiot can solve a TSP instance with 50,000 cities if those cities are laid out on the circumference of a circle. On the other hand, there are ways of constructing fairly small TSP instances that will stump every computer code ever written. Including ours.
Q: Aren't you avoiding my question?
A: The largest problem that we have solved has 7,397 cities. The hardest problem, in a sense, that we have solved has 225 cities.
Q: A few years ago, Jon Bentley was giving talks with titles like "How to solve a TSP with a million cities". Compared to a million, your 7,397 seem puny. Have his million cities been placed on the circumference of a circle?
A: No, they have not. But his usage of the term "solve" differs from ours. What he and a number of others do is first find a reasonably good tour and then prove that its cost is at most, say, 102% of the best one. Given a typical million-city instance, you can do that within an hour. For us, this is only the beginning: we go on trying to prove that the tour we found actually is the best. This may or may not be the case, we may discover better tours during the process, but no matter what happens, we eventually end up with the best tour and a proof that it is the best one.
Q: How can you get such a proof without going through all the tours one by one?
A: By relying on a great wonderful seminal revolutionary breakthrough that Dantzig, Fulkerson, and Johnson made in 1954.
Q: What was that?
A: You know the joke about a man who is looking for his lost wallet under a streetlamp because that's where he can see rather than in the dark place where he actually dropped it? That is what Dantzig, Fulkerson, and Johnson proposed. Instead of solving the problem that they want to solve, they proposed solving a related problem that they can solve. Think of all the tours as points in a space of a very large dimension and then enclose all these points in a box with flat sides. Paradoxically, finding the cheapest of the infinite number of points in the box is easier than finding the cheapest of the finite number of tours. And if you get lucky, then the cheapest point in the box happens to be a tour. In which case you are done.
Q: And if you don't get lucky?
A: Then Dantzig, Fulkerson, and Johnson pick the streetlamp up and bring it a little closer to the place where the wallet was dropped. They make the box tighter. In the jargon, this is known as bringing in a "cutting plane". Think of a flock of white sheep and a single black sheep grazing with such serenity that they don't move at all. The white sheep are the tours, the black sheep is the cheapest point in your current box, and the cutting plane is a straight fence separating the black sheep from the rest of the flock. The success of the Dantzig-Fulkerson-Johnson method hinges on the ability to build that fence, to build it quickly, and to slam it really close to the white sheep.
Q: And you found ways of building better fences and of building fences faster?
A: Right.
Q: Can you describe briefly and in non-technical terms your theoretical results that enabled you to do that?
A: Yes. We have no new theoretical results on the TSP.
Q: So where do your innovations come from?
A: We aspired to emulate smart engineers. And here and there we avoided shooting ourselves in the foot.
Q: What does not shooting yourselves in the foot mean in this context?
A: Each time you build a fence and box the flock of white sheep in a smaller enclosure, the black sheep reacts by sneaking just an inch past this fence, so that it remains enlosed along with the rest of the flock. And then a new cycle begins: you have to build a new fence to separate the black sheep from the white. Traditionally, this new fence is built from scratch; one of our innovations is to try building it by tilting and shifting one of the old fences just a little. If the black sheep can fight dirty, then so can we. We call this trick "tightening" .
Q: Did tightening really help you that much?
A: When we got started, we had our eyes set on a really hard instance from the TSPLIB, a problem named pcb3038. We had armed ourselves with some sixty workstations working in paralel and written, as well as we could, a computer code based on previously published work of others. In January 1992, we began our first run on pcb3038. As we monitored our progress during a few weeks, it was becoming more and more obvious that, despite the considerable computing power at our disposal, we had no hope of ever solving the problem unless we came up with new tricks. In panic and despair, we did come up with a few and solved the problem by the end of April. One of these new tricks that got us over the pcb3038 hump was tightening.
Q: So your theoretical background was of no use to you?
A: I would not say that. True, we definitely did not want our theoretical background to get in the way of common sense. But once in a while this background helped. For instance, when we realized that a wondrous data structure, called a PQ-tree and invented by Booth and Lueker in the nineteen seventies for a completely different purpose, was just what the doctor ordered for dealing with the traveling salesman.
Q: Can you elaborate on that?
A: Imagine a salesman who covers New Jersey and Alaska. It stands to reason that he will make the journey between the two states only twice: once to go and once to return. In that sense, your data decompose into two nearly autonomous parts. The PQ-tree captures a hierarchical decomposition of this kind, wheels within wheels within wheels. We construct the tree by carefully inspecting the black sheep; then we use the tree again and again to build new fences.
Q: How does it feel, moving away from theory and into applications?
A: What applications?
Q: Well, aren't there salesmen who use software like yours to schedule their routes?
A: If there are, I don't know where they are hiding. Some problems in the TSPLIB come from drilling holes in printed circuit boards: there, the prescribed positions of the holes play the role of the cities and the drill plays the role of a salesman. Other problems in the TSPLIB come from X-ray crystallography: there, the prescribed angles of the snapshots play the role of the cities and the diffractometer plays the role of the salesman. But, at least as far as I know, these are the only two sources of the TSP instances that are linked to practical applications.
Q: So how about these two?
A: I have said earlier that you can get within 2% of the optimum in less than an hour even on fairly large TSP instances. If you were a PCB manufacturer, would you invest an extra six months of computing time to save $10 in production costs? And if you were a professor of physics, would you invest an extra six months of computing time to save fifteen minutes of your assistant's time?
Q: Does it bother you then that you have invested so much time into something irrelevant?
A: Does it bother IBM that it has invested so much time and so many resources into something as irrelevant as Deep Blue? The traveling salesman problem is to mathematical programming what chess is to artificial intelligence: thoroughly useless and fiercely competitive sport that serves as a testing ground of your techniques.
Q: Why did IBM do it?
A: If you want to find out, interview them. I don't know. One standard retort is that techniques developed for a useless purpose will sooner or later find a good use. Will the specialized hardware of Deep Blue lead the way to machines that will serve mankind in better ways than providing a sparring partner for Gary Kasparov? I don't know. What I do know is that the useless traveling salesman has many eminently useful cousins. And the new tricks in our bag are likely to help people working on these honest applications in solving harder instances of their problems.
Q: For example?
A: Making daily rounds of phone booths to collect the accumulated coins.
Q: But isn't this precisely the traveling salesman problem?
A: Almost, but not quite. To begin, you have not one salesman but several vehicles. And their workloads have to be more or less balanced. And this phone booth is in front of a fire hydrant, so you must park somewhere else to get its coins. And this other phone booth is on the wrong side of the street, so you will have to cross the street on foot, which will slow you down. And, and, and. . .and there are all those other ways in which the winsome mess of what we call real life encroaches on the austere simplicity of a mathematical abstraction.
Q: And you see the phone booth problem as an honest application?
A: A group of people at the Centre de recherche sur les transports in Montreal have been working on such problems for years. And working on them for clients who are actually paying them for the work. To me, this is the second most stringent acid test of what an honest application is.
Q: What is the most stringent acid test then?
A: Working for a client who pays you for the work and pays you not to publish your results, so that she can keep the edge over her competitors. In that sense, the most honest applications are precisely those that we never hear about.
Q: Changing the tack, what is your next step?
A: To finish the book. To finish the damn book. To finish the
f. . .
Q: Calm down. Now. There. It's OK. What book?
A: The book that will spell out all our innovations in detail.
Q: How far along are you?
A: We have a sixty-page DIMACS Technical Report from about a year ago. But that is just a small part of what we want to tell the general public about.
Q: What's stopping you?
A: The temptation to keep fiddling and improving is dangerous. Building those fences is like solving crossword puzzles. It gets addictive. No matter how much progress you make, you always have the nagging feeling that you still did not nail down a couple of hunches that could bring about another quantum leap. And even if we stopped today, cold turkey, the sheer volume of what we have already done is overwhelming. If we printed our code, it would run to well over a thousand pages.
Q: When do you expect to finish?
A: We have promised ourselves the end of this calendar year, come hell or high water. That is an absolute imperative. I will be off teaching in the fall and plan to spend a lot of time in Houston, where my three comrades-at-arms reside.
Q: What will be the title of the book?
A: That is the last of our worries. We want to concentrate on the substance first. Show me anybody preoccupied by the title of a project hardly off the ground and I will show you somebody who does not inspire much confidence.
Q: One last question. What is the secret of your success?
A: We have worked at it harder than anybody else.
Congratulations to Martin Farach, who has just won an Alfred P. Sloan Research Fellowship for 1996-98. This is a very competitive fellowship with only 10 awards each year in the area of computer science. The selection procedures are designed to identify those who show the most outstanding promise of making fundamental contributions to new knowledge. "Past recipients have stated that this early recognition of distinguished performance which the fellowships confer, after years of arduous preparation, was immensely encouraging and a stimulus to personal and career development." One additional note is that seventeen Sloan Fellows have won Nobel Prizes later in their careers, and hundreds have received other honors.
Faculty Achievements
Eric Allender was an invited lecturer at the Southeast Meeting of the American Mathematical Society in Greensboro, North Carolina, which was held November 17-18. He was an invited participant at the 1996 Workshop on Circuit Complexity, at McGill University's Bellairs Research Center, in Barbados, which was held February 25-March 3.
B.R. Badrinath (Badri) gave a keynote speech at the Mobility and visualization Workshop held in Rostoch, Germany, February 26-27, 1996.
Alex Borgida was a co-organizer of the 4th. International Workshop on Description Logics, held in Roma, Italy in June 1995. He was also appointed to the Editorial Board of ACM Transactions on Information Systems.
Sven Dickinson gave many talks since the last newsletter, which include a conference in Perth, Western Australia, Siemens Research Laboratory (Princeton, NJ), Yale University, and Columbia University. He also hosted several visitors at Rutgers, each of whom gave a talk. Sven received a grant from the AT&T Foundation, "Video Image Database Query by Image Context." He is serving on the committee for IEEE Conference on Computer Vision and Pattern Recognition (CVPR) at San Francisco, California, scheduled for June 1996. He is also serving on the committee for the 13th National Conference on Artificial Intelligence (AAAI) to be held in Portland, Oregon in August 1996, and is serving on the committee for the 13th International Conference on Pattern Recognition (ICPR) in Vienna in August 1996.
Prof. Ronen Feldman from the Computer Science Department at Bar-Ilan University visited Tomasz Imielinski and Haym Hirsh to collaborate with them on their data mining research.
Diane Souvaine serves on the Board of Governors of the National Science Foundation Science and Technology Center for the Computation and Visualization of Geometric Structures and participated in their semi-annual meetings. During the spring semester, she had two visitors jointly to DIMACS and to DCS. Thomas Shermer, Associate Professor of Computer Science at Simon Fraser University spent four months here working on rectangle visibility graphs. Rephael Wenger, Associate Professor of Computer Science at Ohio State University gave a talk on their joint research on constructing piecewise linear homeomorphisms applicable to cartography and to graphics.
William Steiger was on sabbatical during the Fall 95 semester visiting Polytechnic University in Barcelona where he gave a series of lectures to the faculty on Probabilistic Algorithms. He also visited the University of Newcastle in Cairns, Australia and the Math Institute of Hungarian Academy of Science and the Department of Applied Math at Charles University in Prague, Czech Republic. He is organizing a special session for the American Math Society regional meeting at Rider University scheduled for October 1996.
Dr. Imielinski
Recent Technical Reports
Spring, 1996
or contact:
Mary Hoffman (mth@cs.rutgers.edu)
Laboratory for Computer Science Research
Hill Center for the Mathematical Sciences
Busch Campus, Rutgers University
Piscataway, NJ 08855
(908) 445-2928 Fax: (908) 445-0537
To contact the editor, Maryann Holtsclaw, send email to holts@cs.rutgers.edu