CCC2008/ ACM dissertation awards 2007

Two links of interest:

1. Complexity 2008 deadline for early registration is JUNE 1- so sign up NOW!
2. ACM Dissertation Awards What is of interest is that the winner and two of the three runnerups are in THEORY- the winner and one of the runner ups is in Cryptography

Actually the winners are often theorists though this year it is more striking. Are theorists producing the best PhDs in computer science? I would not say that; however, for a theory PhD (and perhaps for theory in general) its easier to tell that something is good work since we have well defined problems that can have well defined solutions. Other areas do indeed produce good work, but it may take time to recognize that.

Tough Math

Back in 1992, Mattel had a controversy on their hands when Teen Talk Barbie said "Math Class is Tough." Today we hear about the difficulty of mathematics about another woman, this one running for president.

"She has fought a very energetic race, but the math just isn't there." (Tim Russert on MSNBC)

"She's mounted an extraordinarily impressive and tough campaign," said Steve Grossman, a Massachusetts superdelegate and pledged Clinton supporter. "The math is tough. Most people think the math is virtually impossible." (Boston Herald)

Obama chief strategist David Axelrod said whichever way the Clinton camp spins it, "the math is the math." (AFP)

The Clintons' War Against the Math (ABC News)

and many more.

What is our beloved field of mathematics doing to poor Hillary? Of course "math" does not describe the technical delicacies of the field, but rather to remark that in the end the nomination goes to the candidate with a majority of delegates and given the current delegate status the probability that Obama will not achieve that majority is quite low. The term "math" is also being used as a logical game-stopper—no one can make 1+1=3 no matter how hard they try.

"Math" gets played by the media as a cruel and heartless monster that many believe Hillary Clinton cannot defeat, rather than the the beautiful and ever growing field of knowledge that we love and respect.

Or maybe, as John Dickerson suggests, another scientific field now applies.

The race for the Democratic nomination…now feels like a quantum physics problem: How long can a body exist in a state approximating motionlessness without actually stopping?

Final STOC Post

James Lee finishes up from Victoria.

Still at the business meeting (with a 15-item agenda), Cynthia explains that another rule of thumb was in place for STOC’08: If a program committee member said "this is my favorite submission," then the paper was marked for acceptance, barring a severe negative reaction from the other committee members.

Next, Bobby Kleinberg tells us about the "TheoryWiki" project, whose goal is to organize a community-wide effort to improve the presence and quality of TCS on Wikipedia. This seems like a fantastic goal. To rant tangentially while I have the chance: Unfortunately, a large contingent of our community recently contributed to the Springer Encyclopedia of Algorithms. There were various area editors who put together a list of possible articles, and then solicited authors to write them. The area editors were not paid. The authors were not paid. On the other hand, the default was for the copyright on all materials to be handed over to Springer, who will create a huge and potentially useful volume, and then sell it at very expensive prices. I agreed to write my article, but I complained quite a bit first. I was told that the process was too far along to change anything. I asked Springer if I could put it on Wikipedia. They said no. Finally, I said: I am writing an article. I am putting it in the public domain. I will give you permission to distribute it however you like; take it or leave it. They took it. Unfortunately, most authors did not make similar deals, and a tremendous amount of time and effort has been wasted (or, in the least, vastly underutilized).

Adam Kalai announces that STOC 2010 will be in Boston (where he and Yael will be joining the newly formed MSR New England). Allan Borodin reads the conceptual manifesto. Despite a lot of dissent expressed in private conversations, Mikkel Thorup is the only one to speak up. He argues that, while new models should be valued, we might also want to appreciate the kind of algorithms that are running on millions of computers around the world right now.

---

I’ll end with some talks I enjoyed from the rest of the conference:

• Chris Umans gives a near-linear time algorithm to compute the composition of two multivariate polynomials over finite fields of small characteristic. This leads to asymptotically faster algorithms for factoring univariate polynomials over finite fields. The composition algorithm is inspired by the Parvaresh-Vardy and Guruswami-Rudra codes. (According to Chris, the “small characteristic” assumption has recently been lifted.)
• Ishai, Kushilevitz, Ostrovsky, and Sahai disprove a well-known conjecture of Mansour, Nisan, and Tiwari by showing that 2-universal hash functions (from n bits to n bits) can be computed by circuits of linear size. Expander codes are the primary tool. (Their ultimate goal is more efficient crypto primitives.)
• Adam Kalai gave an entertaining talk on "The myth of the folk theorem," joint work with Borgs, Chayes, Immorlica, Mirrokni, and Papadimitriou. The "Folk Theorem" is a collection of results from game theory which describe the Nash equilibria in repeated games, i.e. where the same one-shot game is played over and over. The "myth" of the folk theorem is that finding Nash equilibria in repeated games is easy, and it's true for two players: There is a poly-time algorithm. The authors show that once the repeated game has three players, though, finding a Nash equilibrium becomes PPAD-complete, just as in the one-shot case. The reduction from 2-NASH is pretty simple, and comes with the fantastically apt name of the "Actor-Critic game" (which, in the talk, was played by actors Jason and Nicole, and critic Lance).
• Shachar Lovett gives an explicit construction of pseudorandom generators against low-degree polynomials over finite fields, improving over the work of Bogdanov and Viola who did this for d=2 and d=3. Lovett uses the sum of 2^d eps-biased generators (these are pseudorandom against linear functions). His analysis involves the Gowers norms, which measure the bias of random “derivatives” of a function. In very recent work, Viola has shown that one need only sum d eps-biased generators. Viola’s work does not use the Gowers norms, and is simply based on the bias of the polynomial to be fooled.
• Spielman and Srivastava show that every n-vertex graph can be sparsified to a (weighted) subgraph containing only O(n log n) edges, where the sparse version preserves all Rayeligh quotients of the Laplacian up to a (1+eps) multiplicative error. In particular, the weights of all cuts in the sparse version are the same up to 1+eps. They also give a near-linear time randomized algorithm to sample the sparse subgraph. The sample probability of an edge is proportional to its effective resistance in the electrical network defined by the graph. They analyze the sampling procedure using work of Rudelson on central limit theorems for sums of rank-one matrices.

