Winter, 2000
Invitations to lunch on Fridays after CSE 521 (Algorithms).
Winter 2000 Workshop series chair: Zasha Weinberg
(Back to my home page).
So, you're all invited to this event, which will be after class tomorrow, thus around noon.
Much research in theoretical computer science has focussed on computability and on finding lower complexity bounds. Although important areas, I believe that these ignore a more fundamental issue in the theory of computation. Namely, that theoreticians need to eat. At the University of Washington, we hope to break open this traditionally-ignored, but exciting new field in theoretical computer science, thereby adding spice to the more meat and potatoes research areas. Researchers at other schools will salivate over the fruits of our labors, once they have had time to digest our results.
As a preliminary investigation into this exciting new research area, I propose that we discuss theory (or other topics) while having lunch on the Ave after 531 tomorrow. In this way, we will be able to evaluate the effective application of nutrition in the context of theoretical computer science.
A number of models for measurement of algorithmic complexity exist in Computer Science. In 531, we have discussed DTIME and NTIME. Recent gastronomic work at the University of Washington has introduced an interesting new complexity measure: LTIME.
Recall that LTIME(1) is the set of sets of problems that can be discussed during a single lunchtime. Many sets of problems are known to be LTIME(1)-Hard (informally, we say "Lunchtime-Hard").
One problem of theoretical importance is TOPICSUMMARY={<P> | P is a set of complete problem descriptions that will be discussed either this lunch or next lunch}. Obviously, it would take more than 1 lunchtime to discuss this problem, so it is Lunchtime-Hard. Another Lunchtime-Hard problem is WORTHWHILE={<P> | P is a problem that is worthwhile to discuss at lunch}. Indeed, WORTHWHILE is not known to be decidable or even recognizable (note: I'm ignoring the recent paper that states counter-intuitively that WORTHWHILE may be in LTIME(1) if no more than 1 student is involved).
A major challenging in LTIME-theory is the question of an analogue for NP-completeness that would allow us to quickly prove problems to be Lunchtime-Hard, and therefore not waste valuable lunchtimes considering them. Unfortunately, no form of "Lunchtime mapping reductions" exist - in fact it is difficult to speculate what this term might mean without a very strong background in punning theory. Certainly more punning theory than I have.
In order to gain an intuition into Lunchtime-Hard problems, I propose that we have lunch on the Ave, and try to discuss things. Hopefully, this practical experience will translate into novel strategies for the analysis of Lunchtime-Hard problems.
In the age of nutritional computer science, eating and talking are two tasks of significance to computer scientists. Traditional analysis methods of the efficiency of eating and talking have focussed on sequential, Turing eating machine models (named after Alain Turing, a famous eater).
An accident involving much coughing and spluttering uncovered two surprising results. The first result is that eating and talking can be performed concurrently. The second is that there is some dependencies exist, and performing these tasks simultaneously can, in some instances, cause discomfort in the form of coughing, and also make bystanders wonder if they should do something (see Heimlich et. al., 1976, "A Maneuver to Recover from Failed Parallel LTIME Computations").
This second result has made computer scientists reluctant to try this idea - an approach which may lead to parallel algorithms for Lunchtime problems. To prove the existance of practical parallel algorithms, I propose that we go to lunch on the Ave, and eat and talk. If we survive, we will have made a great contribution to the theory of parallel algorithms.
(Predoctoral researcher Isaac Kunen may also discuss his research in nutritional theory of computation. Isaac Kunen, who is regarded as one of the most gifted researchers in nutritional theory of computation, started eating at birth, and has been eating ever since. Later, when he started to study computer science, he set about the goal of applying his experience in eating to computer science)
In nutritional theory of computation, there are at least two popular space bounds. The first is STOMACH-SPACE, which refers to things that fit in ones stomach (note that, contrary to traditional terminology conventions, STOMACH-SPACE-completeness refers to a filling meal. Also, STOMACH-SPACE-hardness refers to languages that may require an antacid, or be otherwise difficult to digest. An example of such language, is anything that may require speakers to put their feet in their mouths).
The second space complexity measure is EYE-SPACE, which refers to things that appear to be in STOMACH-SPACE. Levin believed EYE-SPACE=STOMACH-SPACE. However, Cook set out to disprove him by creating a very long language (in the information theoretic sense). Levin was originally confident that he would be able to digest the complex language, but in the end proved unable to do so. Cook then triumphantly exclaimed "STOMACH-SPACE is a strict subset of EYE-SPACE with respect to you, Levin" (a more colloquial version of this statement is used by mothers around the world, thus showing the wide applicability of nutritional theory of computation. A corrolary to this is that you should never put something on your plate if you're not sure that you will eat it).
Levin then angrily stated that Cook would fit into Levin's STOMACH-SPACE if he wasn't careful. Cook pointed out that while this was true, the transformation would not be LTIME-1 computable, since a lower bound on Cook's weight at the time was 150 lbs while Levin could certainly not eat more than 2 pounds at a single sitting.
Excited by the realization that they had made an important contribution to nutritional theory of computation on the relationship between STOMACH-SPACE versus LTIME-1, they forgot their quarrel, and did not further investigate the EYE-SPACE vs. STOMACH-SPACE question (incidentally, their research into the STOMACH-SPACE vs. LTIME-1 question was unwittingly furthered by Karp, when Karp was mistakenly grilled, topped with a white wine lemon sauce and eaten in a trendy Seattle seafood restaurant, due to an understandable lexicographic mistake of edit distance 1.)
Since STOMACH-SPACE vs. EYE-SPACE is still an open question, I propose that we have lunch on the Ave, and proceed to gain evidence to help figure out the answer to this important question.
(This special workshop meet was proposed by Bart. Bart, who often goes by the name "Ralph", is a world-renowned expert in inverse-nutritional theoretic models, or as it's more commonly known, "Ralphing-Theory").
Recently, a number of the more practically-minded researchers have applied nondeterminism to everyday problems for students. As with most interesting things, this started with nutritional theory of computation, but has relevant applications elsewhere.
The original motivating question is the ACCEPTABLE-RESTAURANT problem. ACCEPTABLE-RESTAURANT={<R,S> | R is a restaurant that serves at least one dish that student S will eat}. Deterministically, the STOMACH-SPACE bound is linear in the number of dishes that the restaurant serves, since the student needs to eat each meal (1 stomach) and then evaluate it. So, this problem is in STOMACH-SPACE(n). Similarly, this problem is not known to be in LTIME(1).
Nondetermistically, of course, we can just guess a meal, and accept if it's okay (using U, the universal eating machine to simulate the student S). So, ACCEPTABLE-RESTAURANT is in NSTOMACH-SPACE(1).
There are two ideas we ignore here. The first is that Oracle for food. It has been shown (Zagats, 1998), that even if you have an oracle that can say whether or not S likes a particular cuisine (e.g. only vegetarian, or no pizza, etc), this problem remains as difficult, except in the obviously trivial cases. Intuitively, this explains why it's so difficult to pick a restaurant with a group of people, even when some members of a group know that they don't like certain restaurants, without having to try anything.
The other interesting idea, is The Savage's Theorem (Ugga-Bugga, 5967 BC). The Savage's Theorem involves a different model of eating still depicted in many cartoons. Specifically, Ugga-Bugga proposed a model in which the eater takes exactly one bite out of a large assortment of foods. Clearly, by taking sufficiently small bites, it is possible to sample all possible foods that a given restaurant has, using only 1 stomach. So, we see that, in this model, this problem is in STOMACH-SPACE(1). Observe that according to The Savage's Theorem, STOMACH-SPACE=NSTOMACH-SPACE.
If students could eat nondeterministically, we could go into a restaurant and not be upset if we ordered something bad, since with high probability, a nondeterministic copy of us ate something better. We can then enjoy our meal, secure in the knowledge that in another nutritional branch of eating, we liked it.
A similar idea of particular relevance to students is exam taking. In the "Journal of Psychology and Nutritional Theory of Computer Science", a recent study suggests that students would be much happier with exams if they could write them nondeterministically. The fundamental algorithm is: (1) Nondeterminstically guess the answers to every question (2) Have the exam graded (3) If the score is too low, then reject
Although most of us probably can't use nondeterminism in this way, I propose that after our 531 exam we compare how close to this ideal we were able to get, and also affirm that every one of us has an equivalent nondeterministic copy that got 100%. Congratulations in advance to everyone! So we can all be happy, and go to the Ave, and select a restaurant that has at least one meal that we'll all like.
First, I would like to welcome you all to the Winter 2000 offering of the Theoretical Lunch on the Ave workshop series. In this workshop, we discuss contemporary research in Nutritional Theory of Computation, while having lunch on the Ave. The Winter 2000 quarter's offering will focus on nutritional algorithms, since it's after 521. I'm planning on having it every Friday.
This week we will be covering the groundbreaking work on distributed soft drink machines that Prof. Anderson described on Monday's class. This work truly brought the field of distributed nutritional algorithms into the computer age. It also inspired the name of the prestigious nutritional algorithm conference, SODA, for "Symposium On Digestion Algorithms" (**NOT** "Symposium On Drinking Algorithms", as some wiseguy suggested.). Incidentally, the SODA homepage is at http://www.siam.org/meetings/da00/index.htm - although curiously, they've spelled "Digestion" wrong - an embarassing mistake I'm sure they'll correct soon.
We could try accessing remote soft drink machines, but this seems abstract. I feel that we need something more concrete in order to truly develop an understanding of this area. So, I propose that we all venture out to the Ave after 521, and purchase and consume food and drink.
Algorithms are commonly analyzed in terms of time and space. These are important attributes, but as nutrutional computer science shows, they are insufficient. Indeed much research in nutritional theory of computation has focussed on analyzing the nutritional content in algorithms.
Recent work at U. W. has considered a Quicksort-like algorithm for finding the convex hull of a set of points. The algorithm requires the use of two bugs (as is well-known to be common in nutritional algorithms). Although bugs are small, they are high in protein. Therefore, we say that this algorithm has a low nutritional content, but a high nutritional efficiency.
Recent interdisciplinary research at Cornell between their computer science and hotel & restaurant management programs is investigating how delicious nutritional algorithms are. According to their research, this convex hull algorithm is nutritious, but not very delicious. See "Deliciosity Models for Algorithms" (Journal of Culinary Arts, to be published).
An interesting nutritional data structure is the well-known red ant/black ant tree, which guarantees logarithmic time performance of insert, delete and find operations. This is a very significant result for nutritional algorithms, because its nutritional content is linear in the number of items in the tree, since at least one (red or black) ant is used for each item.
Unfortunately, tree data structures are not often discussed in nutritional theory of computation, after the whistleblowing paper, "Immoral Nutritional Content in Tree-Based Data Structures" (Christian Computer Science Monitor, 1989, 38:109-114). This paper points out, shockingly, that with all of the parents and children in trees, they have an extremely high nutritional efficeincy, but that cannibalism is clearly not something we should be thinking of as "good" - especially eating children. Therefore we don't typically discuss nutritional of tree-based data structures, and indeed this is why red ant/black ant trees have been called red/black trees since that paper (even though it's so obvious that the colors red and black are only logical when you think of ants. Of course, some researchers insist that these are called red licorice/black licorice trees.).
Note that some nutritional computer scientists feel comfortable with trees that only have roots or leaves, but no parents and certainly no children. With careful design, it is possible to derive sufficient algorithmic nutritional content from such trees.
Clearly, much work in algorithmic nutritional content has been done - and many results remain to be discovered and investigated. Therefore, I propose that we go out to have lunch on the Ave, and play with our food. Not only will this be fun, but hopefully we will uncover algorithms with high nutritional content by doing this.
In the early days of Nutritional Theoretical Computer Science, researchers restricted their location to fixed-position, or "static", nutritional search algorithms. Although of theoretical benefit, these algorithms are only applicable to stationary eaters, such as people who live at a cafe or people who are stuck on a particularly nutritious and frequently-stocked aisle in a supermarket. Indeed, many fundamental nutritional results were first conceived relative to bedridden eaters at hospitals who are fed intravenously.
Since the advent of mobile position, or "dynamic", programming techniques, real world problems are now solvable. For example, it is obvious that the analysis of our weekly journey to the Ave for food requires dynamic programming to simulate.
This week's seminar focusses on a critical early result in dynamic programming in nutritional search algorithms, which is particularly applicable to buffet or potluck dinners. The problem is for an eater to find the best meal at a table (a problem which requires a relatively small amount of dynamic movement). Essentially the idea is to do some bounded amount of work for each entree at the table (in computer science, we often refer to this as being for each "entry in the table". The origin of this mispelling of "entree" is unknown. Like many things in computer science, this is thought to be the contribution of Donald Kinoot, who can't even spell his own name correctly, although Edgar Dikestra must be regarded suspiciously.). Dynamic programming typically allows us to search for nutritious and/or delicious foods in time proportional to the number of entrees at the table.
In order to gain background in this important, but often neglected, concept in Nutritional Theory of Computation, I propose that we go to lunch on the Ave after 521, and eat, or otherwise process, entrees.
The field of Nutritional Theory of Computation was started many years ago, when researchers began to realize that theoreticians needed to eat. It is only relatively recently that researchers have fused this understanding with the knowledge that other groups need to each too. One such group is stooges.
In addition to being unjustly underfed, stooges have long been underrepresented in the Computational Sciences. Did you know that of all of the top ten graduate CS programs, not one of them has a stooge as a student or faculty (note that I'm not including certain people at MIT in this calculation)? And yet, there are many stooges around who have received no benefit from either the Nutritional or Computational Sciences.
Moreover, recently Professors Howard, Fine and Howard, at the University of Hollywood, were actually **denied tenure** for writing a sorting algorithm appropriate to stooges (as recounted in our algorithms text, which happened to be published by MIT). This aggressive control of academic freedom against a major segment of the population cannot continue. Nutritional Theory of Computation has the potential to positively impact everyone's lives. We at the University of Washington must realize the potential of our field.
I therefore strongly encourage everyone to join our workshop tomorrow, and eat lunch, while paying attention to the nutritional and algorithmic needs of stooges and also complete and utter stooges.
DAY CHANGE NOTICE: In honor of the 25th anniversary of the first greedy nutritional algorithms, we will greedily be moving our workshop series two days forward to Wednesday for this week only.
Proof that this greed is optimal: consider the workshop meeting days proposed by an optimal algorithm. Suppose that the optimal algorithm gives a different answer, and consider the earliest day about which they disagree. Then the first day about which they disagree would be this Wednesday. But, why would anyone wait until Friday, when they could eat two days earlier? Therefore, this cannot be the output of the optimal algorithm, since Wednesday is better. Therefore the greedy algorithm gives an optimal solution.
Next week will return to Friday (I have to attend the midterm in 326 on Friday).
Our guest speaker in this workshop will be noted University of Washington researcher Brett Allen. Brett discovered many novel applications of greedy algorithms to Nutritional Computation in a theoretical binge, late in 1996, going through theorem after theorem (always the most significant first). After some initial failure and a sense of overindulgence, this led to his groundbreaking paper published in IEEE Transactions on Nutritional Analysis and Machine Intelligence, entitled "Bulemic Techniques for Backtracking in Greedy Nutritional Algorithms". This has led to a wider applicability of greedy nutritional algorithms as a nutritional search heuristic.
Thanks to Brett for his ideas for this week's workshop (which follow).
We will retrace early steps in greedy nutritional algorithms, such as the correspondence between the Fractional Knapsack Problem and the Buffet Problem. An instance of the Buffet Problem is, of course, a set of dishes at a buffet, with associated nutrition or deliciousness factors. The problem is to determine the most delicious or nutritious mix of dishes. Clearly the most-nutritious/delicious-first algorithm solves this optimally (although the proof is very long and complex, and is divided into many case, some of which taste really bad).
Another problem is the Grocery Cart Problem: given a shopping cart S, and a food store F, what is the most nutritious/delicious assortment of foods in F that fit in S (assuming that parts of foods can be taken). The greedy algorithm of course avoids large, heavy cans of refried beans, in favor of expensive Swiss chocolate (deliciousness case) or rice and lentils with no sauce (nutritiousness case). Once again, this algorithm is optimal.
Recent work at the University of Washington has uncovered a concept called "Matroids". The term "Matroid" is a contraction of "Maalox" and "Altoids", and refers to the need for implementers of greedy nutritional algorithms to have plenty of antacids and breath fresheners on hand. Given a matroid, we can be confident in applying a greedy nutritional algorithm.
Since these ideas may seem too abstract, I propose that we go to lunch on the Ave, and gluttonously consume the best thing available at all times. With this strategy (and with sufficient quantities of Matroids), we can optimally reach an understanding of Greedy Nutritional Algorithms.
For most of its history, the limelight of nutritional theory of computation has focussed on search and consumption problems. Indeed one of the earliest nutritional computation results, which was in food consumption, was discovered prior to the advent of computers - a remarkable application of grpahs by a 6th grade elementary school teacher. I am, of course, referring to the Food Graph (re-named the Food Chain, to be relevant to bicycling enthusiasts, and business majors studying franchises, then later renamed the Food Web to be relevant to the internet.)
A recent article in Nutritional Theory of Computation Today reveals that out of 47 Chocolate Turing awards (the highest honor in Nutritional Theory of Computation), only 2 were awarded for nutritional production algorithms. With the creation of a Computational Nutrition program here at the University of Washington, we are duty-bound to redress this imbalance.
One well-known result in this area is a contribution to growing fruit. In this problem, we are given a set of apples and their locations, and we wish to find a tree that could grow those apples. Obviously the tree must connect all apples, but we would also like to have as little wood used as possible, because this detracts from the nutrients going to the apples. Most Minimum Spanning Apple Tree algorithms are based on the fact that, if we cut any branch, we expect that branch to be the least-woody possible branch connecting the two separated apple-sets (note: clearly we would not want to cut the apple tree during the growing season).
In a well-known, but often distorted, story, former US president George Washington discovered this theorem by cutting a cherry tree. If he had not later decided to pursue politics and recast this story as evidence of his moral rectitude, this nutritional result may have been known much earlier.
In another problem, we are given a set of procedures, nutrients, and seeds, and we wish to know the most profitable path from those raw materials, to marketable food products. Most algorithms to solve this problem systematically find optimal sub-products until best products can be known. One innovative approach is to optimal results by routing water resources effectives. This approach, pioneered by an obscure nutritionist known as "Edgar the Dike-ster", seeks to greedily pick apparently optimal combinations of raw materials, and direct as much water to them as necessary to make them a success.
What better way to understand nutritional production algorithms than to dedicate time to digesting the results of these algorithms? Clearly our best next step is to go to the Ave for lunch, and begin to sink our teeth into this topic.
Last week we discussed the oft-neglected nutritional production algorithms. This week we will discuss the newer field of algorithms for nutritional distribution. Of particular interest is high-performance distribution algorithms. In retrospect, it's obvious that the attention to nutritional search and consumption algorithms and the (insufficient) attention to nutritional production algorithms is useless, if distribution algorithms are too slow. This essentially limits the capacity of nutritional transference, curtailing the maximal flow of nutrients.
By cruelly curtailing the maximal flow of nutrients, we are forcing nutritional providing protocols to cut portions of foods into ever-smaller pieces, in order to feed the same number of people. This over-cutting is a direct result of insufficient high-performance nutritionally distributed algorithms, and causes unsatisfying meals worldwide - even on the Ave. It is clear that minimizing the cutting of portions is equivalent to maximizing the flow of nutrients (this so-called "Max-flow min-cut" principle was evangilized by a radical 60's nutritional computer scientist by the name of Fulkerson. Fulkerson would furiously drive as many nutrients as possible to their destination in the rusted Ford he owned, to improve what he saw as a desperate situation. This is often disparagingly referred to as the "Ford-Fulkerson Method").
A major problem in this area is the transportation of nutrients accross known transportation channels. A non-obvious complication is that not only might we have nutritional constraints on transportation channels (e.g. by weight), but a deliciosity analysis is also necessary (q.v. "Delicious Constraints in Transportation of Nutrients with Hungry Agents", Communications of the Delicious Food Producers, 139 (3): 197-205.). Some foods may be too delicious for the transporter to resist, thereby constraining the flow of such foods. This makes the problem much more challenging than the relatively low-brow versions of this problem found in traditional computer science areas.
As is well known, a basic solution is to transport some nutrients, and then consider if there are more nutrients that can be routed. After routing some nutrients, we merely create a model of augmented nutritional transportation channels, and solve the augmented model. Note that many Organic CS researchers object to "augmenting" nutrients in this way, and argue that this solution does not accurately model notions of healthfulness, and are therefore not sustainable algorithms.
In order to understand this debate, and gain insight into the efficiency, efficacy and sustainability of high-performance nutritionally distributed algorithms, I propose that we go to the Ave and have lunch. In addition to providing key insights into this vital research area, I hope that this will be both delicious and nutritious.
Unfortunately, I have to show up to CSE 326 lecture tomorrow, so I can't come to the lunch on the Ave. However, in the spirit of maximal matchings, I believe that an optimal amount of nutrition would be consumed if other people were to have lunch without me. Therefore, the Theoretical Lunch on the Ave will continue.
Earlier we discussed the buffet problem, wherein an individual wishes to determine their optimal selection, given a set of available dishes. We now consider this problem with a group of individuals, with known food preferences. The food preferences imply a set of edible foods per individual, which may be different for each person. We wish to maximize the number of people that are fed and the number of dishes that are eaten.
We can transform this into a nutritional distribution problem (aka max flow of nutrients), which we discussed last week. We consider a nutrition producer that creates all dishes. The nutrients are distributed to the buffet eaters. The distribution channels are the connections between eaters, and buffet items they are willing to eat. Then the problem can be restated as follows: how can we distribute the nutrients to make the eaters as heavy as possible? So, clearly a reasonably efficient way of solving this version of the Maximal Buffet Problem is to transform it into a nutritional distribution problem, and solve that. Note that this also underscores how important nutritional distribution algorithms are.
In order to understand this reduction and to be able to apply it to other problems, I suggest that as many of us as possible match themselves up with food items on the Ave.
We've been discussing many critical research areas in Nutritional Theory of Computation, and making significant contributions to this field - every week. So, I felt that perhaps many of us might want a break from our usual nutritional studies. Therefore, I propose that - instead of the usual workshop - we just go to the Ave and have lunch.
Last quarter we discussed the computationally hard Restaurant Selection problem. This result means that there is no efficient algorithm to pick a restaurant that satisfies the culinary tastes of an arbitrary set of people, unless N=1.
We might be tempted to simply give up on this problem. However, starvation avoidance is so important, that perhaps we can accept a nearly-optimal solution and eat something (for another take on starvation avoidance, see any decent textbook on Nutritional Operating Systems).
There are a number of heuristics for this problem, but no tight bounds. Some heuristics are to ignore people who don't express any preference, to have some people glumly accept that they won't be happy, and to argue until people get tired of not liking certain foods and begin to believe that they like whatever as long as we go somewhere.
Unfortunately, even with these promising heuristics, it's still possible to find a restaurant that even everyone hates. Interestingly, there are provably good _amortized_ approximation algorithms. The most common are (1) never go to a place that many people didn't like, and (2) maintain a list of acceptable places and disproportionally visit those places. With option #2, we can - over time - attain a bound of arbitrarily close to 1.
This is such a fundamental problem that I'm sure everyone is familiar with reasonable solutions. Nonetheless, I feel it would be very beneficial for us to go to Ave, select a restaurant, and each lunch there. So, I propose that we do just that.
P.S.: by now, I'm sure that everyone is well familiar with the groundbreaking ideas developed in Nutritional Theory of Computation which other fields subsequently adopt. Still, I think it's worth mentioning that nutritional approximation algorithm theory can be applied to exam taking. Thus our Nutritional Algorithm workshop this week is very timely, considering that we have a final exam coming up.
The fortunate fact is that approximation algorithms in exam taking with tight bounds are reasonably easy to achieve. In fact, I'm quite confident that everyone who writes the exam will attain a 1/4.0-approximation to the optimal score on the exam. This attests to the phenomenal strength of U.W. and its students in Nutritional Theory of Computation. Congratulations to everyone in advance for their impressive constant approximation bound!
We have spent a quarter discussing Nutritional Algorithms; now it's time to evaluate what knowledge the participants have in this field, with a final exam. This will be an oral exam, involving putting nutrients in your mouths.
Since probably most people will want to have lunch before 2:30, and also since we can't have the exam be a substantial as the weekly meetings throughout the quarter, I propose that we find a cafe wherein some people can eat lunch, while others can just have drinks.
Attendence is mandatory. Those who do not attend - even those who have lame excuses like Bart - will be assumed to know nothing of Nutritional Theory of Computation. Remember that this is a notable area of strength at U.W., so I'm sure that quals committee won't look kindly on students who irresponsibly focus on 521 at the expense of their Nutritional studies. So come on and eat, drink and socialize.
Copyright (c) 1999-2000, Zasha Weinberg.