Wednesday, April 30, 2008

AAAC in Hong Kong

I just came back from an all too short trip to Hong Kong for the first annual meeting of the new Asian Association for Algorithms and Computation. The AAAC would like to become the Asian version of SIGACT and EATCS. The conference was a good start but dominated by the Japanese and needs in future to draw researchers from across Asia. I went as a speaker, but also as a supporter as I would love to see theory grow around the world and while East Asia has produced a few great researchers, it has not even come close to reaching its potential.

This was my first trip to Hong Kong and the three dimensionality of central Hong Kong is quite striking with many tall buildings built on various points on a hill and in some cases seemingly on top of other buildings. To get from my hotel to the conference at Hong Kong University, I took a series of outdoor escalators, crossed a bridge and then an elevator followed by some stairs. You need to keep track of elevation to get around that city.

I had never been to China. Did this trip to Hong Kong count? Technically yes, since 1997 Hong Kong is officially a Special Administrative Region of China and shares much of the culture and cuisine of China. But a different currency, visa requirements and economic structure makes it seem like a separate country. Someday I will get to mainland China and make this point moot.

Tuesday, April 29, 2008

Should Mahaney's theorem be taught in a complexity grad course for non-theorists?

Today we discuss another theorem in terms of should it be taught in a basic complexity course (taken mostly by non-theorists) (There was an earlier blog about this for PARITY ¬in AC0.)