There were many other beautiful results presented. I suggest using the comments section to highlight your favorites.

STOC Business Meeting, Part I

More from Victoria by James Lee.

Jeanette Wing, the new director of CISE, kicks off the business meeting with an overview of the funding situation for theory at NSF. I think I discern two clear messages: First, NSF is part of the executive branch, so there is one clear way we can affect the budget this November. CISE has requested a 19.5% funding increase for 2009, with a 25.5% increase requested for CCF. Secondly, the best way to expand the amount of funding for theory is for algorithms people to look for money outside of pure theory venues. The opportunity to do this will hopefully be improved by having Sampath and Jeanette on our side at NSF.

Dick Karp wins the SIGACT Distinguished Service Award, for his tireless dedication to promoting and expanding TCS. Prasad and Harald are given their best paper awards. Then Cynthia gives her report on the program committee, and its decision process.

80 papers accepted out of 325 submitted (that's about 24.6%). Some notable results: Congestion and game theory goes 5/13 (38.5%), and metric embeddings goes 0/13 (0.0%). Before the committee met, they agreed on having a more open mind toward conceptual papers which might be otherwise overlooked because they lack technical depth. The following paragraph was added to the call:

Papers that broaden the reach of theory, or raise important problems that can benefit from theoretical investigation and analysis, are encouraged.

This paragraph has been kept for FOCS'08.

The committee sought to appreciate simplicity as a virtue; no longer "I like the ideas, but the proofs are simple"; instead, "I like the ideas, and the proofs are simple!" I don't know if "They changed the model so as to trivialize the problem" is also replaced by "They changed the model, and now the problem is trivial!" I think responsible analysis of a paper is probably a bit more nuanced.

Later, Madhu Sudan spoke of instances where a well-known problem had an easy solution, and this prevented a journal or conference from publishing it. This is certainly ridiculous, and I have a hard time believing that it's a frequent occurrence (of course, I have about 1% of Madhu's experience). I've seen examples where the community considered it "embarrassing" that the solution was so simple, but not where the paper itself was derided.

Personally, I love the beautiful intricacies of hard, technical proofs. It's like a little universe sprung out of the human effort poured into developing a deep understanding of some problem. There are often reoccurring characters, a unique language, a sense of history, twists and turns, all mounting towards a resounding conclusion that one only fully comprehends after multiple readings, and intense effort. But in our field, the beauty of complexity only makes sense in contrast to our search for simplicity. Simplicity is certainly a virtue.

When I have criticized a paper based on "technical simplicity," it's not because I wish the authors had purposely obfuscated their arguments. Rather, one has to understand the primary goals of a theoretical field: To approach understanding through rigor. What we are trying to understand is computation in all its forms. Toward this end, we often consider idealized versions of problems, and in this respect modeling becomes incredibly important. It comes up in algorithms: What happens if the traveling salesman wants to minimize the average latency, and not the total travel time? And it happens in complexity: What if we allow our constant-depth circuits to have mod gates with composite moduli?

In both cases, we are not confronting the actual problem we want to solve; real-life instances of salesman problems (e.g. satellite movement) probably involve other practical constraints, and (uniform) poly-size circuits can probably do a lot more than AC_0[m]. So often I have to measure the importance of a new model by how it differs technically from the old one. If simple modifications of the old TSP algorithms suffice for the minimum-latency version, it's not clear that we have learned something new (even though one could argue independently that the min-latency version is practically important!). And if AC_0[m] circuits could be simulated in a simple way by AC_0[p] circuits, then I wouldn't think as highly of a paper proving lower bounds against AC_0[m].

Maybe we can be a little more appreciative of the subtlety involved in the reviewing process, and agree that "simplicity is a virtue" is a a bit too simplistic to be the motto for a program committee.

STOC Day 1

James Lee reports from Victoria.

STOC 2008 begins. Victoria is a gorgeous city, if a bit sterile. The population feels mostly transient. The people are very friendly, and the streets are very clean. Most academic conversation turns eventually to one of two topics: Outcomes of the hiring season, and opinions on the "conceptual manifesto" (my naming); more on the latter topic in the business meeting post next.

The conference starts off strong, with Ran Raz presenting Anup Rao's optimal parallel repetition theorem for projection games (Anup had visa issues). Anup gives optimal bounds on the rate of decay of the value of a 2-player game repeated in parallel, in the case where the answers of one player determine the unique answer of the other player that causes the verifier to accept (this is the projection property). The decay rate was recently proved to be optimal by Raz, thereby disproving a strong parallel repetition theorem.

A special case of a projection game is a unique game, the topic of Prasad Raghavendra's paper Algorithms and inapproximability results for every CSP?. Prasad is one of our own, a theory student at UW; his paper was co-winner of the best paper award and sole winner of the best student paper award. For a few years now, since the KKMO max-cut paper, it has been suspected that there is an intimate connection between the unique games conjecture and the power of semi-definite programming in approximation algorithms, although it is only recently--in the work of Austrin--that this connection has begun to materialize explicitly. Prasad sets the connection in stone: He gives a general class of SDPs and a generic poly-time rounding algorithm for all of them, such that for any MAX k-CSP problem, the approximation bound achieved by his algorithm is best possible assuming the unique games conjecture. A key technical step involves converting any integrality gap for his SDP to a unique games hardness result. The talk is remarkably lucid and well-paced.

The other best paper winner is Harald Raecke, for his work "Optimal hierarchical decompositions for congestion minimization in networks." Raecke shows roughly that, given a graph G, there exists a family of trees such that any multi-commodity flow problem in G can be solved by first routing it in each of the trees (trivial), and then mapping a convex combination of those routings into G. The resulting routing in G has congestion within O(log n) of optimal. The mapping from the tree routings to routings in G is fixed, and in particular independent of the flow instance. This gives an O(log n)-approximate oblivious routing protocol, which is best-possible. His proof is a beautiful and unexpected reduction to the FRT tree embedding theorem. In another quite unexpected move, Raecke shows that his tree decomposition theorem can be used to obtain an O(log n)-approximation for the minimum bisection problem.

