From his The New York Times obituary : David Harold Blackwell was born on April 24, 1919, in Centralia, Ill.

The household saving rate and the household investment rate dropped in the European Union and in the 16-member euro zone in the first quarter of 2010, according to a detailed set of quarterly European sector accounts released by Eurostat, the statistical office of the European Union, and the European Central Bank .

This is an IBM commercial. I’m not sure about “math can do anything”, but it’s encouraging to see a positive message about math for a change.

According to IBM’s “Smarter Planet”, the 3 ways they want to contribute to a smarter planet are:

1. Instrument the world’s systems
2. Interconnect them
3. Make them intelligent

The following video explains how math can make our planet more intelligent. (I was worried he was going to push Internet fridges, but I was spared.)

One has to wonder – is urbanization such a great idea…?

Related posts:

1. Friday math movie – Pump up your brain
2. Friday math movie – Martin Gardner
3. Friday math movie – 2009 Halloween Math Class

Just for fun, let’s compare the tail bounds you get from the moment method with the explicit tail bound of the exponential distribution.

First, we need the moments: if then for You can compute these using induction and integration by parts. By Markov’s inequality and Stirling’s approximation,

for sufficiently large.

The derivative of the final quantity is

if we consider only the quantity in the parentheses is monotonic:

It follows that if is sufficiently large that the quantity in the parentheses is negative for some , then we can optimize the approximate tail bound by setting to be the root of the quantity in the parentheses.

If , then the root is given by the Lambert W function:

Putting it all together, the moment method gives the following tail bound for a random variable :

How does this compare to the actual bound ? Just eyeballing it, it looks like asymptotically, the moment bound gives you an exponential tail bound with a worse constant. If true, that’s pretty amazing!

Hmmm. On second thought, this is only amazing because I forgot I already worked this out in a more general setting.
Possibly relevant posts:

• Explicit Moment, Tail bound connection (3/12/2010)
• Moment generating function? (6/3/2010)
• Quick and easy route to concentration inequalities for order statistics (8/13/2009)

Martín Escardó and Paolo Oliva have been working on the selection monad and related functionals. The selection monad `S(X) = (X -> R) -> X` is a cousin of the continuation monad `C(X) = (X -> R) -> R` and it has a lot of useful and surprising applications. I recommend their recent paper “What Sequential Games, the Tychonoff Theorem and the Double-Negation Shift have in Common” which they wrote for MSFP 2010 (if you visit the workshop you get to hear Martín live). They explain things via examples written in Haskell, starting off with the innocently looking functional `ox` (which i I am writting as ox in Haskell for “crossed O”):

ox :: [(x -> r) -> x] -> ([x] -> r) -> [x]
ox [] p = []
ox (e : es) p = a : ox es (p . (a:))
   where a = e (\x -> p (x : ox es (p . (x:))))

It is just four lines of code, so how complicated could it be? Well, read the paper to find out. If you are ready for serious math, have a look at this paper instead.

The following problem is from Doctor Eco's Cyberpuzzles. I have shortened and generalized it.

We are going to put numbers into boxes. If x,y,z are in a box then it CANNOT be the case that x+y=z. If you put the numbers 1,2,...,n into boxes, what is the smallest number of boxes you will need?