Why is SAT &lem S, S spare , implies P=NP interesting? important? (Henceforth Mahaney's thm.) I'm not trying to convince you that it is, I am asking if it is. Here are some thoughts.
  1. The original motivation is the Berman-Hartmanis conjecture that all NP complete sets are poly-isom. Mahaney's thm is a consequence of the conjecture. One could do the BH paper and show why it is plausible and then give this result. But is it worth it?
  2. The result is a stepping stone to Karp-Lipton's result that SAT &leT S, S sparse, implies PH collapses. This begs the question- why is KL important? Because it is a stepping stone for Yap's result that SAT &isin coNP/poly implies PH collapses. And why is that important? Because it is used in the proof that if GI is NPC then PH collapses. This is good enough for me- evidence that a natural problem is NOT NPC-- surely worth knowing. But do we need to present Mahaney's result to get to Yap's result?
  3. Should point out that KL is also interesting because it is a link between uniform and non-uniform complexity. But again, perhaps we could do that without Mahaney's result.
  4. The techniques used to prove Mahaney's result are interesting and lead to other theorems of interest. Like what? Well, ur, the Ogiwara-Watnabe result which replaces &lem with &lebtt. And the result of Lozano that generalizes this to other classes like MODaSAT (number of assignments is &equiv 0 mod a). Why are these of interest? I have an intuitive sense that they are, but I can't even really say why theorists find it interesting. For that matter, do theorists find it interesting? (This was discussed in this blog entry, though the discussion was derailed by someone asking an off-topic question.)

Monday, April 28, 2008

What would the best base be?

(A partial continuation of the last post).

We use Base 10 because we have 10 fingers on our hands. But if we could pick a base based on what is better mathematically or computationally or some objective criteria, what would it be?
  1. When I was young I thought that if we had always used base 8 then computer science would be easier and computers would be faster. While partially true, not MUCH easier or MUCH faster.
  2. In 1934 there was an article with title An Excursion in Numbers, by F. Emerson Andrews, in The Atlantic Monthly urged abanding Base 10 for Base 12. (Yes- the The Atlantic Monthly not The American Mathematically Monthly. I'm surprised too.) There are some advantages- 12 is divisible by 2,3,4,6 and since 12 is used for eggs there may have been some reason for it. The Duodecimal Society advocates changing to base 12. They have (or perhaps had - I could not find it on the web) a newsletter The Duodecimal Bulletin, which is translated into one other languauge and has the title Ekskurso en Nombroj. I'll let you figure out what language that is. (ACK- this info comes from Mathematical Cranks by Underwood Dudley.)
  3. Picture that you want to represent every number between 1 and n. Lets say its in base 10. In an adding machine (whats that?) you would have log10 n columns and each one of them has 10 keys. So the total number of keys you need is 10log10n. More generally, if its base b then you need blogb keys. What value of b minimizes this? The answer is e. Since we can't use e for normal counting, this does indicate that 2 or 3 would be best. Since 2 is also good for computer science, my vote goes to using base 2.
  4. To end where we began this- I wonder how Obama, Hillary, and McCain would vote?

Friday, April 25, 2008

If we had 12 fingers on our hands then Obama would be the nominee

dits have said the following (paraphrased):
Hillary needs to win the PA primary by double-digit to get back in this race. (She ended up with something like a 9.2 or 9.4 advantage depending on who you ask. She rounds up to 10, he rounds down to 9.)
What if we had 12 fingers on our hands? Then we would use a base 12 system and she would not be close to the magical ``double-digit lead.'' Would she drop out? No, but the win could not be spinned as dramatically.

Pundits and others do not realize that base 10 is arbitrary and is not connected to anything interesting mathematically or politically.

Hippies used to say Don't trust anyone over 30 without realizing that they had given in to the establishments insistence that base 10 rules us.

Its been said 50 is the new 40. Why 50 and 40? Should be 49 is the new 36 since squares are ind of base. (Is 100 is the new 81?)

The Beatles had it right with their song When I'm 64.

A while back this blog noted its 1000th entry. Mistake- we should have noted its 1024th entry.

Thursday, April 24, 2008

The Life of the Party

Being a Math/CS professor is generally the kiss of death at any large social event. But thanks to the movie 21, for one short moment, I was the center of attention.

I haven't seen the movie yet, but apparently there is a scene where an MIT Professor (played by Kevin Spacey) uses the Monty Hall problem to help choose his blackjack team. So I helped explain why it makes sense to switch doors.

The movie had more math, basically simple card counting techniques to give an advantage at the blackjack tables. Any movie like this that glorifies mathematicians help our community, even if they just use math to win money at casinos.

In fact, our family was invited to another party earlier this week where the guest of honor was one of the members of the original blackjack team that the movie was based on. Being a mathematician is cool again, at least for a couple of weeks.

Wednesday, April 23, 2008

What Happened to the Indians?

I lamented to some Indian colleagues that we had no IIT applicants to the CS theory graduate program at Northwestern. Chicago and many other US institutions drew many of their best students from the Indian Institute of Technology campuses over the years.

I suggested that Northwestern was not yet on the theory map, at least in India. Likely true, but in addition the number of IIT CS majors going to the US for Ph.D.s has dropped by about two-thirds over the last couple of years. The culprit: Large, mostly US, banks are hiring the top graduates at salaries extremely high by Indian standards to work in their India offices. We had seen a smaller drop earlier with the software industry hiring but the software doesn't pay nearly as well as the banking industry. The Hindu writes about this trend.

I'm happy for India's success but worry about the impact on US science and CS theory in particular. You don't have to look far at the best theorists to see a large number of Indians, mostly IIT alumni. Imagine if most of them ended up as bankers in Mumbai. What a loss!

Back in the US, where do we get our graduate students from now? The Israeli's have long since stopped coming here, now that they can get quality Ph.D.s in Israel. Most Europeans also stay in Europe. We've also seen a drop in Chinese applicants. The US needs to start developing new sources for foreign students, or maybe, just maybe, find a way to attract more Americans.

Tuesday, April 22, 2008

Laptops in classroom and lectures

More students are bringing laptops to class. More faculty are bringing laptops to talks. Is this good, bad, or ugly? Some points
  1. I was sitting in on the best teacher in my dept (Dave Mount) teaching an elective course (so students there wanted to be there) on how to write video games (a topic of interest). Many of the students in the class were using their laptops to surf the net.
  2. Another professor has banned laptops from his class. If a student claims they are taking notes on it, as 5 did, then he demands that they email him the notes (only 1 took him on it).
  3. Is this any different than students doodling or gazing out the window or other ways to distract themselves?
  4. Since attendence is not mandatory, why insist that they not have laptops? I am not asking this rhetorically--- I am tempted by the idea of banning laptops also.
  5. Professors at talks also bring their laptops. We have not developed a culture where this is considered rude. Not clear why we haven't.
  6. Are today's youth better at multi-tasking so that they can do two or more things at once, like surf the web and listen to a talk? Again, I ask this non-rhetorically.
  7. I have no strong opinons here, but I want you to write your so I can borrow them next time I am feeling argumentative.

Monday, April 21, 2008

Ketan Mulmuley Responds

Someone pointed out to me your post where it is stated that, according to me, any approach to separate P from NP must go through GCT. This is not what I think or said. One cannot really say that GCT is the only way to separate P from NP or that any approach must go through it. Indeed as the article (On GCT, P vs. NP and the Flip I: A High Level View)—henceforth referred to as GCTflip—which describes the basic plan of GCT, clearly states: GCT is a plausible approach to the P vs. NP problem. But as it also explains there are good mathematical reasons to believe why it may well be among the "easiest" approaches to the P vs. NP problem.

One such argument—the zero information loss argument—was presented by K.V. in his talk. According to it, any approach to separate the permanent from the determinant in characteristic zero must understand, in one way or the other, the fundamental century-old problem in representation theory, called the Kronecker problem, or rather its decision form. (though this understanding may be expressed in that approach in a completely different language). This is what I repeated during the lunch after that talk, and this is perhaps what the post is referring to.

The only known special case of this problem which is completely solved is the Littlewood-Richardson problem. The most transparent proof of this (which also provides far deeper information regarding this problem needed in GCT, unlike other proofs) goes through the theory quantum groups, and the only known good criterion for the decision version requires the saturation theorem for Littlewood-Richardson coefficients. GCT strives to lift this most transparent proof to the Kronecker problem, and more generally to the generalized subgroup restriction problem (and its decision form), which is needed in the context of the P vs. NP problem in characteristic zero.

All this is explained in detail in the article GCTflip mentioned above. It does not assume any background in algebraic geometry or representation theory. It has been read by the computer science graduate students here. They had no problem reading it. But it does need a month. It is my hope that you would spare a month sometime for the sake of the P vs. NP problem.

Friday, April 18, 2008

Facebook and Forums and Feeds, oh my!

Facebook and Forums and Feeds, oh my. (Upon seeing Lance Fortnow's facebook post Bill Gasarch asked Evan Golub, who does research in Human-Computer Interaction and educational technologies (though his Ph.D. involved Expander Graphs) to do a guest post on facebook. This is that post.)

Lance recently wrote wondering how he would use a Facebook page with his course. I should start by saying that although I have a Facebook account, I don't really use it - I signed up for it to look around and to decide whether I wanted to start using it and haven't decided on "yes" yet.

In thinking about Lance's question, my first question was whether he would create a Facebook group for his class, or create an actual user and name it after his class. Depending on what notification options work on a group -vs- work on a user might guide this decision. For example, if one of these allows other Facebook users to receive a notification when the wall is written on, then it might become the better choice.

My next thoughts on this relate to Internet-based course management ideas that could be done via other technologies, but might be possible using Facebook instead. So, what could Lance do with a Facebook account/group for his class that could already be done with forums? He could provide a way for students in the class to:

  • ...get in touch with each other and find out about each other outside of the classroom
  • ...from study groups during the semester
  • links to useful resources related to class topics
  • Next, what could Lance do with a Facebook account/group for his class that could be already be done with an RSS feed? He could have a way to let students know when he has:

  • ...posted a new assignment
  • ...posted additional notes
  • ...updated the grades posted online
  • Assuming that anything that could be done via Facebook could also be done using forums or feeds or other technologies, why use Facebook rather than web forums or RSS feeds or other tools at our disposal? To borrow an idea from Alexandre Auguste Ledru-Rollin, one reason might be "because that's where the students are, so if we want to guide them, that's where we should be".

    However, the above is more the reason why I have not used Facebook with my courses yet. I see Facebook as a place where students go to socialize, not to do classwork. I recall reading when I was a student that you shouldn't do homework in bed or your brain might have more trouble turning off thoughts of schoolwork when you are trying to go to sleep. I don't know whether there is research to back up this perception that I picked up somewhere along the way, but if so, then perhaps we should ask whether it would be better to keep our courses off of Facebook (unless we are teaching a course that covers social networking as a topic). If this is meant to be a social space for students, would we be infringing upon this by bringing our courses there?

    As an (essentially) non-Facebook user, there might be some uses that would be unique to Facebook (or similar social networking sites) of which I am unaware. This "reply" to Lance (prompted by Bill) is meant more to open what I see as a central question raised by Lance's question of "what to put up there" (see his original post).

    Thursday, April 17, 2008

    My First Grand Student

    Today I am in Madison, Wisconsin where Scott Diehl has just defended his thesis. Scott's advisor, Dieter van Melkebeek, was my advisee at Chicago, making Scott my first Grand Student. I've waited a long time for a grand student, my first student Carsten Lund graduated back in 1991. But Carsten went to AT&T and my next student Lide Li also went into industry. But now with three students in academia (including Sophie Laplante at Paris-Sud and Rahul Santhanam going to Edinburgh), Scott will be the first of many.

    Actually what I really want is an infinite tree below me, but König's lemma says I needed a grand student first.

    Diehl's thesis is on time-space tradeoff's for satisfiability. I worked in this area about a decade ago then extended some of that work with Dieter who then worked on it with Scott, a passing of knowledge from generation to generation. The symbolism is so, umm, symbolic.

    So as not to slight the other members of the family: Scott's academic aunt, my most recent student Varsha Dani, graduated last quarter. And just two days ago I was back at U. Chicago for Sourav Chakraborty's successful defense (Sourav is a student of Babai).

    It's so nice to see the young ones grow up.

    Wednesday, April 16, 2008

    The Revenge of Parallelism

    Now that I sit in an engineering school, I see more applied recruiting talks. Many of them have a variation of this picture.

    This picture represents the future of Moore's law. The number of transistors in our computers continue to grow exponentially but the clock speed is levelling off. What do we use this new transistors for? To make multiple CPUs on a single integrated circuit, known as a multicore machine. New chips from Intel have 2 or 4 cores and the number of cores is expected to double every couple of years.

    Multicores present interesting challenges for computer science, for example compiler researchers are trying to make the best use of multiple CPUs without having the user explicitly use parallelism in their code.

    Our theory community hasn't really responded to this new computing model (nothing much in STOC and FOCS, though SPAA 2008 has a special track on the topic). Now the theory isn't that interesting if you have two or four cores, but what happens when we have millions on a chip? Do our old parallel models like the PRAM apply to multicore machines? There are hints of this in comments to my PRAM post three years ago. Or perhaps we need new models.

    We study computational complexity in computer science instead of mathematics because, at least some level, our models reflect real-world computing paradigms. As those paradigms change, Complexity quickly adapts (random and quantum for instance). Should multicore machines be another one of these paradigm changes that drives our theory?

    Tuesday, April 15, 2008

    Complexity of Income Tax

    Its INCOME TAX TIME in the USA. Which country has the most complicated Income Tax System? How can you measure the complexity of an Income Tax System? Some factors:
    • The number of pages in the tax code.
    • The length of the form you hand in.
    • The percent of tax payers who hire someone to do their taxes for them. (This may also be affected by the computer literacy of the country.)
    • The number of changes in the tax law from year to year.
    • The minimum amount you have to declare. (Do I need to declare my 25 cents that I won from Justin, my 8 year old great nephew, on a math game? Can he use the -25 cents as a deduction? He can use it to offset gambling gains.
    • The number of items you can deduct.

    There is a problem with all of these measures. What if the tax code is 100,000 pages long but 99.9% of the people only need the first page? One solution is to do some sort of weighted sum.

    Deciding whether a tax system is complicated is a hard problem; however, deciding if its fair is a much harder problem.

    Monday, April 14, 2008

    Eight (yes eight) math problems worth $1,000,000

    Most readers of this blog know of the Millenium Problems. There are seven of them (which I list below) and solving any of them will get you $1,000,000. (The website above has the following bug/feature- when you go to it you get to a description of ONE of the problems with the entire list on the right-hand side. It seems random which problem you get.)
    1. Birch and Swinnerton-Dyer Conjecture
    2. Hodge Conjecture
    3. Navier-Strokes Equations
    4. P vs NP
    5. Poincare Conjecture (seems to have already been solved)
    6. Riemann Hypothesis
    7. Yang-Mills Theory
    There is ANOTHER problem that is worth $1,000,000. There is a novel entitled Uncle Petros and Goldbach's Conjecture. Its about a mathematican who is obsessed with Goldbach's conjecture. For publicity, the publishers are offering $1,000,000 for a solution to Goldbach's conjecture. Did this publicity stunt work? The book is selling used for $3.48 on amazon, and I borrowed it from a friend. On the other hand, it is very doubtful they will have to pay it anytime soon.

    Its a pretty good book- the math and mathematicians are spot-on. Its a good airplane book, say the kind of book you can read on the airplane on your way to Conf on Computational Complexity 2008.

    Friday, April 11, 2008

    How to Prove NP Different from P

    At TTI yesterday, K. V. Subrahmanyam gave a talk giving one of the better overviews of Ketan Mulmuley's Geometric Complexity Theory approach to separating complexity classes. This approach reduces various problems including P ≠ NP to hard problems in algebraic geometry.

    Afterwards at lunch, Ketan made it clear that he believes

    1. GCT will eventually lead to proving P versus NP. In fact, any proof that NP is different than P must go via GCT.
    2. Such a proof will not happen in my lifetime.
    Ketan argued that any complexity theorist who really cares about P v. NP (such as myself) should spend a full month understanding this approach as it will give them a glimpse into how we will eventually separate P from NP. Given my limited knowledge of representation theory and algebraic geometry, I suspect it would take me much more than a month and doubtful that I could ever push the theory any further. Also while knowing the resolution of P v. NP is very important, knowing the details of the proof, especially if it requires deep and complex mathematics, is not nearly as important. I was excited to see Fermat's Last Theorem resolved in my lifetime but I have no desire to actually understand the proof.

    Ketan is not even giving me that opportunity. Consider a huge mountain and you want to reach the mountaintop. Ketan comes along and says he'll teach you how to create the tools needed to climb the mountain. It will take a hard month of study and actually these tools aren't good enough to climb the mountain. They need to be improved and these improvements won't happen in your lifetime. But don't you want to learn how others will climb the mountain centuries from now?

    If you want to spend the month, go here and start reading. Let me know when you've been enlightened.

    Thursday, April 10, 2008

    Applying Math to politics

    In a prior post I tried to apply math to the problem of who to ask for a ride home. Todays post is about someone elses attempt to apply math to politics.

    This is from This is from New York Magazine, Feb 4, 2008. (before McCain had clinched the Rep. Primary). The article was called Anatomy of a Freak Show by Kurt Andersen. Here is his formula and his justification.

    (Romney + Huckabee)/3 + .01McCain + sqrt(Guilliani) = Bush

    1. Romney and Bush were both Businessmen, though Bush was a pathetic one, while Romney was a good one.
    2. Huckabee and Bush are both Evangelical Christians, though Bush is a pathetic one, while Huckabee is a good one.
    3. McCain and Bush were both party boys in college who later became figher pilots, though Bush avoided real combat.
    4. Guilliani and Bush both have a chip on their shoulder.
    Is the formula true? Depends how you define true, but I'll say its not even wrong.

    Wednesday, April 09, 2008

    ICALP and EC

    A busy conference day yesterday. In the morning I had two papers rejected by ICALP but later buffered by two papers accepted into Electronic Commerce. I'll take 2 for 4 any day.

    The list of accepted papers for ICALP Track A has been posted. The EC list isn't out yet.

    For ICALP, one my papers was rejected because the proof didn't seem hard enough and the other for having too many theorems.

    Thus, while I do find that the results are interesting, reading the paper (including the appendix), I am not convinced that it is possible to present the results in a satisfying way within the page constraints. There simply seems to be too many results included for this to be feasible.
    I need to listen to my own advice.

    Update 4/10: EC accepted papers here.

    Tuesday, April 08, 2008

    Applying Math to getting rides

    Here is an attempt, to apply math to the real real world and what the limits are.

    I do not drive so I sometimes need a ride home (about once every two weeks). SO, who to ask? If giving me a ride home adds alot of time to their normal ride, then I would ask them less often. How to quanify this?
    If person x has to go i minutes out of his way, then I will ask person x at most once every i weeks.
    But here are problems with the formula:
    1. Let say that person x normally takes 5 minutes to get home, but giving me a ride home will add 10 minutes, yielding a 15 minute ride. Let say that person y normally takes 30 minutes to get home, but giving me a ride home will add 10 minutes, yielding a 40 minute ride. Person x may view giving me a ride as tripling the time home, while Person y views it as adding just 10 minutes. On the other hand, Person y already has a 30 minute ride and may not want to add anything to it.
    2. How much do they like my company? Is i minutes with Bill seem like log i minutes, &radic i , i/2, i, 2i, or i2, minutes (past i2 and I won't ever ask for a ride). (OFF TOPIC QUESTION- how do you do a good sqrt symbol in html? Whats above is the best I could find.)
    3. Ditto for how much I like their company.
    4. What if when giving me a ride home they pass by their own house and have to backtrack? Even if its not too many extra minutes it has a psycological effect.
    5. How complicated is x's life? If x has to drop one of their kids at soccer practice, and one at Piano lessons then fitting a ride for me into it may be complicated even if it is not that many minutes out of the way.
    6. Giving someone a ride TOO school is far worse then giving someone a ride FROM school, since FROM school both parties can be more flexible.

    Monday, April 07, 2008

    A Web 1.0 Guy in a Web 2.0 World

    I consider myself reasonably Internet savvy. I've been using email since the early 80's, have been doing research via IM, I write a blog and have done some podcasts. But when it comes to social networking I find myself on the outside, in the wrong generation. It's not merely that I don't make much use of social networks, I just don't get it. I've tried out Facebook, Myspace and Linkedin, have loads of "friends" and haven't gotten much use out of them. I've asked younger people why they spend so much time on Facebook and what they get out of it. They tell me plenty and yet I'm still missing some crucial understanding of what makes these networks so popular. Perhaps like trying to understand why a roller coaster is fun without actually taking a ride.

    Someone told me that if I started a Facebook page for my course, I could become the most popular professor in the University, but I don't know how to start or what to put up there.

    In many of my classes, I start with the same question, "What is a computer?" The first response: "Something I can't live without." Computers have run the gamut from number crunchers, to word processing to a communications medium to an indispensable extension of oneself in a virtual world, a world I can enter but will never be more than a tourist.

    Friday, April 04, 2008

    If we didn't log on how much email would we get?

    We all get lots of email. One reason is that we respond to it. When I go out of town I set in place a vacation program and do not log on (or I log on but do not respond to anything--- unless its REALLY important- a slippery slope). How much email do I get? What are the factors?
    1. In 1998 I went to Italy for 6 weeks and did not log on at all. I came back to roughly 300 emails. (Very little Spam). This was far less than I thought I would get. The reason: Since I didn't respond and my vacation program said I was out of town, people did not re-email.
    2. In 2007 I was on vacation for 11 days over Christmas/New Years and predicted I would get roughly 100 emails. Much to my surprise I got exactly 100 emails. Part of the reason it was so low was that it was most schools winter break. I predict that this will be less true over time- people seem to be working 24/7 and technology is allowing them to.
    3. I was out of town and off of email from March 30 until April 3 (the last few days). I got exactly 150 emails. About 10% was from ORBITZ confirming my flights.
    4. My spam filters are pretty good- most of the email that got through was not spam. Before I had good spam filters I would get lots of spam AND lots of bounced email when my spam was responded to by my vacation program which then got a bounce.
    When I am at a conference I try to avoid logging on. I'm there to learn things, meet people, doing stuff I can't do normally. There is very little important email that needs to be dealt with now. CCC08 will be an exception as I expect there will be email telling me that there aren't enough bagels or whatnot.

    Thursday, April 03, 2008

    An Analog Guy in a Digital World

    During my blogging hiatus last summer, some times I would see something that would make me want to write a post if I were still blogging. Such as the movie Live Free or Die Hard.

    Bruce Willis reprises his role as policeman John McClane battling tech wizard Thomas Gabriel (Timothy Olyphant) who is creating havoc by taking over various computers controlling traffic, power and the like. For such a computer-oriented theme, the movie had a retro anti-tech feel. Though McClane is teamed up with a computer geek played by Justin Long (Mac from those Apple ads), he fights back mostly by crashing cars and blowing things up. McClane's aversion to technology is a running theme in the movie, where Gabriel at one point mocks him as an analog guy in a digital world. Without spoiling too much, you can guess who wins out in the end.

    The movie itself has much less CGI than other recent action movies, relying on old fashioned stunts and lots of explosives. There is an interesting theme to this movie: Even in a technology dependent world, an old-fashioned hero can still save the day and have a lot of fun doing it.

    Wednesday, April 02, 2008

    Two Israels

    My Israel trip started with a visit to the Technion with a short side trip to the University of Haifa. Visiting universities in Israel is not unlike visiting universities anywhere else in the world. I gave a seminar presentation, we talked research and gossiped about other computer scientists. We didn't talk politics much and then it was mostly American politics. Professors there have the usual problems balancing theorems and families.

    After that, spurred by my daughter's upcoming Bat Mitzvah, I and the rest of my family did a tour with several other families from my congregation. This mission, as it was called, emphasized the Israel I grew up learning about, the Jewish state that we mention in many of our prayers. We examined the struggle of the Jews thousands of years ago, sixty years ago and today. I touched both the sacred Western wall of the old temple and the much newer wall that separates Israel proper from the territories.

    Two very different experiences in the same country. But these worlds get very close. We drove by Tel Aviv University, visited a once-secret bullet factory near the Weizmann Institute and said our welcoming prayers to Jerusalem just downhill from Hebrew University. But more than that, one cannot help but notice the plaques on the walls at the Technion mentioning the various infrastructure donated from American Jews. These have been possibly the greatest gifts to the country as the strong Israeli University system has propelled an extremely successful high tech industry giving Israel an economic security that seemed unimaginable when I was a kid.