I expect that the next post, concerning the business meeting, will be a bit controversial. In other news, Adam Klivans loses $20 for betting that the desert contains papaya. It was mango.

Visioning Workshop

James Lee starts his guest posts from Seattle and Victoria.

On Saturday, SIGACT, in conjunction with the Computing Community Consortium, held a workshop on Visions for Theoretical Computer Science. The goal of the workshop was to produce "vision nuggets" about exciting research themes in TCS that could have a large impact in the future. In other words, to craft PR materials that advertise TCS outside the community (most importantly, to funding agencies). Some pre-workshop socializing started off a bit dangerously, with Anna Karlin explaining that Avi Wigderson should saber the champagne since last time she ended up in the emergency room…

     

The visioning began excruciatingly early (certainly before I could see clearly), but it started off with some good news from Sampath Kannan, the new director of the Computing and Communications Foundations (CCF) division at NSF:  We're moving up in the world (or at least in the new NSF bureaucracy tree).  CCF will be restructured into three top-level clusters:

• Algorithmic Foundations
• Communication and Information Foundations
• Hardware and Software Foundations

STOC/FOCS/SODA/CCC-esque theory will fall into the first cluster.  Besides the hopefully inevitable consequences of getting us closer to the root, there were some more subtle ones, e.g. computational geometry and quantum computation will no longer be funded separately from the rest of theory (Sampath was careful to distinguish quantum computation from e.g. quantum information and quantum engineering which don't fall into this cluster).

Then we broke into groups to "brainstorm" the nuggets; the groups were arranged into categories based on nugget sketches submitted ahead of time:  computational complexity, data-centric computing, economics and game theory, natural science, parallel computing/networks/architecture, and security/privacy/reliability.  By lunch time, various nuggets emerged, with potential titles like "Debunking the privacy vs. utility myth"  (followed by an argument about whether this constitutes a double negative and should be replaced by "Bunking the privacy vs. utility reality"?).  Watch the wiki for polished nuggets appearing in the near (hopefully) future.

The workshop was not without controversy, with Leonid Levin and Avi diametrically opposed on the number of nuggets we should be creating.  Leo thought we should have 0 nuggets, since the future of science cannot be mandated by committee.  Avi, on the other hand, treated the nuggets much like crack (the more the better).  At one point, a group wondered "Should we merge these two nuggets into one?" with Avi replying (paraphrased) "But they're so fundamentally important, why not split them into three?"  In the end, we seemed to find a happy medium (especially once Levin realized that our goals were less as "Gestapo" and more as "PR firm").  In the mean time, the view out the window of the UW CSE department provided a calming distraction.

After the workshop, a large contingent of the participants boarded a seaplane for the trip to STOC 2008.  First Rocco Servedio loaded Karp's luggage.  Then he flew us to Victoria.  See you in Canada.

         

Thanks to the organizers:  Bernard Chazelle, Anna Karlin, Richard Ladner, Dick Lipton, and Salil Vadhan for all their hard work in designing a productive and non-too-painful day of workshopping.  Credits to Claire Mathieu for some of the pictures.

Reminder: Register for Complexity 2008

REMINDER: Register for COMPLEXITY 2008. Deadline is June 1 for early registration; however, the earlier the better. Register here.

Why should you go?

1. If you are a beginning student in theory you should go to see what research is happening. Something you see in a talk may inspire a PhD topic.
2. If you are a student in theory who already has a topic in Complexity then you should go to see how your topic connects to other branches in Complexity. And to talk to other people who may know stuff about your topic.
3. If you are a student in theory who is working in algorithms then you should go to broaden your horizons.
4. If you are NOT a theorist than should you go? Depends- if you want to get into theory or if you have a passing interest then certainly. If NOT then... well, there may be some other reason to go.
5. If you are an adjunct, postdoc, lecturer, professor, research scientist, or some other category that I can't recall, some of the above reasons still apply to you.

It is likely that you won't follow some of the talks. Realize that just knowing that some area of research is out there is good. A talk can be a good place to find this out and get references. Also, some talks you can skip, hang out in the halls, and meet your fellow theorists.

The Week Ahead

Neither Bill or I will be attending the upcoming STOC in Victoria. Have no fear, we have once again enlisted an excellent guest poster to keep you all abreast of the latest happenings.

On Saturday in Seattle, there will be a Visioning Workshop with two goals.

1. Identify broad research themes within theoretical computer science that have potential for a major impact in the future, and
2. Distill these research directions into compelling "nuggets" that can quickly convey their importance to a layperson.

We have workshops like this every now and then (remember Portland?), and it is good for our community to occasionally step back and make the case for theory, both to attract good researchers and funding, but also to ourselves so we don't lose sight of the basic reasons of why we do what we do.

At the STOC business meeting, Borodin will discuss his co-authored letter about conceptual contributions that has already appeared on Scott's blog. Nobody seriously argues against papers with important conceptual points, rather we have the problem that STOC and FOCS have gotten to the point that they accept only a fraction of the strong papers in a given year and difficult decisions have to be made and it is much easier to recongize a strong technical paper than a strong conceptual one. Still both the STOC and FOCS 2008 committees are fighting back with the new line added to the call.

Papers that broaden the reach of theory, or raise important problems that can benefit from theoretical investigation and analysis, are encouraged.

We can only recognize true conceptual greatness when it stands the test of time conflicting with computer science's deadline-driven conference system. Something has to give.

Surveyed to Death

So far in May I got requests to fill in surveys for Consumer Reports, industry research in IT management, a hotel I recently stayed in, new Lyric Opera dining options and at Northwestern: Internal Communications, International Office, course management system, library space planning, research computing needs and dealing with prospective grad students. The Internet, particularly sites like Surveymonkey make surveys very simple to create and distribute. Each survey promises to take only a small amount of my time and in some cases (like Lyric Opera Dining) I actually care about the outcome. But since I get constant requests, I tend to skip nearly all such surveys.

If you ask the average person on the street which is more accurate: a random sampling of 1200 people or an online survey open to all, most will (incorrectly) say the latter. On-line surveys suffer from statistical skewing—they only measure people who take the time to fill out surveys. And as people like me get inundated with requests, the only ones to fill out surveys are people with strong opinions about the topic or those with too much time on their hands and the results of these survey will be a quite poor reflection of reality.

If every survey writer only sent their surveys to a small randomly selected group of people, then each of us would have very few surveys to fill out and could take the time to do so. But we can't expect surveyors to act so responsibly, nearly all surveys will suffer. So don't bother with the surveys. Open up an on-line suggestion box, a message board or a blog and get the discussion going. Use words instead of meaningless statistics to guide your decisions.

The problem with making websites

In my last post I had as a side comment that I maintain a website of applications of Ramsey Theory to Computer Science. One of the comments pointed out two papers that are not on it (but will be soon) and someone else said he had used it. GREAT on both counts!.

When making a website of applications of Ramsey Theory to Computer Science or website of satires of Bob Dylan. or a website of Funny Math Songs (coming soon) or any list or a website of famous people known only by one name (hoping somone else does this, but I have a pretty good list) one encounters various problems:

1. What is an Application? What is Ramsey Theory? What is Computer Science? These are not important questions, but when making a list they need to be answered. For example, is using Gowers Techniques that have been used in Ramsey Theory count? Probably yes since most people looking at my website on applications of Ramsey Theory will care about that. Do I count papers that use computer programs to find Ramsey Numbers (or VDW numbers or...). I have not, thats not really an application. What about computer science papers (hmmm- how do you define that?) that give constructive lower bounds on Ramsey Numbers? (I have begun a website on Constructive Ramsey Numbers that makes no pretense of being close to complete.) If you include to much you lose coherency. Better indexing might help, but I don't have that much time to spend on this. (I'd have more if I didn't do this blog :-).)
2. What is a Bob Dylan Satire? If Bob Dylan sings it, then can it be a Bob Dylan satire? (Yes). If William Shattner sings Mr. Tamborine Man very badly, and its funny, but he did not intend it as satire, is it a satire? (Yes). If someone just sings incoherently but its not funny is a Dylan satire? (No) Here my criteria is mostly Do I find it funny?, or is there Some other reason to include it? But in the end its my call and might be arbitrary at times. Fortunately, in this one area, I may be the worlds leading authority so the answer might be If Bill Gasarch says its a Dylan Satire, then it is.
4. Funny Math Songs- When I get around to this one I will use the Is it funny? criteria. Otherwise you are stuck with lots of stuff that uses math very tangentially- For example, in Bob Dylan's song Tangled up in Blues he has one line Some are mathematicians, some are carpenters wife's. One line does not a math song make. Also, there are some songs about computers being hard to use (The best one- Where's the Service by The Pheremones.) I would not include this. Should I include it in funny songs about computer science. No- its not science. But it is funny. Alas- so many websites to make, so little time.
5. More generally, when making a list you need to balance the need to be complete with the need to be coherent. And many unimportant questions need to be answered, such as What is an application. This may help sharpen your mind and teach you things, but it can also drive you into pointless arguments with Dylan Fans.

What is an application?

What is an application?

1. When I took Algebraic Topology the professor said at one point I will now show you an application of homotopy theory at which point the one physics major taking the class woke up and said An application! Finally! Is it an application to quantum field theory? The professor said No, we will use homotopy theory to show that every polynomial with complex coefficients has a complex root The Physics student went back to sleep. (Short sketch of proof: Using Homotopy theory you can show that the complex plane and the punctured complex Plane (remove the origin) are different topologically- the former has trivial homotopy group, while the later has homotopy group Z. Therefore there is no `nice' map between them. If there was a poly p(z) with no roots then you can use this to get a nice map between the two.)
2. When I took Ramsey Theory the professor said at one point I will now show you an application of Ramsey theory at which point the one physics major taking the class woke up and said An application! Finally! Is it an application to quantum field theory? The professor said No, we will use Ramsey's Theorem to show that, for all m, there exists an n so that, for all sets of n points in the plane, no three colinear, there exists m that form a convex m-gon. The Physics student went back to sleep. (Short sketch of proof: Let n be the 3-hypergraph ramsey number such that for any 2-coloring of the 3-sets of [n] there is a homogenous set of size m. Given the n points in the plane, color sets-of-three as follows: if the number of points in the triangle formed by the 3 points is ODD then color it RED, otherwise BLUE. There will be m points such that every set of 3 has the same parity inside it. One can show that these m points form a convex hull of an m-gon. First step of this proof: if one of the points is inside the convex hull then its inside a triangle formed by three of the other points. NOTE1: Much better bounds are known. NOTE2: Finding the smallest n is called the Erdos-Szekeres problem or the happy ending problem. See this paper for a survey.)
3. I have a website of website of applications of Ramsey Theory to Computer Science. One of the first ones was Yao's paper Should tables be sorted?. This paper shows that in the Cell Probe Model, if the universe is big enough then yes indeed, tables should be sorted. (Short Sketch: Assume there is a scheme for, given n elements of the ordered universe U, stores them in an array of length n cells. Let the universe U be of size the n-hypergraph Ramsey number such that for any n!-coloring of the n-subsets of U there is a homogenous set of size 2n-1. Color an n-subset of U by the permutation it is stored in. There will be 2n-1 elements such that any subset of n is stored in the same permuation. Assume that it is SORTED (if not then it is a fixed perm to make it SORTED). One can show that if the list is sorted then binary search is the best way to find an element. See this paper for a survey. )

So, are these applications or not? The first one applies topology to algebra. The second one applies Ramsey Theory to the Erdos-Szekeres problem. The third applies Ramsey Theory to Data Structures.

The first and third seem like legit applications. The second one is suspect- applying one Erdos-style branch of combinatorics to another. But they are different branches. One metric of how legit an application is might be how far apart the fields are.

Teaching Parallelism

Uzi Vishkin wrote these ideas on how to teach a parallel computing course as a comment on my earlier parallelism post.

The basic claim is that:

• It does not make sense to have a new platform of general-purpose parallel computing succeed the established serial platform without having a one-to-one match of EVERYTHING, including algorithms and data structures.
• In particular, it does not make sense to teach parallel programming without teaching parallel algorithms and data structures. The gap between programming and algorithms must be bridged, so that the continuum from algorithms and data-structures to programming will resemble as much as possible the continuum in serial computing.
• Since the PRAM theory is the only serious candidate developed in nearly 3 decades of research, PRAM algorithms have got to be taught.

I expect theorists to endorse this argument and use it to convince their colleagues that PRAM algorithms need to be taught. But, I have to be frank. I am concerned that some of us will do the following: teach a course on parallel algorithms as a purely theory course WITHOUT any connection to programming. This will miss the point as it ignores the need to relate algorithms to programming. The Q&A at the end of this text elaborate further on the programming issue.

As others have implied, you can find several fine sources for PRAM algorithms. For this reason, my comments below mostly focus on a way to address the parallel programming issue:

1. In class presentation.
   1. Read Section 2.1 entitled XMTC in FPGA-Based Prototype of a PRAM-On-Chip Processor. It reviews a modest extension to the C programming language called XMTC that allows PRAM-like programming. XMTC essentially adds only 2 basic commands to C: Spawn and PS (for prefix-sum).
   2. Devote a total of around 15-20 minutes similar to slides 37-39 in these slides to present XMTC. Slide 40 can guide a discussion.
2. Supporting documentation. The students should then be referred to: the XMTC Manual and the XMTC tutorial.
3. Programming assignments. Please look up under assignments on this course page.
4. Running programming assignments. The UMD PRAM-On-Chip project is on track for public release by the end of June 2008 of:
   1. a cycle accurate simulator of the PRAM-On-Chip machine, and
   2. a compiler from XMTC to that machine.
   The will allow your students to run XMTC code on an emulated 64-processor PRAM-On-Chip machine. To remind you, a hardware prototype of such a machine (using FPGA technology) has been in use at UMD since January 2007. A compiler that translates XMTC to OpenMP will also be released, giving your students an alternative way to run their assignments.

Finally, please note that this type of programming cannot be too difficult. I have given a 1-day parallel algorithms tutorial to a dozen high school students in Fall 2007 and subsequently some of them managed to do on their own 8 programming assignments. In fact, the above link to programming assignments gives these 8 programming assignments. The only help the high school student got was one office hour per week by an undergraduate teaching assistant. They did not get any school credit for their work. Their participation was in the context of a computer club after completing their regular school work (8 periods per day).

If you are looking for code examples, you are welcome to write to me.

Here are some Q&A:

Q: I never learned parallel programming formally, but I picked up some ideas in my free time from Java/MPI/OpenMP/etc. How do any of these relate to XMTC parallel programming?

A: XMTC parallel programming is simpler and different.

Q: The problem of algorithms being taught independently of programming is present within the exclusively serial world. What would you say to the many theorists who are resistant to the idea of having a heavy programming component in their courses?

A: IMHO the serial case is completely different. Most students have experienced/learned serial programming BEFORE taking the serial algorithms course. This is NOT the case for parallel programming. My experience is that students learn best if parallel programming is coupled with parallel algorithms. The main difference is that the parallel algorithms course is where parallel programming should be FIRST taught. The reason is that parallelism requires introduction of some first principles representing an "alien culture" to students. In contrast, serial computing is related to: (i) mathematical induction, (ii) the way our brain instructs our body (as a single processor), etc. There is nothing out there that prepares us for parallel computing.

Q: What text do you use for teaching parallel algorithms?

A: I have been using my class notes.

Warm thanks to Adam Smith and Aravind Srinivasan for their helpful comments on an earlier draft of this text.

Electronic Commerce and Prediction Markets

Registration has opened for the upcoming ACM Electronic Commerce Conference (which I am general chair) in Chicago July 10-12. The conference is immediately followed by AAAI and The Third World Congress of the Game Theory Society both also in the Chicago area. Before the EC conference is a series of workshops and tutorials covering topics from on-line advertising to social networks.

One of those workshops covers an area that has excited me for several years now, The Third Workshop on Prediction Markets. Prediction markets aggregate information quite efficiently in ways we don't yet fully understand and remains a fertile area of study. Legal limitations on betting have restricted the applications of prediction markets, particularly in the US, but that might change soon. The Commodity Futures Trading Commission (CFTC) is asking for public comment for regulations of prediction markets. Their concept release gives a nice discussion of the legal issues. Will this lead to more legitimate real money markets in the US? Time will tell.

More from Pennock and Masse.

Any Questions?

A speaker in a seminar talk loves to get questions during the talk for this means that at least one person is trying to follow the talk. A talk with no questions means everyone is either completely following the talk or is completely lost, most likely the latter.

Each question though involves three parties: the questioner, the speaker and the rest of the audience. A good talk has a certain rhythm and questions can disturb that rhythm. So how does the audience feel about the questions? Depends on the question.

1. Questions that clarify the model or some aspect of the proof. We need these questions to properly follow the talk. When others ask these questions, I learn that I really hadn't understood the model when I had thought I had.
2. Questions that argue against the model or results. Usually entertaing but can often degenerate into a long argument. The host needs to become a moderator and has to give one of those one-time nerd jokes that have become standard lexicon: "Take this discussion off-line."
3. Questions that point out mistakes. Usually annoying and serves no purpose unless, of course, it takes down the whole proof.
4. Questions that prove how smart the questioner is. The most annoying. I cringe whenever I hear a question starting with the word "So".

At the end of the talk the questions usually suggest various extensions to the work that can often go on forever. Most of the audience just wants to escape but is too polite to leave. The host again needs to end the discussion. Having food in another room to continue the discussions in can help immensely.

Vanished from the web- of more interest...

In my last post I told of a Masters Thesis that vanished from the web, into the night. I suspect I am one of the few people who wants a copy, hence this incident will not attract any wider attention. This is a contrast to today's tale of vanishing.

A while back a talented fellow named Kevin Ryan recorded and put on the web Dylan hear a who, which was 7 Dr. Suess stories sung in Dylan style. (Since I own what is probably the largest collection of Bob Dylan satires in the world-- 127 satires and an additional 14 songs that I don't count as satires but others do--- this was a must have.)

Kevin Ryan got a Cease-and-desist order from the Dr. Suess people to remove it, and he did, as you can see here. One version of the story, which seems correct, is in this article

One Moral of the story: If you find a SOMETHING on line that you may want to keep, DOWNLOAD IT. Do NOT depend on it still being there later. But there is a different issue here:

Is what the Dr. Suess people did legal? I do not know. Is what the Dr. Suess people did moral? I do not know. Is what the Dr. Suess people did stupid and against their own interests? Yes. I can picture someone hearing Dylan hears a who and going out and getting some Dr. Suess books. I cannot picture hearing it and therefore not getting some books. Businesses need to devolp different business models for the e-world in which we live. For example, they may have worked out a deal where a link to purchase Dr. Suess books is on that same website and/or an advertisement. It is likely there are other possiblities. For more on this, read the book wikinomics, which I might blog about at some later date.

If you find something online download it NOW

A few months ago I was looking into some of the origins of Ramsey Theory (in particular I was looking at what Hilbert needed Hilberts Cube Lemma for) and I came across the following online

Combinatorial Number Theory: Results of Hilbert, Schur, Folkman, and Hindman by Yudi Setyaan. A Thesis submitted in partial fulfillment of the requirements of the defense of Master of Science in the Department of Mathematics and Statistics. Simon Fraser University, July 1998

I printed it out and still have it. It was not helpful for what I wanted, but it was interesting and I'm glad to have it.

Recently I wanted to email it to someone else so I searched for it again. Its gone! Now you have to pay for it at amazon. I also looked for the author on line to see if he might email me a copy (I doubt he gets any money from it and I suspect he would be delighted to find out the someone actually read it.) Couldn't find the authors email address, though I am hopeful that I will.

Moral of the story: If you find a document on line that you may want to keep, DOWNLOAD IT. Do NOT depend on it still being there later.

Report on Sym for Lipton's 60th bday (guest post Ken Regan)

(Guest Post by Ken Regan)

A two-day symposium in honor of Richard J. Lipton's 60th brithday was held April 27--28 in the brilliant new Klaus Advanced Computing Center at Georgia Tech. The wide variety of talks influenced by Dick Lipton's ideas attested his ability to say something deep about many subjects. Deep and still keeping to a dictum of Hilbert featured on one speaker's slides: the simple attracts. An example referenced in many talks was his ("one-paragraph") proof of the self-reducibility of the permanent Wikipedia entry). Another referenced his co-authorship of a March 2008 report to the Georgia Secretary of State with recommendations and advisories on electronic voting.

The first talk by Richard Karp carried the message that problems of the Hitting-Set kind are easier most often in practice than their worst-case NP-complete pedigree leads one to expect. This was supplemented by Neal Young's second-day talk involving Lipton's question, "Is it hard to generate random hard instances of NP-complete problems?" Ravi Kannan spoke on the practicality of finding good approximate equilibria for non-zero-sum games and market situations. Dan Boneh showed the extent to which even certified-sound cryptosystems become vulnerable when keys k are used to encrypt data that overtly contains k, or when there are closed cycles of encodings of multiple keys. He also explained how Lipton's kung-fu wielding of the Chinese Remainder Theorem in attacks on RSA and kin slowed web servers by 8%. Anita Jones surveyed the urban landscape of computer security, and propounded the sequence of system calls made by a program as a signature by which to identify malware.

Michael Rabin described a practical implementation of zero-knowledge protocols for high-stakes auctions, one point being efficiency gains from coding on the arithmetic rather than going all the way down to Yao's oblivious ZK circuit verification. Nisheeth Vishnoi presented a polynomial-time algorithm that distinguishes the "Yes" case of the "Unique Games Conjecture" from a tighter "No" case asserting also that the underlying graph is an expander (paper). This evinces a surprising difference between "Unique Games" and non-unique Constraint Satisfaction Problems, and suggests that if the UGC holds at all, any proof must differ widely from traditional proofs establishing hardness of CSPs.

Erik Winfree's multimedia talk "Is DNA Computing?" demonstrated that whatever one feels about the feasibility of large-scale DNA computers (on which Lipton followed Adleman's first paper with a neater formulation), DNA activity is undeniably computational.

Giovanni diCrescenzo talked on Lipton's idea of storing keys not as small files but parceled among huge hunks of stored data, so that intrusion attempts to recover them leave huge footprints, applying hashing and extractors to implement it. I surveyed the frontiers of super-linear lower bounds, including the Lipton-Tarjan separator theorem's relevance and Dick's part in time-space tradeoffs for SAT, and used Allender-Koucky's observation as a segue to super-polynomial lower bounds. I outlined my position that "Very High Degree" methods are capable of surmounting known barriers and may be necessary.

Dick's longtime friend and associate Richard DeMillo surveyed Lipton's contributions to fundamental problems of software correctness. Wenke Lee focused on how 'bots have opposite behavior and intent to viruses, and how the company Damballa founded by Merrick Furst, him, David Dagon, and Lipton combats botnets.

Parikshit Gopalan presented new ideas on the lower bound frontier of ACC[m] for composite m, and continued a running gag on the power of Chinese remaindering. But Avi Wigderson planted a Monty Python foot on further progress by demonstrating that almost all known complexity-class results preserve themselves under an arithmetical form of relativization, while P vs. NP and most other frontier relations do not. Memo to new graduate students honing their technical abilities by building oracles A separating classes C from D: the ante just got upped to building both A and a low-degree extension A' such that C^A is not contained in D^{A'}, so then proving C contained in D would require "non-algebrizing techniques". And various vice-versas...all of which tighten the rules of equation-solving needed to build A. One sentence of hope remained on Avi's slides actually by Scott Aaronson: methods that go beyond treating (feasibly-constructed) multilinear extensions as black-boxes can possibly evade the new barrier. Jin-Yi Cai closed by presenting a "Holographic" algorithm toolkit of subversive power, whose steep learning curve is helped by its affinity with quantum computation.

On the learning-curve subject, I came away with the impression that although it is often higher for cryptographic protocols than algorithms, more of the former actually get implemented. Of course, Karp has always stood for implementing algorithms, and Neal Young reported on how his beats simplex for its target domain, but I'm just reporting my positive impressions of security applications from the two days. In all it was a rich meeting, with "not too many embarrassing stories" for Dick and lots of energy.

The ID Conundrum

I called human resources at Northwestern with a question about health insurance. After she had trouble tracking me in the system we discovered Northwestern had the wrong social security number for me. Northwestern take great care to hide my SSN, using an employee number on my Faculty ID card and allowing me electronic access to my paycheck with nary a social security number in site. Northwestern would probably not use my SSN at all except they need it to report taxes which would have caused all sorts of havoc had, by pure luck, I didn't catch the mistake.

That's the problem with the social security number. We've become so scared of using the SSN, the number has become useless. What we need is a unique public ID that we are not afraid of using. In my ideal world, we would all have a public and private ID. With someone's public ID I could use it to call them, text them, IM them, email them even send them postal mail by simply writing their ID number on the envelope and the post office's computers will know how to route the mail. People would use their private ID to log onto some central server to set the places that the public ID points to as well as block certain users and deal with privacy restrictions.

You could use your public and private ID to log onto all your services so you don't need to keep separate accounts on various webpages. Both Northwestern and the University of Chicago have single electronic IDs and passwords to access email, benefits and wage information, course information, get wifi access and much more.

Now that people avoid using the SSN as a public ID, cell phone numbers and email addresses are beginning to play that role. Privacy advocates have slowed down efforts to have a public ID for a variety of reasons. But the great need for an ID means the market will start using whatever it has available and isn't it better to carefully design a proper public/private ID than have some ad-hoc market-driven system instead.

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.

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 AC₀.)

Why is SAT &le_m 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 &le_T 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 &le_m with &le_btt. And the result of Lozano that generalizes this to other classes like MOD_aSAT (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.)

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 log₁₀ n columns and each one of them has 10 keys. So the total number of keys you need is 10log₁₀n. More generally, if its base b then you need blog_b 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?

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.

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.

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.

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.

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.

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

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

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.

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?

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.

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.

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.

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.

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.

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 i², minutes (past i² 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.

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.

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.

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.

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.

Erik Demaine proves P=NP!

Details

Opening Day

Fresh back from my Israel trip, still slightly jet lagged, and several hundred emails await me. Hold on, I will get to yours soon.

A new quarter starts today at Northwestern and with it a new course, teaching C++ to young undergraduates. Poor kids.

As of today, I now officially have a teenage daughter and will continue to have at least one teenage daughter for the next 10 years, 2 months and 3 days. Not that I'm counting.

But most importantly, just fifteen minutes after my class today, the White Sox take the field in Cleveland for their first official game of the 2008 season. Baseball is back and all is good in the world.

Univ of MD Grad Student Visit Day

Today was UNIV OF MD GRAD VISIT DAY for computer science grad students. We invited the students who got into UNIV OF MD Grad School in Computer Science for a free lunch and some talks about he program and such, in the hopes that they will come.

1. This is a relatively new concept for most schools. When I was applying to grad schools I do not think any school did it. Now many of them do. And now we all have to do it because everyone else does it.
2. Does it work? Depends on what `works' means. Students do get more information and hence can make a better choice. Whether this is good or bad for UNIV OF MD or any particular school is hard to say.
3. I am happy with the lack of propogandizing we do. We present Maryland honestly. Also, the prospective students get to talk to the students already here to get a true picture.
4. Many of the students who come to the Visit Day have already decided to come to UNIV OF MD so they are just here for the free lunch. I even met one today who already decided NOT to come and was here for the free lunch. Its a good lunch, but not that good.
5. On a related note--- many more students now have done research as a ugrad then when I went to school (I got my ugrad degree from SUNY Stonybrook in spring 1980.) The good thing about this is that if a student says, for example, I want to work in AI they have a better idea of what that means then they used to.

~ ~ ~

Complexity Conf 2008 - CCC08- You can now REGISTER!

You can now register for Conference on Computational Complexity, 2008 which will be in College Park Maryland. Go here to register and also find out more about the conference.

Lance and I will both be there.

If you have never met me and want to say high, I read your blog and I think it is XXX where XXX is any adjective you want, then you can recognize me by either this old picture of me or this more recent picture of me. However, since I am one of the local organizers you may just see a blur as I run this way and that getting things organized.

If you have never met Lance and want to say high, I read your blog and I think it is XXX then you can recongize him by either this, this, or this . I think the last picture captures the true Lance Fortnow.

An odd way to find good employees- it might work

I recently got the following email. It is not spam in that it is a legitimate company asking a fair question and it has only gone to a select group of people. However, a very similar email may have gone to other select groups of people, perhaps millions of select groups of people. Italics are mine.

I found your name while researching scholars who have served as teaching fellows under Professor Harry Lewis at Harvard. The D. E. Shaw group is currently looking to hire a small number of truly gifted individuals with outstanding backgrounds in math, physics, computer science, and other technical fields. As an organization, the D. E. Shaw group goes to extraordinary lengths to identify such candidates and introduce them to the firm. Based on your work as a teaching fellow in one of the most challenging CS courses at Harvard, you seem to be especially well-placed to help us find people with strong academic backgrounds whose areas of specialization might be particularly relevant to the work we do. Do you have any students or colleagues who stand out in your mind as possessing unusual raw ability even among a relatively gifted population of peers? If so, we would be enormously grateful if you'd bring them to our attention. If you yourself might be inclined to explore opportunities with us, I encourage you to send us a copy of your resume.

So, this person researches scholars who have served as teaching fellows under Professor Harry Lewis. How many people do research on that? Do they have their own Journal?

The sender did get one thing right and one thing weird. RIGHT: I was Harry Lewis's TA for Automata Theory in Fall 1981 and Fall 1984. WEIRD: The course was challenging for the students, but I doubt it was one of the most challenging CS courses at Harvard. Actually, I doubt that phrase even makes sense- for me Automata Theory was easy and programming courses were hard, and others felt the opposite.
Harry Lewis has on his website a list of all the people who ever TAed for him, which is where the sender got my name (other TAs of Harry Lewis, some further back than myself, have gotten the same email).
So, why did D.E. Shaw choose this group of people to send the email to? Harry Lewis has no connection to the company, so thats not it.

1. They believe, rightly or wrongly, that ugrads at Harvard who get to TA courses must be pretty good, and grad students who go to Harvard must be pretty good. But see next item.
2. They did not say that they want me to apply. They think I might know people that should apply. At the end of the letter they have an after-thought-type-statement saying essentially, `oh, and you too, I guess'
3. The list of Harry Lewis TA's is available! I also TAed for Michael Rabin, Gerald Sacks, and Leslie Valiant, but they don't have lists of their TAs on their websites. Hence people who do research on (say) scholars who have served as teaching fellows under Michael Rabin or the others have a much harder time.

Deadline Extension for NSF Theoretical Foundations Grant Proposals

(Guest post from Richard Beigel, NSF Theory Director, paraphrased. Any bad spelling or grammar you can attribute to me.)

Because of questions about the deadline in the Theoretical Foundations (TF) 2008 solication, the Theory of Computing program will accept revised Project Descriptions via Fastlane until 11:59pm EDT March 31, 2008. I cannot speak for other program directors. If your proposal is for a different program in TF, please contact your program director directly with any questions.

The link about this grant is here

Nine Billion Names

Arthur C. Clarke passed away yesterday. Of course 2001 dominates peoples memory of Clarke, but it was one of his short stories, The Nine Billion Names of God, that gave me the willies as a kid. It's about a group of monks that hire a computer company to print out all the possible names of God. Read it here before reading the rest of the post.

The story is quite dated as one could now bring a laptop and a couple of batteries to Tibet to complete the task. Nine billion is hardly a large number any more; one could enumerate those names in a few seconds these days. I'm teaching intro programming next quarter. Maybe I'll make it into an class assignment. If the world were to mysteriously end when the students finish the project, at least no one will be around to blame me.

The Life of David Gale

Guest post by Nicole Immorlica

We say goodbye this month to a profoundly inspiring mathematician and economist, David Gale. His influential paper with Lloyd Shapley entitled College Admissions and the Stability of Marriage in 1962 introduced the much-loved stable marriage problem to the literature. The problem asks how a matchmaker in a village can arrange marriages such that no couple wants to divorce their assigned partner and run off together. Such a set of marriages is called "stable", and the set of stable marriages turns out to have a beautiful and endlessly amusing mathematical structure, uncovering such universal truths as "the proposing side of the market ends up with the best partner." (I.e., be proactive in your personal life?) Beyond giving professors and students endless hours of fun and amazing lectures, the stable marriage problem has also had significant impact in many practical settings by providing policy-makers a powerful tool with which to design centralized markets like public school choice and the National Residency Matching Program (NRMP). While the stable marriage work is perhaps Gale's most well-known contribution, he has also contributed significantly to many other fields of math and economics, about which I am much less qualified to comment. He also developed a sort of online museum of mathematical concepts MathSite, which includes some really neat interactive exhibits and is accessible to people of all ages and skill levels.
David Gale was 85, and is survived by his partner, Sandra Gilbert, three daughters, and two grandsons.

Should a grad student use one offer for leverage at another school?

One of my readers emailed me the question below. I gave some answers but then I thought Lets draw on the wisdom of my readers

(EMAIL FROM A READER) I have gotten into two math grad schools which I will call A and B. I want to go to A, but B offered me substantially more money. Can I use the offer from B as leverage to get a better offer from A?

My answer was NO because

1. I doubt it will work--- money has to come from somewhere, I doubt School A can just find money for you.
2. I doubt it will work-- School A has other students who want to go there, I doubt you're that big a deal to them.
3. If you make a threat like this you need to be able to carry it out. That would put you at school B which you don't really want.

Speculation: This just isn't the kind of thing that grad students do. This is NOT a reason to NOT do it, and perhaps grad students should do it. Do you want to be the rebel who changes the system? Can you be?

Readers- what do you thing? Do grad students ever do this? (I don't think so). Should they? Should she? ~

The Broken Remote Problem

This year I wrote one of the problems on the Univ of MD High School Programming Contest. The following conversation did not take place but could have.

BEGIN

BILL: Here is my problem. Imagine that you have a remote control for a TV set but that only a few of the numbers work. Also the UP-ONE and DOWN-ONE buttons work. Write a program that, given which numbers are available, and given x and y, return the sequence of botton pushes that get you from x to y in the least number of pushes. (NOTE- this description is incomplete- see problem 7 for a formal description.)

PROGRAM COORDINATOR: Is this some sort of Ramsey Thing in disguise?

BILL: No.

PROGRAM COORDINATOR: Then how did you think of it?

BILL: The remote at my in-laws only had 4 and 5 and UP and DOWN working.

END

The Broken Remote problem is not hard in that it does not need cleverness. But there alot of details to get right. Only 2 schools got the problem; however, the reason might be because problem 3 was harder than anticipated, hence some did not get to problem 7.

The point of all this?- similar to this post- everyday situations can inspire a math or comps sci problem.

Is the problem original? Hard to define what ``original'' means; however, I would not be surprised if it a similar problem appeared in some other contest.