You can use a simple greedy algorithm to get some partition, but it might not be optimal. The following set is not NPC (by Mahaney's theorem) but also seems to not be in P: I suspect that the following set is not NPC and not in P:

{ (n,k) : there exists a way to partition {1,...,n} into at most k boxes so that no box has x,y,z with x+y=z }

There are many variants.

{ (n,k) : there exists a way to partition {1,...,n} into at most k boxes so that no box has x,y,z with x+y=2z }

This one I know is thought to be hard- it is asking for the min number of colors so that you can color {1,...,n} and not have any Monochromatic arithmetic sequences of length 3. This is an inverse van der Warden numbers; hence I am sure that it is not in P, and that there is no proof of this, and its not NPC.

Let E be a linear equation like x+y-z=0. We represent E by its coefficients., so E would be (1,1,-1). The statement E(a,b,c)=0 means a+b-c=0. Fix E on a fixed number of variables, say a. How hard is

{ (n,k) : there exists a way to partition {1,...,n} into at most k boxes so that no box has x₁, ..., x_a with E(x₁,...,x_a)=0 }

If we do not insist the set being partitioned was {1,..,n} we get more problems:

{ (a₁,...,a_n,k,E) : there exists a way to partition {a₁,...,a_n} into at most k boxes so that no box has x₁,...,x_m with E(x₁,...,x_m)=0 } I suspect this is NPC.

One can always use the Greedy Algorithm on the above problem, though it may not give the optimal answer. Consider the following meta problems: (``the problem'' can either refer to the version where we are partitioning {1,...,n} or a given set. Hence below there are eight problems, not four.)

1. { E : For the problem with E, Greedy gives optimal }. This is in co-NP.
2. { (E,a) : For the problem with E, Greedy gives within a*optimal }. This is in co-NP.
3. { E : the problem with E is in P }
4. { E : the problem with E is NPC }

For the last two I don't even know if they are decidable.

I recently a letter from WETA (public TV) which I quote from:

This letter is quite different from any we've ever sent to you. For years we wrote to you about WETA's great programs and the need they filled in your life. Today, I must write to you about WETA's needs. And if friends like you don't respond to them, there will be far less programs to enjoy.

There is something wrong with this letter: I have gotten the exact same letter from them for about 4 years now. Hence the statement This letter is quite different from any we've send to you is not just false but verifiably false.

While I expect letters to exaggerate I do not expect to have easily verifiable lies that do not even help their cause. So why did they do this? I do not know. But whatever the reason, it is sheer incompetency. Hence I will not give to them. This raises the following question:

If a charity (or whatever Public TV is) asks for money they can exaggerate how much they need it. Should they?

1. Some readers will say GOSH, they really need the money! I better give!
2. Some readers will say They always need money. I am not going to bother.

We also have here a societal problem. Since many (legitimate) charities exaggerate about how dire their situation is or how serious their problem is, after a while it all gets tuned out. We have here a a Prisoners Dilemma problem- each one thinks (correctly?) that if they exaggerate their problems they will get more money. But if they all do it the public gets cynical and gives less money overall. (NOTE- I do not know this to be true, but I am curious. If anyone does know then let me know.)

How can they get out of this trap? I do not know. However, the least they can do is to not say things that are obviously false. There may be a well defined Game Theory or EC problem here. Or it may be a public policy problem. We won't know until its solved.

I will be sending my next book review column for SIGACT NEWS off on July 28, 2010. It has LOTS of books on its BOOKS I WANT REVIEWED list. YOU get a chance to look at the book list and request one to review before the list goes out (if you do this then I will modify the list).

Here is a link to the list of books I want reviewed HERE. If you see a book you want then email me at gasarch@cs.umd.edu the name of the book and your postal address. We will then work out details over email- when the review is due, and whether me or the publisher sends it to you. I would like you to email me before July 28 so I can take those books off the list, but if you email after that date and the book you want is still available, that will be fine.

Before volunteering you should read my advice for reviewers.

Here is a LaTeX Template.

Richard Lipton had a wonderful post asking for a seventh Millennium Prize now that Poincare's conjecture has been solved. I posted a suggestion on his blog but got no comments. I'll expand on it and see if I get any comments here.

HISTORY: The original proof of VDW's theorem , in 1927, yields INSANE (not primitive recursive ) bounds on the VDW numbers. (Shelah (1988) later got primitive recursive bounds and Gowers (2001) got bounds you can actually write down!) Inspired by VDW's proof Erdos and Turan (1936), made two conjectures:

1. If A is a subset of N of positive upper density then A has arbitrarily long arithmetic sequences. Proven by Szemeredi in 1975 (see here for more.)
2. If Σ_{x ∈ A} 1/x diverges then A has arbitrarily long arithmetic sequences. (This conjecture implies the first one.)

A proof of either of these yields a proof of VDW theorem. The hope was that it would lead to a proof with better bounds. Szemeredi's proof of the first conjecture did not yield better bounds; however, Gowers proved the first conjecture a different way that did yield better bounds on the VDW numbers.

The second conjecture is still worthwhile since it may yield even better bounds and because it is interesting in its own right. So, I propose the second conjecture of Erdos-Turan as the 7th Millennium problem. (It might need a snazzier name. The Divergence Conjecture? The k-AP Conjecture? Suggestions are welcome!)

1. Greene and Tao have already shown that the primes have arbitrarily large arithmetic progressions.
2. The work that has gone into Szemeredi's theorem and the Greene-Tao theorem spanned many areas of mathematics. Hence this is not just an isolated problem.
3. The problem has been open since 1936. Hence it is a hard problem.
4. Will more connections to other parts of math be made? Is the problem too hard? A NO answer to both of these would make it not that good a problem.
5. The converse to the conjecture is not true. Note the following set:
   
   A = ∪_{k∈ N} {2^k + i : 0 ≤ i < k }
   
   The set A has arbitrarily long arithmetic sequences but If Σ_{x ∈ A} 1/x converges.
6. Is there a plausible condition that characterizes the sets that have arbitrarily long arithmetic sequences?
7. There is already (I think) a 3000 dollar bounty on the second conjecture. So the Clay Math Institute will have to just give 997,000 dollars.

Considerable discussion about funding at CRA Snowbird. Ken Gabriel, Deputy Director of DARPA, talked about how DARPA is restructuring its programs to become more university-friendly. They've made great progress though there are still some sticky issues of project-oriented proposals and security clearances. On a related note DARPA recently announced a new Crypto Program that may be of interest to the theory community.

Peter Harsha, the CRA director of public affairs, talked about NSF funding and how the renewal of the COMPETES act almost got derailed over pornography. NSF and CISE in particular did well in the administration's budget request but there is some uncertainty as we head into the fall elections.

The best part of the snowbird meeting is networking, talking to a number of CS leaders especially at the meals and breaks. The last session was small group meetings with current deans on how to deal with our own deans. Even though I'm not a chair I do find myself dealing with my dean and his staff quite often and we were able to get some good advice on quite a range of specific issues. Our group got lucky in matching up with  Dan Huttenlocher, Dean of Computing and Information Science at Cornell, and Martha Pollack, former Dean of the School of Information at Michigan. The best general advice: have a good working relationship with your dean and don't just ask or complain but really make the case on how the particular resource you need will benefit your school.

I'll be mostly on vacation and off the net for the next couple of weeks. Be nice to Bill while I'm gone.

22 Jul 2010

In this Newsletter:

1. Math of the great summer brain drain
2. Math tip: Radius of Curvature, an application of differentiation
3. Slope of the logarithm curve at any point
4. Friday math movie – Khan’s Academy
5. How to import GeoGebra files into JSXGraph
6. Final thought – stay positive

1. Math of the great summer brain drain

Here is some interesting information about how forgetting works, and what we can do to reduce it.

Do you want to be a successful math student? This could be a good place to start.

Suitable for: Everyone.

Everyone knows students drop a few grades in their knowledge during the summer months. What’s the math behind this? Read more: Math of the great summer brain drain

2. Math tip: Radius of Curvature, an application of differentiation

I re-wrote a page on Interactive Mathematics recently and thought you may find it useful.

A reader sent in a question asking how to find the radius of curvature if we don’t know the function. I solve this problem in 3 different ways. You can get some good mathematical understanding from this.

Suitable for: Everyone. Even if you have never heard of calculus yet, you will come across it one day and this example gives you an idea about what it can be used for.

Summary of the page:

• What is radius of curvature and why study it?
• Example of radius of curvature involving a cubic curve
• Exploration of radius of curvature using an interactive graph
• A second example (the one sent in by a reader) that is solved in 3 different ways:
  1. Using a parabola to model the data and differentiation
  2. Using linear approximations and concepts of calculus
  3. Using the formula for the circle passing through 3 points

So here it is:

In this example, we learn about radius of curvature and one of its applications. Read more: Radius of Curvature

3. Slope of the logarithm curve at any point

Suitable for: Everyone. Once again, this example involves differentiation (a calculus topic), but the main concept is easy for everyone to understand: as you move around a curve, the slope changes.

This is a new interactive graph in IntMath. You can drag a point around a logarithm curve to learn about the changing slope. You’ll laso learn what a log curve looks like. Learn more: Slope of the Logarithm Function

4. Friday math movie – Khan’s Academy

Suitable for: Everyone.

Here’s a wide range of free videos by a guy that clearly loves to teach. This is a very popular math video series. Watch a typical video. This one is about the Unit Circle: Friday math movie – free math videos by Khan Academy

5. How to import GeoGebra files into JSXGraph

Suitable for: Math computer geeks.

This article explains how you can create interactive math applets using GeoGebra (which is easy) and import those files into JSXGraph (which displays the math in a browser, and is cross-platform and cross-browser). Read more: How to import GeoGebra files into JSXGraph

6. Final thought – stay positive

A lot has been written about the power of positive thinking. But it’s true!

The people who have a negative approach to math ("This is dumb!" "This is never used in the real world!") and do nothing much to improve their skills, get into a cycle where they get worse.

Here’s a thought from self-help speaker and author Brian Tracy:

"The more positive you are when you think and work toward your goals, the faster you achieve them." [Brian Tracy]

Until next time, enjoy whatever you learn.

Related posts:

1. How to import Geogebra files into JSXGraph
2. IntMath Newsletter – Overcoming fear of math tests, free calculus book
3. IntMath Newsletter: radians, graphs, math class

I was never a big fan, so I just heard that Numb3rs was canceled for the fall. I guess the law will have to go back to fighting crime the old-fashioned way: calling in Batman to help.

I just returned home from my first trip to the CRA Snowbird Conference, the biennial meeting of CS chairs and other leaders in the CS community. I really enjoyed the short meeting and saw many old friends who are now chairs, some people I've only known by email and many I've talked to for the first time. There are a few theorists who have become chairs and deans, and, in the case of Jeff Vitter, provost at Kansas. Unlike theory conferences where I am usually one of the old people, most CS chairs are just about my age.

Last week, the Center for Computational Intractability hosted a Geometric Complexity Theory Workshop. Geometric complexity theory (GCT) is an approach to P vs NP and related problems proposed by Ketan Mulmuley and Milind Sohoni, in which they were naturally led to using techniques in algebraic geometry and representation theory. This workshop was the most recent attempt to explicate GCT to both mathematicians and computer scientists, and discuss recent related results. Without looking at the attendance list, my impression was that the workshop was approximately 3/8 complexity theorists and 3/4 classical mathematicians (meaning that about 1/8 fell into both camps), and was about 1/3 students and 2/3 postdocs/professors. This turned out to be a pretty good mix.

The first two days were scheduled to be all Ketan all the time. Despite the fact that Ketan is an excellent presenter, talking for two days straight and keeping the audience interested would be a tough task for anyone. Not everyone made it to the end, but a significant fraction of the audience did. Ketan's lectures were interspersed with a lot of discussion and debate, including a couple short impromptu guest lectures from audience members on some background topics. Pointed questions came from both classical mathematicians and complexity theorists, and as often as not were answered by audience members from the other field. It was refreshing to see the humility of the giants of multiple fields: great classical mathematicians asked complexity theory questions that a complexity undergrad could answer, and vice versa. I think this is one of the few times I have ever heard of serious classical mathematicians mingling with complexity theorists, and I think it worked quite well. This type of interaction and more seems necessary for the GCT program, and can only be a Good Thing for both fields.

And now for two technical items from the workshop.

Avi Wigderson and others (sorry to the others, but Avi sticks out most in my memory, and I didn't learn everyone's names!) repeatedly suggested applying the techniques of GCT to easier problems than P vs NP and see if they can be pushed through to fruition for easier lower bounds. At the moment, GCT reduces P vs NP to certain hard conjectures in algebraic geometry and representation theory. The corresponding conjectures arising in easier lower bound problems would hopefully be easier, maybe even easy enough to solve in our lifetimes! Peter Burgisser has been looking at matrix multiplication using these techniques (an idea originally suggested by his adviser, Volker Strassen, long before GCT came along), and his student Christian Ikenmeyer gave a presentation on their results as one of the research talks on the third day.

Christian's talk was probably the most salient for complexity theorists not intimately familiar with GCT, so I'll mention a bit more about it to finish off the post. GCT introduces the idea of a "geometric obstruction" (=some type of representation-theoretic object) to "there are circuits of size n^c for SAT up to length n" (NP vs P/poly). If a geometric obstruction exists for all (or infinitely many) input lengths n, then P is not equal to NP. The conjectures arising in GCT imply that such obstructions exist. But even in smaller problems, such as matrix multiplication, no one had ever seen such geometric obstructions! Peter Burgisser and Christian Ikenmeyer did computer calculations and found geometric obstructions to the border-rank of 2x2 matrix multiplication. (The border-rank of 2x2 matrix multiplication roughly captures how many multiplications are needed to approximate 2x2 matrix multiplication, in a specific sense.) The geometric obstructions they found show that the border rank is at least 6 (it is known to be 7, by a significant algebro-geometric result of Joseph Landsberg). Although this only proved a weaker result than what was already known, for a comparatively easy lower bound (compared to P vs NP), this is an important proof-of-concept for the GCT approach of using geometric obstructions to prove complexity-theoretic lower bounds. This work also raises the intriguing possibility (also suggested in the GCT series of papers) that one might be able to "verify P neq NP up to length n" for larger and larger n, the same way people verify the Goldbach Conjecture or Riemann Hypothesis up to a certain numbers of integers/zeroes. Unfortunately, doing this in the GCT setting even up to n=10 seems to take too much time (whereas Goldbach and Riemann have been verified for millions of integers/zeroes).

Finally, I should mention even in the case of 2x2 matrix multiplication, the conjectures that arise seem almost as difficult as the ones arising in the P vs NP problem. Avi and others suggested we look at even easier problems.

UPDATE 7/20: Slides of the research talks are now available here, and videos will be added soon.

Recently I had the horrendous realization that I’ve lost whatever little origami skills that I once possessed. I was trying to entertain a bored child on the plane who speaks a little English, and I knew no German save “guten tag”. I thought I would fold a paper crane and I couldn’t! Anyway, I attended [...]

http://people.ee.duke.edu/~wrankin/misc/tensor.html

The Job Market in Theory (likely in all of academia) has more randomness and arbitrariness (are those the same?) then people may realize. Especially young PhD's who have never been to a faculty meeting where these things are discussed. The process is quite complex (is that the same as random and arbitrary?). I am NOT saying that merit plays no role. I am saying that its very hard to make a clean statement like Person X got a job an school Y because of Z.

With that in mind, I list out some criteria I have heard played a role in a hiring decision. My point is NOT to help you game the system (note that some of the factors I've heard cut both ways) nor to argue that the system is good, bad, or ugly. My point is only that the process is more arbitrary-random-complex then you might think. While its not all merit, its also not all who-you-know or politics.

I invite you to give leave comments on factors you have heard of, but to keep it civil please do not mention the people or schools involved.

1. Merit: This is itself ambiguous. More papers? Longer papers? Co-authors? How about take a sum where each summand is (number of citations)*(importance of paper)*(number of pages)/(number of coauthors). And then there is grant potential.
2. Does a postdoc have a better chance then a fresh PhD? A postdoc has had more time to increase his weighted sum mentioned under Merit, but the school KNOWS he has had more time.
3. Two-body-problems can be GOOD or BAD. Often a school does not have two positions.
4. Being a women can be GOOD or BAD (for getting a job).
5. I would like to say Being black can be GOOD or BAD (for getting a job) however since there are so few black PhD's in computer scientists applying for academic jobs, I have not heard any stories about this. (NOTE- I use the term black instead of African American since they need not be American.)
6. Being socially inept can be GOOD or BAD. How could it be good? It plays to the stereotype. He's so socially inept, he must be a genius. I DO NOT recommend pretending you are socially inept.
7. Speaking your mind can be GOOD or BAD. He'll be a leader in the community or He'll be a pain in the ass
8. Having a Blog- the jury is still out on this one. I have heard of a case where having a blog helped someone get an interview. (It was a serious blog about the field he was in. I can't imagine that complexity blog would help me get a job if I was looking.)
9. Spending too much time deciding what to have for lunch can be a negative. If he can't figure out what to have for lunch then how can he formulate a coherent research plan.
10. Area can be a factor- does a school need or want someone doing area X? This is sometimes formalized, for example the school has money targeted to hire someone who does, a particular area. (Side topic- Targeted positions- Good or Bad? Good in that you are not going to have to compare people in diff areas. Bad in that there may be someone really good in another area who you want to hire but can't.)
11. Subarea is a factor- for example, we want the kind of theorist who can talk to our people in systems.
12. Having a champion in the dept who is helping push your case HELPS unless the person doing the pushing is a jerk or not good at pushing a case.
13. Being an ex-convict probably hurts. If there was a theory genius who served 10 years in jail, that might be a negative. Might be mitigated if he could pull in some serious grant money. However, if the jail term was for embezzling grant money, then maybe not. Actually, the whole question might depend on what he was in jail for and is he now reformed.
14. A very big factor is how good is the job market when you get out. This may be a much bigger factor than anything else on this list.

As most of you are taking a break from math or school work, here's a little (addictive) math game to play online or as printed version: Kenken.

In it, you have to place the numbers in the grid kind of like in Sudoku so that no number appears twice in the same row or column, BUT there's an additional twist: it gives you "cages", and the numbers within a particular cage have to work to a given answer with a given math operation (either addition, subtraction, multiplication, or division).

KenKen practices logical thinking and is, I think, more fun than Sudoku.

It's easier to understand if you go see and try it yourself. The smaller sizes, such as 4x4 game, are great for kids, and the larger ones are good for us adults or older students.

• Kenken.com has nice Kenken puzzles online plus instructions, but only one for each size.

• MathDoku.com has an unlimited number of Kenken puzzles to play online in three sizes and several difficulty levels.

What do you get out of this paragraph (from Charlie Stross' The Atrocity Archives via Daniel Lemire)

The [Turing] theorem is a hack on discrete number theory that simultaneously disproves the Church-Turing hypothesis (wave if you understood that) and worse, permits NP-complete problems to be converted into P-complete ones. This has several consequences, starting with screwing over most cryptography algorithms—translation: all your bank account are belong to us—and ending with the ability to computationally generate a Dho-Nha geometry curve in real time.

I get a new homework question.

Show that NP-complete = P-complete if and only if NP = L.

Wave if you solve it.

(This post is similar to this old post. I am posting this anyway since when I first posted I made fundamental mistake. I fixed it the point I was trying to make get lost.)

About once a semester I get asked

What are the natural problems that are in NP, not known to be in P, and not known to be NPC? What is known about them?

And I give the standard answers:

1. Graph Isomorphism. If its NPC then PH collapses so it is though to NOT be NPC. There is no real consensus about its status with respect to P.
2. Factoring. If its NPC then NP=coNP so it is thought to NOT be NPC. Most people think that it is NOT in P since people really want to solve this one and have not been able to. This is not a rigorous argument. Factoring is in QP. If quantum computers are ever practical then we may need to rethink how we think about these things.
3. Discrete Log. Actually, are there reasons to think this is NOT NPC?

The answer above are standard and I suspect most of my readers know them. However, there is a large source of problems that are in NP, likely not NPC, likely not in P, that people don't seem to talk about much: SPARSE PROBLEMS that are thought to be hard. The ones I know about are from Ramsey Theory. I give one example but there are many like it:

{(1ⁿ,1^m,c) : the n×m grid can be c-colored and not have any mono squares}

1. This is clearly in NP since the coloring itself is the witness.
2. Since this is a sparse set it is not NPC unless P=NP. (Actually it can be coded as a tally set.)
3. I want to say People think this is hard. You may ask Name Three of Them! Indeed, the number of people who work on Computational Ramsey Theory is fairly small. However, Ramsey Theory itself has many people working on it and nobody has anything close to a result indicating that this problem is in P. I personally think that it is hard.
4. For a fixed c there is a finite number of grids G1,...,Gp such that the n×m grid is c-colorable iff none of G1,...,Gp can fit inside the n×m grid. Hence, for fixed c, the problem is in P. (So the problem is Fixed Parameter Tractable.)
5. Everything said above holds if you replace squares with rectangles or other configurations in the above.

Questions:

1. Are there other sparse problems in NP that we think are NOT in P? (that is, ones that DO NOT come from Ramsey Theory).
2. Should we be teaching these in our complexity classes as examples of possible intermediary problems? The proof that they are likely not NPC is easy. However, to argue that these problems are likely not in P is hard. Also, these problems may appear unnatural to some students. (They may appear unnatural to some of my readers.)
3. It is easy to argue that Factoring is probably not in P since you can point to the fact that people REALLY want to solve it quickly and so far have not. This is not a rigorous argument but I do count it as evidence. Is there a similar argument for GI? Is there a similar argument for my Ramsey Problems?
4. Is there a mathematical reason to think that Factoring, GI, or my Ramsey Problems are not in P?

Occasionally I’ll find myself looking for some way to pass a note to myself. Say I’ll come across a reference to a paper while using the internet from home, and want to store the link until I can access the paper through the school’s online subscriptions. When it was free, I used backpackit.com, although it was a hassle to have to login and deal with the structure they imposed on my notes. Lately I’ve been using google docs, but that involves a lot of overhead to login and then navigate to the documents I use for note taking, and the interface doesn’t make note taking a comfortable experience.

Tonight I discovered a new site, www.aypwip.org/webnote, which is almost perfect. To access your note workspace, you simply enter the name at the front page; there’s no validation needed, since you could ostensibly give your workspace an obscure or random name. If the site supported embedded pictures, live links, and LaTeX, it would be perfect for my needs. The source code is also available, so you can roll your own modifications in.Possibly relevant posts:

• Scanning in books (10/6/2004)
• MIT Open Courseware (10/29/2003)
• Internet road trip (9/27/2002)

Let denote the spectrum of an invertible matrix. Here’s the question: if is contained in the upper open half plane and is a projection matrix, then is contained in the upper closed half plane?

This is turning out not to be a straightforward problem (or maybe I just don’t see the easy way to go about this), so I ran a dozen or so Mathematica experiments with random and . The results suggest that the implication is true, but it may be the case that it’s simply true with high probability for random matrices:

In this example is 1000×1000, is rank 500, red points are in the spectrum of , and blue are in the spectrum of . For smaller rank projections, the red rectangle is still centered, but smaller. It’d be interesting to quantify the behavior of the spectrum for random but fixed … but let’s not get off track.

BTW, I *did* run the simulation for smaller sized in case the ‘everything performs better with higher dimensional random matrices’ deal was going on, and it doesn’t look like that’s the case.Possibly relevant posts:

• Almost Isometries and Singular Values (7/8/2010)
• Max-min property and an application (2/9/2010)
• Spectral Mapping Theorem (6/14/2006)

Consider a fixed projection and a random matrix , then you’d expect that for some Here’s a proof:

First, use a taylor series expansion to get the recursive relationship

In the final line, and where is an matrix with orthonormal columns, given by the SVD of . Likewise

This decomposition implies that is block diagonal in the basis given by :

Take the log of both sides and factor out the unitary matrices to see

so

Possibly relevant posts:

• Almost Isometries and Singular Values (7/8/2010)
• Trace dual of the norm (1/19/2010)
• Puzzled by holomorphic functions of a matrix (7/13/2010)

Eugene Lim went to Haiti after the earthquake to teach calculus after the earthquake. He has posted a first-hand account at Cosmic Variance.

Ok, explain this to me: Epstein gives the following definition of what it means to take when is a symmetric matrix whose spectrum lies in the domain of holomorphiticity of (if that’s the correct phrase to use)

where is a contour surrounding the spectrum of .

Then he defines for on the cut plane by the formula

and immediately turns around and states that this implies that if is positive then

How, if at all, does this follow from his original definition? And where can I read more about the details of this kind of complex analysis on algebras? ( I’m only interested in the matrix case, but general theory is better than none)

Update:
I think I get it now. I think the issue is that is not uniquely defined in general, so the integral expression is used to get a unique analytic continuation on the cut plane, then you can proceed as usual:

The only noteworthy part of this is that the definition of he gives is equivalent to the usual diagonalization definition which is easier to work with.Possibly relevant posts:

• Almost Isometries and Singular Values (7/8/2010)
• Dual of an inequality and equality constrained SDP (2/26/2010)
• Cumulants of projected random matrices are projected matrices (7/12/2010)

Someone said that he thinks a paper is more credible if there are coffee stains on it. Well, here’s the solution - a latex package.

There are lots of nice videos out there which would be ideal to show to students before lectures or during breaks just to break the monotony. Here’s one about Fibonacci numbers and nature that’s pretty impressive, although I don’t think one will learn much maths from it.

I need to learn some stuff. I’m trying to understand what is essentially the simplest proof of one of Lieb’s inequalities:

If is self-adjoint, then is concave on the positive-definite cone.

The simplest proof seems to be Epstein’s, as summarized in (just one page!) Appendix A of Ruskai’s paper.

I follow the gist of the proof, but when it comes to justifying statements like “ can be extended to an analytic function on the upper half plane”, I’m plain stumped. Also, what does that integral expression for where is an analytic function mean? (should I diagonalize A and use Cauchy’s theorem on each entry on the diagonal, and interpret the division by a matrix as inversion?)

The language of this synopsis is tantalizingly suggestive, yet alien enough that I can’t quite move from my intuitive understanding to a solid technical grasp of each step.

I’m trying to follow the proof because I’d like to prove that if I pinch the exponentiated term with an arbitrary projection then you get the generalization: is concave on the positive-definite cone. I think that from Ruskai’s description of Epstein’s proof, this is trivially true— you end up with mapping from the upper half plane into the closed upper half plane, but apparently that is sufficient for the function to be a Pick function and have that convenient integral expression.

If anyone’d like to confirm that, I’m all ears Possibly relevant posts:

• Puzzled by holomorphic functions of a matrix (7/13/2010)
• 1-forms and topology (7/27/2007)
• Two ways of doing cool stuff with matrices (2/27/2007)

This is a bit different entry from the norm, and if you're not interested in music (or oldies music), just ignore it. (I realize people's musical tastes vary tremendously.) I just wanted to share a bit of news of my favorite, 24K Gold Music Shows, and their new YouTube channel. They mainly play music from 50s and 60s; that is, oldies music.

(Well, I do also like classical music pretty well -- I played piano in my youth for 13 years, and still occasionally do at home.)

You can now see 24K Gold music videos at YouTube. For example (click on the song links to see these in high density):


Cara Mia (my favorite!):


Love Can Build a Bridge (a beautiful ballad with a strong emotion):


Or something faster such as Elvis' Burning Love:




Johnny B Goode



See more videos - or subscribe at their channel page.

Just attended a nice talk by Erik Demaine on Origami and puzzles. He demonstrated some remarkable stuff and ended with a cute picture hanging puzzle - how to hang a puzzle with two nails such that by removing either one, the picture drops. A brief description is at the end of the following paper http://erikdemaine.org/papers/FUN2004i_TheoryComputSys/paper.pdf and a [...]

1. Is it possible for someone to be denied Full Prof? Yes, but it is rare.
2. Is it possible for someone to fail a PhD defense? Yes, but it is rare.

These questions are similar. Why might either happen?

1. I suspect that the most common reason for someone to be denied Full Prof is that they went up without the Chairman's or the Departments approval. That is, they insisted on going up. I really cannot see a reason for a professor to do this except some sort of bad logic which I will discuss later.
2. I suspect that the most common reason for someone to fail a PhD defense is that they insisted on defending even though the advisor didn't think they were ready. While the advisor should have stopped it there may be other reasons (e.g., a job offer to the student has been made so he really needs the PhD NOW, or some deadline is coming up) that came into play. Could also be bad logic which I will discuss later.
3. Could also be because of politics. I've heard of this happening but never really saw a case I could verify myself. One problem: Everyone who is ever denied Tenure or Full Prof says that it was political. Hence its hard to tell when it really is.

BAD LOGIC:

1. A prof might think Everyone who I've ever seen go up for Full Prof has gotten it, so all I need to do is go up for it.
2. A student may think Everyone who I've ever seen defend their thesis has passed so all I need to do is get a defense scheduled. I have seen the following: nobody fails a defense for several years because the adviser don't put you up until you defend. Then the mentality sets in that all you need to do is defend and you'll pass. Then someone pushes this and ends up failing. THEN people are scared for the next few years, until its forgotten. That is why someone fails a PhD defense every 6 years or so.

WHY DENY SOMEONE FULL PROF? If you deny someone TENURE they LEAVE. Hence something is accomplished. But if you deny someone Full Prof they are still there, just annoyed. Hence it seems like a really bad idea to deny someone Full Prof.

WHY DO YOU WANT TO BE A FULL PROF? Salary increase? My school is now not giving raises. You get to write letters for more people. Is this really a good thing? You get to be on more committees. Is this really a good thing? You get more respect? This is questionable. People stop asking So, are you a full prof yet? This is a good thing.

HOW BAD IS IT: In both cases you can re-do. That is, you can come up for full prof later and you can fix your thesis and defend later. Even so, it can be a trauma.

FYI: I passed my PhD defense first try in May of 1985. I got Assistant prof in 1985, Associate Prof (Tenure) in 1991, and Full Prof in 1998.

Mark Chu-Carroll, the math blogger at ScienceBlogs, has quit the site, after ScienceBlogs made the bizarre decision to host a blog sponsored by Pepsi. The ensuing blow-up has caused ScienceBlogs to pull the Pepsi blog, Food Frontiers, but a version of it lives on at Pepsi’s own site.

I bought two clamshells of strawberries last week, and never got around to consuming them. Today I started to make lemonade and realized this was the perfect chance to put them to use, and try my hand at something new. Boy did this turn out good!

Here’s my recipe for strawberry lemonade: You’ll need four cups of water, a cup of brown sugar, a half pound of strawberries (half a clamshell’s worth), a cup of fresh lemon juice, and about a tablespoon of the peel from the lemons. Heat two cups of the water to boiling, dissolve in the brown sugar, add the peel, and let the mixture cool. Hull and puree the berries, then mix the puree, the sugar mixture, the lemon juice, and the remaining two cups of water. Refrigerate the mixture until cold, then strain it to get rid of the peel and any remaining chunks of berry flesh.

This is delicious, but very much on the sweet side. You may want to halve the sugar.Possibly relevant posts:

• Spicy Pesto Lasagna (6/3/2009)
• Successful culinary experiments (9/30/2008)
• Bajan Food Part I: Sweets (11/3/2008)

After thinking about it a bit, I thought there must be some results in the literature that would allow me to get bounds like in the last post much quicker. I mean, that problem seems like one that lots of researchers must have run into before, and basic enough that there should be results recorded in standard matrix theory texts. After a not so careful search of Bhatia, I came up with a quicker way of getting slightly weaker bounds.

The upper bound follows from the simple relationship ; this bound is as strong as the one I found. The lower bound follows from the same inequality by considering that is the inverse of , so , which gives the weaker lower bound

I wonder if there’s a quick way to get the optimal lower bound, or if there’s a standard reference for it…Possibly relevant posts:

• Moment generating function? (6/3/2010)
• Almost Isometries and Singular Values (7/8/2010)
• One more reason why projections with controlled condition numbers are useful (8/24/2009)

Given a matrix with SVD and a conformal (wide) matrix which is almost an isometry (the spectrum of is in a small interval bounded away from zero), I’m interested in relating the spectrum of to that of Precisely, I’d like to establish relations like where are related to the unprimed quantities and possibly (in as weak a way as possible) the spectrum of .

The upper bound is surprisingly easy to get at:

where is an almost isometry with the same constants as Apply the Courant-Fischer-Weyl formulation:

If you apply the other Courant-Fischer-Weyl formulation,

where “” refers to the smallest eigenvalue over the range of , and in the last expression is the particular projection matrix

Now notice that

So it turns out that almost isometries treat all the singular values of a matrix rather nicely: .

Possibly relevant posts:

• Cumulants of projected random matrices are projected matrices (7/12/2010)
• Puzzled by holomorphic functions of a matrix (7/13/2010)
• Dual of an inequality and equality constrained SDP (2/26/2010)

It looks like Joel and I (mostly Joel, of course) may have come up with a way to bound the interior eigenvalues of a broad class of random matrices, something that apparently has not been done in such generality or usefulness—viz, the bound is non-asymptotic—before. It looks like they concentrate normally. Super exciting, if it turns out to go through completely.

I’m going to work on that tomorrow, but for today, I have completed the thought behind the error bound for using the fast randomized svd power method with column sparsification. I’m going to spend the next hour or so consolidating that, then I’ll take the rest of the day off. Maybe go get some frozen yogurt, watch some Hulu, and just generally enjoy the end of a successfully (finally!) completed project. Possibly relevant posts:

• Planning a talk on random matrix inequalities (6/2/2010)
• Nyström method (for low rank approximation) (6/28/2010)
• Progress on NNLS (9/27/2009)

a conflict-of-interest? Some thoughts.

Thought One

PROF: I can't vote on Professor X's Full Prof case since I have a conflict.

CHAIRMAN: (There are not that many Full Profs around so he is concerned about having a quorum.) Really? Whats your conflict?

PROF: My wife works as an F.R.A (Faculty Research Assistant) for Prof X.

CHAIRMAN: Is that really a conflict?

PROF: (Surprised) Uh--- I really think it is.

CHAIRMAN: Which way would it bias you?

PROF: (Even more surprised) I don't think that matters.

The odd thing is that it really is hard to say which direction it would bias PROF in. Does the wife like her job? Does she know that the prof is really good at what he does? Really bad at what he does? It could go in any direction.

Thought Two

I have reviewed two books that my advisor wrote in my SIGACT NEWS column. For his excellent books BLOWN TO BITS I have at the beginning of the review:

Disclaimer: Harry Lewis, one of the authors, was my PhD advisor.

That seems fair. However, the reader may wonder which direction the bias goes. In my case I thought Harry was an excellent advisor (Disclaimer: I also know that he reads this blog). But what if I thought he was a terrible advisor? I wonder if the reader has a right to know which direction the conflict goes in. Perhaps disclaimers should be of the following form.

Disclaimer: Harry Lewis, one of the authors, was my PhD advisor; however, I believe this review is unbiased.

Disclaimer: Harry Lewis, one of the authors, was my PhD advisor; He was an AWESOME advisor. Hence this review may be positively biased.

Disclaimer: Harry Lewis, one of the authors, was my PhD advisor; He was a TERRIBLE advisor. Hence this review may be negatively biased.

(The advantage of the last one is that if it is a positive review then the book must be really really good.)

Thought Three

Lets say I was having the NSF theory director over to my house for dinner on his birthday. Since he may give me a grant someday, should I charge him for it? How about a compromise- he pays for the dinner but I pay for desert. I think the rule may be that I can spend less than ten dollars over the course of the year. (Richard- I hope you enjoyed your birthday desert, since that's it for the year.)

At a CCC Council meeting last week, a common theme emerged. The Army is "swimming with sensors and drowning in data". Biologists are considering trashing some of the DNA sequences they have already acquired because it will likely be cheaper to resequence in the future maintain the current data. We've been collecting tons of information, what should we do with it and if we don't have the tools yet to deal with all this data, should we bother keep it?

This reminds me of one of my favorite homework problems in complexity: Given two log-space computable functions f and g (the read-only input tape and write-only output tape don't count for space), show that the composition f(g(x)) is also log-space computable. The direct approach doesn't work for you don't have the space to store g(x).

The solution is to recompute the bits of g(x) as you need them. The lesson: When storage is expensive, it is cheaper to recompute what you've already computed. And that's the world we now live in: Storage is pretty cheap but data acquisition and computation are even cheaper.

So who says complexity has nothing to say about the real world?

Within CS theory who ended up at what jobs? Neither Lance nor I knows this. But YOU do--- collectively! So, I ask you, the readers, to leave comments about who ended up where. Please include name, where they came from, where they are going to, and what position they were hired in, what they work in (fairly broad- e.g., algorithms, complexity). For all of this if you don't know then still leave a comment. Only post comments that you know are true. I only want to list theorists; however, my definition of theorist is fairly broad. Use your own judgment.

I'll start it off by stating two hires I know about:

1. MohammadTaghi Hajiaghayi: He was at AT+T but will be at The University of Maryland at College Park in the fall, hired as an assistant professor. He works in Algorithms of all kinds.
2. Hector Bravo. He was a postdoc at Hopkins but will be at The University of Maryland at College Park in the fall, hired as an assistant professor. He works in computational biology.

Unprovable Propositions
Among other things, Godel's first incompleteness theorem allows us to construct a statement in the language of Peano arithmetic that can't be proved using the axioms of Peano arithmetic. Unfortunately, this statement is a highly contrived proposition whose sole purpose is to be unprovable. People who learn of Godel's theorems often ask if there are other more natural and uncontrived mathematical statements that can't be proved from the Peano axioms.

My goal in this post will be to describe one of these propositions. Not just uncontrived, but actually very useful. I only intend to tell half of the story here because I feel like there are many good treatments already out there that tell the rest. I'm just going to get to the point where I can state the unprovable proposition, and then sketch how it can be proved if you allow yourself a little Set Theory.

> {-# OPTIONS_GHC -fno-warn-missing-methods #-}
> import Prelude hiding ((^))
> infixr 8 ^
> type Natural = Integer

Termination
Suppose we implement a function to compute the Fibonacci numbers like so:

> fib 0 = 0
> fib 1 = 1
> fib n = fib (n-2) + fib (n-1)

How do we know that fib terminates for all natural number arguments? One approach is this: if we pass in the argument n it clearly never recurses more than n levels. Each time it recurses it calls itself at most twice. So it must terminate in O(2ⁿ) steps (assuming that the primitive operations such as addition take constant time). We can think of this code in a kind of imperative way. It's a bit like n nested loops, each loop going round up to two times.

Suppose instead that we have some kind of recursive function g that goes n levels deep but for which the number of calls of g to itself is no longer two. In fact, suppose the number of self-calls is very large. Even worse, suppose that each time g is called, it calls itself many more times than it did previously, maybe keeping track of this ever growing number through a global variable. Or instead of a global variable, maybe an evil demon decides how many times g calls itself at each stage. Can you still be sure of termination?

A Simple Machine
In order to look at this question, we'll strip a computer right down to the bare minimum. It will have an input (that the evil demon could use) for natural numbers and will output only one symbol. Here's a design for such a machine:

> data Machine = Done | Output Machine | Input (Natural -> Machine)

A value of type Machine represents the state of the machine. Done means it has finished running. Output s means output a symbol and continue in state s. Input f means stop to input a number from the demon (or elsewhere), call it i, and then continue from state f i. This is very much in the style discussed by apfelmus and I in recent blog posts.

Here's an interpreter for one of these machines:

> run1 Done       = return ()
> run1 (Output x) = print "*" >> run1 x
> run1 (Input f)  = readLn >>= (run1 . f)

For any n we can easily build a machine to output n stars. This is such a natural machine to want to build it seems only right to give it the name n. If we want to do this then we need to make Machine an instance of Num and define fromInteger for it:

> instance Num Machine where
>    fromInteger 0 = Done
>    fromInteger n = Output (fromInteger (n-1))

Typing run1 8, say, will output 8 stars.

Now given two of these machines there is a natural notion of adding them. a + b is the machine that does everything b does followed by everything a does. (Remember, that's b then a.) To do this we need to dig into b and replace every occurrence of Done in it with a. That way, instead of finishing like b, it leads directly into a. In the case of a + Input f, for each number i we need to dig into f i replacing each Done with a:

>    a + Done     = a
>    a + Output b = Output (a + b)
>    a + Input f  = Input (\i -> a + f i)

There's a natural way to multiply these machines too. The idea is that in a * b we run machine b. But each time the Output command is run, instead of printing a star it executes a. You can think of this as a control structure. If n is a natural number then a * n means running machine a n times. In the case of a * Input f, instead of multiplying by a fixed natural number, we get an input from the user and multiply by f i instead:

>    _ * Done     = Done
>    a * Output b = a*b + a
>    a * Input f  = Input (\i -> a * f i)

We can make a machine to input a number and then output that many stars. Here it is:

> w = Input fromInteger

Try running run1 w.

Can you guess what the machine w * w does? Your first guess might be that it inputs two numbers and outputs as many stars as the product of the two numbers. Try it. What actually happens is that we're computing w * Input fromInteger. Immediately from the definition of * we get Input (\i -> w*i). In other words, the first input gives us an input i, and then w is run i times. So if we initially input i, we are then asked for i more inputs and after each input, the corresponding number of stars is output. Although the original expression contains just two occurrences of w, we are required to enter i+1 numbers.

Given the definitions of + and * it seems natural to define the power operation too:

> (^) :: Machine -> Machine -> Machine
> a ^ Done     = Output Done
> a ^ Output b = a^b * a
> a ^ Input f  = Input (\i -> a ^ f i)

The power operation corresponds to the nesting of loops. So, for example, w ^ n can be thought of loops nested n deep.

Try working out what w ^ w does when executed with run1.

Consider the set M of all machines built using just a finite number of applications of the three operators +, * and ^ to w and the non-zero naturals. (The non-zero condition means we exclude machines like 0*w that accept an input and do nothing with it.) Any such expression can be written as f w, where the definition of f makes no mention of w.

Suppose we use run1 and we always enter the same natural n. Then each occurrence of w acts like n. So if we start with some expression in w, say f w, then always inputting n results in f n stars. We could test this with run1 (w^w^w^w), always entering 2, but it would require a lot of typing. Instead we can write another intepreter that consumes its inputs from a list rather from the user (or demon). And instead of printing stars it simply prints out the total number of stars at the end:

> run2 Done    _        = 0
> run2 (Output x)   as  = 1 + run2 x as
> run2 (Input f) (a:as) = run2 (f a) as

Now you can try run2 (w^w^w^w) [2,2..] and see that we (eventually) get 2²²².

Termination Again
If we run a machine in M there's a pattern that occurs again and again. We input a number, and then as a result we go into a loop requesting more numbers. These inputs may in turn request more inputs. Like the mythological hydra, every input we give may spawn many more requests for inputs. As the number of inputs required may depend on our previous inputs, and we may input numbers as large as we like, these machines may run for a long time. Suppose our machine terminates after requesting n inputs. Then there must be some highest number that we entered. Call it m. Then if the original machine was f w (with f defined in terms of the 3 operators and non-zero naturals), the machine must have terminated outputting no more than f m stars. So if our machine terminates, we can bound how many steps it took.

But do our machines always terminate? The input we give to the machine might not be bounded. If we run run2 (w^w) [4,5..], say, the inputs grow and grow. If these inputs grow faster than we can chop off the heads of our hydra, we might never reach termination.

Consider a program to input n and then output fib n. It accepts an input, recurses to a depth of at most n, and calls itself at most twice in each recursion. Compare with the machine 2 ^ w. This accepts an input n, recurses to a depth n, calling itself exactly twice each time. So if 2 ^ w terminates, so does fib. The more complex example above where I introduced the evil demon will terminate if w ^ w does, as long as the demon doesn't stop inputting numbers. So if we can show in one proof that every machine of type Machine terminates, then there are many programs whose termination we could easily prove.

Let's consider an example like run1 (w ^ w) with inputs 2, 3, 4, ...

We start with w ^ w. Examining the definition of the operator ^ we see that this proceeds by requesting an input. The first input is 2. Now we're left with w ^ 2. This is w * w. Again it accepts an input. This time 3. Now we go to state w * 3. This is w*2 + w. Again we accept an input. This time 4. We are led to w*2 + 4. This now outputs 4 stars and we are left with w * 2 which is w + w. We accept an input 5, output 5 stars and are left with w. After a further input of 6, it outputs 6 stars and terminates. Or we could just run run2 (w ^ w) [2,3..] and get 15(=4+5+6) as output.

The transitions are:
w ^ w
-> w ^ 2
-> w * w
-> w * 3
-> w*2 + w
-> w*2 + 4 -> ... -> w * 2
-> w + w
-> w + 5 -> ... w
-> 6 -> ... -> 0.

Now for some Set Theory. Rewrite the above sequence using the transfinite ordinal ω instead of w. The sequence becomes a sequence of ordinals. Any time we accept an input, the rightmost ω becomes a finite ordinal. So we have a descending sequence of ordinals. This is true whatever ordinal we start with. The execution of either Input or Output always strictly decreases our ordinal, and any descending sequence of ordinals must eventually terminate. Therefore every machine in M eventually terminates.

But here's the important fact: to show termination we used the ordinal ω, and this required the axiom of infinity and some Set Theory. Instead we could encode the termination question, via Godel numbering, as a proposition of Peano arithmetic. If we do this, then we hit against an amazing fact. It can't be proved using the axioms of Peano arithmetic. So we have here a useful fact, not a contrived self-referential one, that can't be proved with Peano arithmetic.

Why can't it be proved using just the Peano axioms?
A few years back, Jim Apple made a post about constructing (some) countable ordinals in Haskell. His construction nicely reflects the definitions a set theorist might make, but the code doesn't actually do anything. Later I learned from Hyland and Power how you can interpret algebraic structures as computational effects. apfelmus illustrates nicely how an abstract datatype can be made to do things with the help of an interpreter. Roughly speaking, doing this is what is known as operational semantics. So I thought, why not apply this approach to the algebraic rules for defining and combining ordinals. The result are the interpreters run1 and run2 above.

run1 gives an example of a Hydra game. In fact, its precisely the hydra game described in this paper because it always chops off the rightmost head. The Kirby-Paris theorem tells us we can't prove this game terminates using just the Peano axioms. A web search on Goodstein's theorem will reveal many great articles with the details.

A well-ordered quantity that you can keep decreasing as a program runs, and that can be used to prove termination, is an example of a loop variant. Loop variants are often natural numbers but the above shows that transfinite ordinals make fine loop variants. But in the interest of being fair and balanced, here's a dissenting view. The author has a point. If you are forced to use transfinite ordinals to show your program terminates, the age of the universe will probably be but the briefest flicker compared to your program's execution. On the other hand, if you don't want an actual bound on the execution time, ordinals can provide very short proofs of termination for useful programs.

(By the way, this article is a sequel to my own article.)

Exercise
Algebraic structures give rise to monads. Can you see how to generalise the definition of Machine to make it a monad? If you pick the right definition then the substitution of a for Done in the definition of + should give you a particularly simple definition of ordinal addition. (See this for a hint on how substitution works in monads.)

> instance Show Machine
> instance Eq Machine
> instance Ord Machine

I recently received Math Jokes 4 Mathy Folks from the author, Patrick Vennebush. This is a very comprehensive collection of math-related jokes that all "mathy" people will definitely enjoy, and math teachers could use this book to enliven their lessons.

I have seen several of the jokes on the Internet, but never such a large collection.

The jokes are categories into chapters such as

• One-Liners, ("A hungry clock goes back four seconds.")

• Graphic Jokes, (For example, "Cube Roots" picture you see on the cover of the book.)

• Three Dudes, (An engineer, a mathematician, and a chemist are...)

• Conversion Chart, (10⁹ antics = 1 gigantic, or 454 graham crackers = 1 pound cake)

• Professions,("The secretary of defense informed the president, 'Yesterday, three Brazilian soldiers were killed. 'Oh, no!' the president exclaimed. ... 'How many is a brazillion, anyway?' ")

And so on.

In each section, the jokes that require the least math knowledge to understand are first, and then the material "advances". People who have studied math in college will get the most out of it, but there are joke for every level.

Please note the author has included a few bathroom jokes and a few slightly dirty ones - if you don't like those, they can easily be marked over.

FOCS accepts, abstracts and PDFs. The conference itself will be held October 23-26 in Las Vegas.

There is a proposed TCS version of Math Overflow, a Q&A site to let the crowd help your research. The site needs your commitments or it won't happen. More on the Geomblog.

I plan a post about NSF goings on after some expected announcements of new programs and personnel but just a reminder that the CAREER deadline is fast approaching, July 20 for CS.

Consider the following problem:

A hole is drilled through the center of a sphere. The cylinder-with-caps is removed. The length of the removed cylinder (it also has caps on it which do not count for the length) is 6 inches. What is the volume of the remaining solid?

There are two ways to do this problem.

1. Here is the solution using calculus:
2. Here is a solution which you may consider cheating. The very asking of the question implies that the answer can be determined from the data given. Hence we can CHOOSE an instance of the problem and KNOW that our solution for this instance is always the solution. We choose to have a cylinder of radius 0 (so its just is a line of length 6). Hence the answer is the Volume of a Sphere that is 6 inches in diameter: (4/3)(π)3³=36π.

There are two ways this may be considered is cheating.

1. Minor one: Deriving the volume of a sphere itself requires calculus so I didn't really get around that issue. However, the Volume of a sphere is well known so I think this is a quibble. (Does anyone know a non-calculus proof for the formula for the the volume of a sphere?)
2. Major one: We used the fact that the answer can be determined from the data to find the answer. Is this appropriate?

How would you grade this if given as an answer on an exam? Here are some thoughts:

1. If you put this on an exam what would you do if a student had this solution? Reward them for thinking outside the box or penalize them for not showing they know calculus?
2. What if it was on a mathematics competition?
3. Best solution might be to make it a multiple choice question so they do not need to show how they did it. Those that think of the clever solution are rewarded by spending less time on it--- unless it took them a long time to think of the clever solution. Those that do it via calculus also get it right. You might want to make one of the choices Cannot be determined from the data given.

Nicole Immorlica reports on the NSF CISE Broader Impacts Summit held last week in DC.

We've all seen it. Most of us have even written one. I'm talking about that ``clearly marked paragraph'' in the summary page of each and every NSF proposal:

Broader Impacts This proposal has far-reaching impacts. As part of my program, I will develop a new graduate course entitled My Research Area, that will introduce students to cutting-edge research in Proposal Topic X, Y, and Z. I will also incorporate these lectures into some of my Undergrad Courses. Special attention will be given to recruiting Women and Minorities. And I may even talk to A High School Student once in a while. Yada yada.

As often written, these broader impact sections, like the one above, read like the teaching section of my job description. So then, what is a broader impact, really? How can we improve our impact? And, most importantly, why should we, as a community, care?
I am now on an airplane returning from an NSF summit organized by Tracy Camp, Juan Gilbert, Judy Goldsmith and Samir Khuller (kudos to you) that discussed just that. The summit consisted of about 100 members of the CISE research community, and the purpose was to collect input from us about what we want broader impacts to be and how they should work. My working group was tasked with fleshing out Broader Impact #4, ``Broad Dissemination and ...'' (who knew, there are in fact five types of broader impacts, contained in a bulleted list in some NSF document from 2007, and yes, they all have long unmemorable bureaucratic names). Here's what we had to say (disclaimer: all comments are colored by my own personal biases and are not intended to accurately reflect the opinions of the participants etc. etc.):

1. What is a broader impact? All sorts of really cool things count here. In our group on broader dissemination, we came up with: blogging, YouTube video clips, maintaining wiki pages, writing a textbook, a popular science book, directing a play about science, designing a museum exhibit building computers with kids, with senior citizens, talking directly to the curious public in Scientific Cafe, with K-12 at National Lab Days, talking to the media, writing your representatives... Many of these have been done before, and I think there will be a link on the NSF website sometime soon giving pointers to some wonderful examples. More generally, a good broader impact is realistic and, ideally, measurable — points which ought to be discussed in the proposal.
2. How can we as a community help our individual members improve their impact? Some people have an internal fire that is fueled by helping others, and for those we can enable their impacts by simply making it easier to give. For this, the NSF will provide lists of ideas, and several programs like National Lab Days and BPC further help by providing ``match-making services'' that give a searchable interface to existing outreach opportunities (looking around there, I found a local high school that wants someone to come talk about careers in science, for example). Then there are also carrots and sticks. The carrots are higher weight for broader impacts in the review process as well as the tenure process (ummmm, I'll believe it when I see it); and the sticks are holding PIs accountable for their proposed impacts through annual reports alongside a threat of withheld funding upon failure to attempt said impacts (spank spank).
3. Why should we care? If you haven't figured it out by now, I am an incredibly cynical and suspicious individual. While I personally care about certain types of community service, I nonetheless felt that broader impacts in a proposal were simply a nod to Congress, a necessity that allows our elected representatives to justify giving us hundreds of millions of tax dollars, and of minimal importance in funding decisions and career success. I now see that, while there is a certain grain of truth in my snide remarks, the NSF is on a serious mission to change all this, and we should be too. We have a passion, and as privileged members of humanity, we have a duty to share our passion with those around us, thereby enriching their lives as ours were enriched for us by circumstance and chance and past generations of great givers.

Some random thoughts about quiz shows.

THOUGHT ONE: There could be a quiz show based on P and NP. We all think that FINDING an answer is harder than VERIFYING an answer. We use this! The contestant gets a question (or perhaps a category of questions) and is asked

P or NP ?

NP means that they will try to ANSWER the question. P means they will get to hear a POSSIBLE answer and VERIFY IT. NP is worth more money, perhaps alot more. How to verify?--- a few ways are possible.

1. The host gives the correct answer and the contestant either says (1) OH, I knew that- here is how I knew it (and then gives an explanation of how they knew that). Thus the contestant must verify that he can verify. If so, they get some money. If not then perhaps a bit penalty like lose ALL of their money or get an electric shock. (2) OH, I didn't know that. No money but no penalty.
2. Hook the contestant to a lie-detector and if they say claim Oh, I knew that and they are not lying then they get some money. If they claim they knew it and are lying then they are already set up to get an electric shock, so do that.

Get the audience to yell NP! NP! NP! --- rooting for the contestant to GO FOR THE BIG MONEY!

Could there be quiz shows based on other complexity classes?

THOUGHT TWO: On the show Cash Cab after contestants have finished they can either WALK AWAY (with money that is usually between 400 and 1500 dollars) or risk it on a DOUBLE OR NOTHING video bonus question. Should you risk it? There are two parameters X and Y.

1. If you didn't do that well, so you have LESS THAN X, then you are off your game and shouldn't risk it.
2. If you won a lot of money, at least Y, then you should just be happy and walk away with it.
3. If you won between X and Y then do the video bonus question.

I am risk averse, so X ≥ Y and I would never do the video bonus question. How about you? It might matter how much 400 or 1500 dollars is worth to you--- so you may very well be a risk taker in Cash Cab but not in Deal or No Deal where the amounts of money are much larger and thus more likely to be life changing. So X and Y might be functions of, not just how risk averse you are, but also on how much money is at stake. Could this be modeled?

THOUGHT THREE: When you watch a quiz show where there is only one contestant (e.g., Who wants to be a Millionaire or Cash Cab) and you yell out an answer, and the contestants yell a different answer, who do you hope is right?

1. I hope that they are right.
2. Almost everyone I've asked disagrees: That is, if I ask Alice, Alice hopes that Alice is right and the contestant is wrong.
3. If I was watching with someone I wanted to impress then I might hope that I am right.
4. If I like (dislike) the contestant then I hope they get it right (wrong) ind of what I yelled out.
5. So- what do you hope for, and why?

I expect to see a paper at INNOVATIONS on any or all of these topics.

Grothendieck categories are a generalization of categories of modules. Sheaves of abelian groups over a topological space also form a Grothendieck category. Grothendieck categories are a special case of abelian categories, but the extra structure allows additional theorems to be proved.

Grigory Garkusha has a thorough introduction to the subject on arXiv.

There was a Women in Theory Workshop at Princeton From June 19-23. ***SORELLE***, who was there, has some intelligent and interesting things to say about it here.. I will, instead, offer up a question.

I was at a Ramsey Theory Workshop in Italy and it was noted that of the 27 people there, none were women. Is there a shortage of Women in Ramsey Theory? Is this a problem? I suspect there is a shortage, however Ramsey Theory is too small an area to worry about it. Hence I doubt there will ever be a Women in Ramsey Theory Workshop.

Should there be a African-Americans in Theory Workshop? There are so few that it would end up being a bunch of non-African-Americans discussing why there so few African-Americans in Theory. To have a workshop analogous to the Women in Theory Workshop you need a larger critical mass. How many African-Americans are in Theory? What if I drop the requirement they must be American? I honestly don't know but I suspect its not that many. (If I am wrong then please let me know in the comments.)

Let A be an area (e.g, Recursive Algebraic Topology) and P be a subset of people (e.g., Left handed Latina Lesbians). When does a on P in A Workshop make sense? If A is too small then it would not make sense. If there are very few P's in A then there really can't be a such a workshop unless its mostly non-P's discussing why there are so few P's in A. If P is too big then there may not be a need for such a workshop; however, there may still be if there are issues facing P's that are not facing non-P's.

1. There have been African Americans in Mathematics Workshop. Here A is big enough and P is above critical mass.
2. According to this 24% of all lawyers are female and 44% of all law students are female. There may still be a need for workshops for female lawyers as they may face issues that male lawyers do not. Here was one: A Transformational Workshop for Women Lawyers.
3. Male Nurses are few in number, but there are some and I suspect they have problems that women nurses do not have. I do not know if they have workshops, but they do have their own magazine here.

What other workshops or conferences or whatnot on these types of issue have there been?

Most conferences hope that they will last a long time (e.g., We just had the 25th CCC. I hope there is a 50th). I suspect that the participants in the Women in Theory Workshop hope that these workshops are eventually not needed.

Psyche Corporation has a song called "Whirring World" about the Fibonacci Sequence.. You can hear it here:

http://www.myspace.com/psychecorp

..I couldn't find any better-quality versions on youtube as all the youtubes are of live performances so it's harder to hear the numbers distinctly.

Lyrics: http://psychecorporation.com/lyrics/ww.html


The song we're currently working on features the DNA sequence from the poliovirus, but that's not done yet.

I have just finished writing a LONG article on homeschool algebra 1 recommendations and advice. It took me quite many hours to write and research.

Questions about what to do for algebra 1 have become one of the "frequently asked questions", so I decided to write down something that I can refer people to, from now on.

I realize you may have different opinions and even suggestions for algebra curriculum in homeschool, so if you let me know, I'm willing to look into other possibilities not mentioned in the article.

How to best describe what we do to the layperson? It depends on what you mean by layperson.

I was in Austin Texas visiting my nephew Jason. I was also giving a talk at the University. My nephew fixes forklifts for a living and does not care about abstract things. (I'd be as bad at his job as he would be at mine.) He asked me what the talk was on. I think he asked just to be polite but did not really care. Even so, I tried to put it in as concrete terms as possible. My thought process: (1) Don't use n. Use an actual number, say 100. (2) Don't state a theorem. State an easily grasped corollary.

BILL: Picture that there is a 100 by 100 chessboard. Picture that you want to put queens on the diagonal so that every square of the board is either covered or under attack. What is the least number of queens you need for this? (NOTE: I leave it to my readers to prove that, for an n x n chessboard, this is IDENTICAL to finding large 3-free sets, that is, large sets that do not have arithmetic progressions of length 3.)

JASON: That is the dumbest problem I ever heard!. First off, chess is played on an 8x8 board. Secondly, only once while playing chess did I ever get my pawn to the end of the board to get a second queen, never mind getting n-o(n) queens (he didn't put it that way). And thirdly... who cares?

BILL: I don't suppose it would help to tell you that this relates to some deep mathematics of interest.

JASON: Of interest to who?

BILL: Uh... Never mind. (I thought about telling him that better bounds on the VDW numbers could get you $3000 dollars but decided not to.)

I usually do better than this with very concrete easily grasped statements. But he doesn't care about this problem. And actually, why should he? (I am sure some of my readers don't care about this problem either.)

I set up a new blog, Future of STOC to discuss role of our main conference and how to achieve it.

At STOC this year we had a relatively large attendance of 350 but why not 1000 or more? Why isn't our flagship conference bringing the theoretical computer science community together?

A couple of months ago I wrote up a proposal to address these issues and circulated them to a number of people in our community. You can read the proposal and the responses on the blog. Based on those responses the SIGACT Executive Committee decided to slowly increase the maximum number of acceptances but also open up the discussion at the STOC business meeting, which we did. Many people at STOC asked me to post the proposal and the responses and open up the discussion to the broader community. That's the purpose of the new blog.

We want to hear from you, the theory community. Tell us if you love STOC the way it is. Or how can we change STOC to make it more relevant to you? Even if you would never plan to come to STOC, tell us why.

Go to the Future of STOC and join the conversation.

The Institute Vienna Circle is hosting a workshop on Carnap next week, June 28 and 29.  The program is here.

(Guest Post by Vijay Vazirani)

Foundational ... or Simply a Curiosity?

Conventional wisdom has it that whereas linear programs have rational solutions, nonlinear programs have irrational ones. The discovery, in recent years, of increasing numbers of nonlinear convex programs that always admit rational solutions is challenging this long-held viewpoint. Furthermore, these convex programs capture the solutions to some fundamental problems in mathematical economics and game theory, e.g., market equilibrium under linear utilities.

As if that were not enough, these convex programs also admit combinatorial polynomial time algorithms for computing their (exact) optimal solutions; very recently, even strongly polynomial algorithms have been found. I am writing this guest post at the suggestion of several people who were not aware of these developments.

The main question that arises is: Is this phenomenon simply a curiosity or is it indicative of a grand, new chapter in the theory of algorithms? Let me put forth some reasons to believe that the latter may be the case.

Most of us are familiar with the notion of integral LP's -- LP's that behave like integer programs, in that they always admit integral optimal solutions -- and the key role they played in the birth and blossoming of combinatorial optimization. Indeed, some of the most elegant and foundational algorithms (e.g., for matching and max-flow) and algorithmic ideas (including the notion of polynomial time solvability) were discovered within this field.

Of course, not every combinatorial optimization problem admits such an LP; in particular, none of the NP-hard ones do. The latter were tackled via LP's that admit near-optimal integral solutions; their study lies at the core of the field of approximation algorithms. Again, it is remarkable that for many fundamental problems, their hardness of approximation is captured exactly as the integrality gap of such an LP (or SDP).

In view of this larger picture, and the clean, canonical and elaborate structure that was exploited in obtaining the combinatorial algorithms, the discovery of rational convex programs seems more than a curiosity, though only time will tell. However, rational convex programs are not likely to be found for more than a couple of handfuls of problems, as was the case for integral LP's. If so, where does this take us?

My best guess at present is that we need to seek combinatorial algorithms for finding near-optimal rational solutions to nonlinear convex programs; the motivation being that as always, we expect such algorithms to yield a wealth of valuable insights. In the past, such insights were crucially used for advancing the theories mentioned above. Once again, only time will tell if this is the right way of building on rational convex programs -- and of course, we should not forget that mathematics has its own agenda and its own ways of throwing surprises at us!

For further information, please see the introduction to the following paper here and references mentioned therein; the latter are available on authors' web sites.

These two Assistant Professorships in philosophy have just been advertised
at LMU Munich (see below). The deadline for applications is July 2nd, 2010. (German language skills are not mandatory.) Soon also several postdoctoral and doctoral positions in philosophy (at the new Munich Center for Mathematical Philosophy) will also be advertised.

(1) Ludwig-Maximilians-University Munich is seeking applications for an
Assistant Professorship in Logic and Philosophy of Language
at the Chair for Logic and Philosophy of Language (Professor Hannes
Leitgeb) at the Faculty for Philosophy, Philosophy of Science and the Study
of Religion. The position, which is to start from October 1st 2010, is for
three years with the possibility of extension. Technically, it is a
so-called 'Akademische Ratsstelle auf Zeit' in the Bavarian university
system, which means basically that one has the rights and perks of a civil
servant.

The appointee will be expected (i) to do research in logic and philosophy
of language, (ii) to teach five hours a week in these or in related areas,
and (iii) to contribute to the new Munich Center for Mathematical
Philosophy (MCMP) which is about to be founded at the LMU. The successful
candidate will have (iv) a PhD in philosophy or logic, and (v) teaching
experience in philosophy or logic.

The appointment will be made within the German A13 salary scheme. More
information on this position can be found at:

http://www.uni-muenchen.de/aktuelles/stellenangebote/wissenschaft/20100617151216.html

Women are currently underrepresented in the Faculty, therefore we
particularly welcome applications for this post from suitably qualified
female candidates. Given equal qualification, severely physically
challenged individuals will be preferred.

Applications (including CV, certificates, list of publications) should be
sent to

Ludwig-Maximilians-Universität München
Fakultät für Philosophie, Wissenschaftstheorie und Religionswissenschaft
Geschäftsstelle
Hauspost Fach 41
Geschwister-Scholl-Platz 1
80539 München

E-Mail: alexander.nawrath@lrz.uni-muenchen.de

by July 2nd, 2010.
Contact for informal inquiries: Prof. Dr. Hannes Leitgeb

(2) Ludwig-Maximilians-University Munich is seeking applications for an
Assistant Professorship in Mathematical Philosophy
at the new Munich Center for Mathematical Philosophy (MCMP) which will be
tied to the Chair in Logic and Philosophy of Language (Prof. Dr. Hannes
Leitgeb) at the Faculty for Philosophy, Philosophy of Science and the Study
of Religion. The position, which is to start from October 1st 2010, is for
three years with the possibility of extension. Technically, it is a
so-called 'Akademische Ratsstelle auf Zeit' in the Bavarian university
system, which means basically that one has the rights and perks of a civil
servant.

The appointee will be expected (i) to do philosophical research assisted by
logical or mathematical methods, (ii) to teach five hours a week in areas
of philosophy in which logical or mathematical methods are applied, and
(iii) to take on management tasks in the new Munich Center for Mathematical
Philosophy. The successful candidate will have (iv) a PhD in philosophy or
logic, and (v) teaching experience in philosophy or logic.

The appointment will be made within the German A13 salary scheme.

More
information on this position can be found at:

http://www.uni-muenchen.de/aktuelles/stellenangebote/wissenschaft/20100617151904.html

Women are currently underrepresented in the Faculty, therefore we
particularly welcome applications for this post from suitably qualified
female candidates. Given equal qualification, severely physically
challenged individuals will be preferred.

Applications (including CV, certificates, list of publications) should be
sent to

Ludwig-Maximilians-Universität München
Fakultät für Philosophie, Wissenschaftstheorie und Religionswissenschaft
Geschäftsstelle
Hauspost Fach 41
Geschwister-Scholl-Platz 1
80539 München

E-Mail: alexander.nawrath@lrz.uni-muenchen.de

by July 2nd, 2010.
Contact for informal inquiries: Prof. Dr. Hannes Leitgeb

( Reminder:Deadline for submitting to special issue of Theory of Computing in honor of Rajeev Motwani is July 30. See here. )

CCC 2010!

1. Ran Raz gave an AWESOME invited talk on Parallel Repetition of two player games ( here are the slides). What was most striking to me is that this line of research lead to the solution of a math problem (the Foam Problem) which would seem to be completely unrelated to it. Has this happened before- research starting in TCS leads to the solution of a seemingly unrelated math problem? Of course, my question is ill defined since TCS, Math Problem and seemingly unrelated are not well defined.
2. The talks following Ran's were also on two player games so his talk was a great way to get you up to speed on what follows. I would recommend that the Program Committee try to do this in the future: have the invited talk be the first in a session on related material. (I also realize that this may be hard to pull off.)
3. Subhash Khot gave a good invited talk on The Unique Game Conjecture. (These Slides should soon be available soon on his website. There is already a written survey on the material on his website and also slides he gave at FOCS05 on UGC. Here is his webpage.) This conjecture has been a great breakthrough in that it gives us something reasonable to assume that gives approx lower bounds- some of which match the approx upper bounds. It has also had many other applications unforeseen even by Khot when he first conjectured it. (Over dinner Khot told me he is only 90% sure that it is true. Gee, I thought he would have more confidence than that!.)
4. The talks that followed Khot's talk were all on UGC, and that was a big win.
5. Oded Regev gave great invited talk on The Learning with Errors Problem. (Talk and paper are here.) This was a talk where I learned about a problem I had not heard of and its connections to other problems. One of the applications was crypto (not surprising- that is Regev's main area.) The talks that followed it did not connect to it as much as for the other invited talks. This does not take away from the fact that I learned stuff of interest that I did not know ANYTHING about before.
6. Jakob Nordstrom gave a nice talk On the relative strength of pebbling and resolution. I had not known that pebbling was used to give lower bounds on resolution and I look forward to reading his 200 page survey on this topic. (It is on his website.)
7. Eric Allender had a paper in the first CCC (called STRUCTURES then) on Auxiliary PDA's. Eric Allender had a paper in the 25th CCC on Auxiliary PDA's. An Auxiliary PDA is a PDA with an additional log space workspace. I look forward to an Eric Allender paper on Aux PDA's at the 50th CCC. Note that Eric has worked on many other things as well.
8. Hrbues, Wigderson, Yehudayoff had a paper on Relationless Completeness and Separations. The idea here is to take algebraic complexity and see if you can get lower bounds if you do not assume that the operations are associative or commutative. The good news is that they did! The bad news is that the bounds for the case where the operations are associative and communicative are as hard as they were when Valiant first proposed this model many years ago. Valiant was at the talk and told me later that he would have thought that there would be more progress by now.
9. Alexandra Kolla had a paper Spectral Algorithms for Unique games. She seems to think that the UGC is false!
10. Impagliazzo and Williams talk on Communication Complexity with Synchronized clocks was an interesting new model of Communication Complexity which was used to solve some problems in classical CC. Also easy to understand since it was the first talk on a model. I suspect that within 5 years people will be using hard math to study this model and the talks will be harder to follow.
11. Buhrman, Fortnow, Koucky, Loff's paper show us that random strings are powerful in Derandomization from Random Strings
12. The most depressing talk was Derandomizing Arthur-Merlin Games and approximate counting problems since it seemed to imply that we need lower bounds on circuits to get derandomization. Worth knowing but not good news.
13. Business Meetings and Spouses: I know of three people who brought their non-complexity spouses with them to Boston. (They went sightseeing during the conference.) There are three approaches to what to do the night of the business meeting. One went to the meeting and left the spouse at the Hotel. One skipped the meeting to be with their spouse. One brought the spouse to the meeting. What would you do?
14. Business meeting was uneventful. CCC11 will be in San Jose as part of FCRC, CCC12 will be in Portugal (this was already sort-of known). Next year we may be leaving the 10th century and rather than give out handwritten proceedings on parchment we will be doing something electronic. Valentine Kabanets and Dieter von Melkebeek will be on the CCC steering committee, replacing two people whose terms have expired.

Common Core State Standards is a state-led initiative (not by the government) and designed by a diverse group of teachers, experts, parents, and school administrators.

They hope these standards will be adopted by various states. We shall see! It would definitely help if the math standards didn't vary so much among the various states. In some states, there are SO many standards and objectives per grade that it seems impossible students could learn it all well.

You can view the mathematics standards here. They also have language arts standards available.

snarXiv is a site the generates parody abstracts for high-energy physics theory papers, a la arXiv. While the abstracts don’t quite make sense, they eerily resemble the real thing.

snarXiv versus arXiv is another site that gives you a random snarXiv and arXiv paper title, and asks you to tell the fake from the real thing. The fake titles are much harder to recognize than the fake abstracts. Initially, I got the first 5 right, but after about 25 I was down to random chance.

Via Not Even Wrong.

László Lovász wins the Kyoto Prize for "Outstanding Contributions to Mathematical Sciences Based on Discrete Optimization Algorithms."

(Will post on Complexity next week. I am waiting until the invited talks have their slides online so that I can point to them.)

Let's say you just got a PhD in Logic. (ASIDE- my spell check program flagged PhD, but it gets 54,000,000 hits on Google so it has to be correct.) The job market is not so good. That is, the academic job market is not so good. I have recently been alerted to two alternative career paths one could take.

1. Get a job on Wall Street! You are probably thinking Oh, they want people that are good at math and can program. While that is true, they actually want people who know about ordinals! Ordinals? Yes Ordinals! See here.
2. Peter Cholak is a logician at Notre Dame who has had seven PhD students finish. Two of them went then went to Catholic seminary and become Catholic priests.

What to make of this? In American there is a priest shortage (see here for an article about it that mentions the law of large numbers). Hence the priesthood is a good job market. Are there other logicians-turned-priests? In this day and age I suspect there are not that many. In an earlier time when neither field required the kind of training they do now, there may have been more.

The job market for Protestant Ministers and Rabbis is not very good (See Protestant Ministers and Rabbis.) I was unable to find out how the job market is for Imam's.

I suspect that the decision to go into any of these fields is more of a calling than having a keen eye on the job market. Peter Cholak's two logician-turned-priest students just got their calling a bit late. They were both at the Fifth Conference on Logic, Computability, and Randomness so they are both trying to keep up some with logic. That may be hard; however, they may have help from up above.

I recently updated and revised my page listing various online math curricula. I tried to put the current pricing there so people could compare them easier, and also list them by level (either elementary/middle or middle/high school).

I feel using some online math program is an excellent choice for many parents, homeschooling or not. Sometimes they can be used as a supplement, and sometimes as a stand-alone program, especially with kids who like computer work because they get some extra motivation just because it's on computer. My own kids happen to like IXL for some additional math practice every now and then.

Of course many of these offer videos, and watching math videos online is a definite advantage of today's computer age.

Most of the curricula or programs are commercial but a few that I listed are actually free resources.