Lance Fortnow's Blog, page 122
May 28, 2013
Theory Jobs 2013
A reminder of the rules
I set up separate sheets for faculty, industry, postdoc/visitors and students.
People should be connected to theoretical computer science, broadly defined.
Only add jobs that you are absolutely sure have been offered and accepted. This is not the place for speculation and rumors.
You are welcome to add yourself, or people your department has hired.
This document will continue to grow as more jobs settle. So check it often.
Edit
May 23, 2013
Quantum Computing Fast and Slow
and Scott Aaronson's Quantum Computing since Democritus. Not much to connect the two except both deal to some extent about probability and computation and I want to write a blog post for each chapter, for much I disagree with both authors. But that's what makes them so much fun, so rare to find science-oriented books both worth reading that have the guts to say things that one can disagree with.
In full disclosure, Scott and I agree that he would post about my book if I wrote about his but what a deal. Scott's book is a pleasure to read. He weaves the story of logic, computation and quantum computing into a wonderful tour. You can get an idea of Scott's style by how he explains how he will explain quantum.
The second way to teach quantum mechanics eschews a blow-by-blow account of its discovery, and instead starts directly from the conceptual core - namely, a certain generalization of the laws of probability to allow minu signs (and more generally, complex numbers). Once you understand that core, you can then sprinkle in physics to taste, and calculate the spectrum of whatever atom you want.
He approaches the whole book by this philosophy. Every now and then he moves into technical details that are best skipped--either you already know it or will get lost trying to follow. But no problem, the story remains. You need to appreciate Scott's sense of humor and his philosophical tendencies, and he does get way too philosophical near the end, particularly a strange attack on Bayesian that involves God flipping a coin. At the end of the book Scott contemplates whether computer science should have been part of a physics department but after one reads this book the real question is whether physics should be part of a CS department.
Kahneman gives a readable tour of behavioral economics with a variety of examples, though I don't agree with his interpretation of many of them. His fast and slow refers to decisions we make instinctively and quickly (like judging a person based on first impressions) versus more slow and deliberative (like multiplying numbers). There is a computer science analogy, in that his fast refers to what we can do with machine learning, simple trained models to make quick judgments that occasionally gets things wrong. I'm not a huge fan of behavioral economics, but it is useful in life to know the probability mistakes people make so you can avoid making them yourself. The wikipedia article has a nice summary of the effects mentioned in the book.
While these two books cover completely different areas, the themes of probability and computation pervade both of them. One simply cannot truly understand physics, economics, psychology and for that matter biology unless one realizes the computational underpinnings of all of them.
May 21, 2013
Do you KNOW how you KNOW what you KNOW? I don't KNOW.
As an undergrad I learned mostly from taking courses. Hence I could say things like I Know Group theory from a course I had in Abstract Algebra in the Fall of 1978 (Side Note- I know why I should care about groups from reading the algorithm for graph isom for graphs of bounded degree---in 1988). I learned a few things on my own- I learned that a graph is Eulerian iff every vertex has even degree from a Martin Gardner article. But since most of my knowledge was from courses I knew how I knew what I knew.
As a grad students I still took courses but more routes to knowledge emerged. Papers! I could say things like
I know the oracle constructions about P vs NP because I read the Baker Gill Solovay paper on October 23, 1981. It helps that Oct 23 is Weird Al's birthday. But even here things get a bit murky- someone TOLD ME about the paper which lead me to read it, but I don't recall who. So one more route to knowledge emerged- people telling you stuff in the hallways.
I saw Anil Nerode give a talk on Recursive Mathematics and that day went to the library (ask your grandmother what a library is) and read some articles on it. This was well timed- I knew enough recursion theory and combinatorics to read up on recursive combinatorics. In this case I know exactly how I know what I know. Might be the last time.
As a professor I read papers, hear talks, hear things in hallways, and learn stuff. Its getting harder to know how I know things, but to some extend I still could. Until...
THE WEB. The Web is the main reason I don't know how I know things. I sometimes tell Darling I read it on the web which is (a) prob true, and (b) prob not very insightful.
So- do you know how you know what you know?
On Jeopardy recently the final Jeopardy question was as follows.
TOPIC: Island Countries.
ANSWER: No longer Western, this one-word nation has moved to the west side of the international Date Line to join Asia and Australia.
BILL: What is SAMOA!?
Darling wondered how I know that:
DARLING: How did you know that? Is there a Ramsey Theorist in Samoa?
BILL: Not that I know if, but that's a good guess as to how I knew that. Actually Lance had a blog post Those Happy Samoans about Samoa going over the international dateline and losing the advantage of having more time to work on their conference submissions.
DARLING: Too bad there isn't a Ramsey Theorist there to take advantage of that!
Thanks Lance!- In this one case I know how I know what I know!
May 16, 2013
The MOOCs Degree
We will roll out slowly, with a smaller scale courses to corporate affiliates to work out the kinks and the plan to go to the general public in fall 2014. Read the FAQ to get more information about the program.
It's been fun watching the development of this degree, in particular hearing Sebastian talk about his MOOC 2.0 plans to scale courses with a small amount of expense that we pull from the tuition. No doubt we will have challenges in making this degree truly work at a large scale but I'm truly bullish that we'll a self-sustaining quality Masters program that will reach tens if not hundreds of thousands of students.
Here we go.
May 13, 2013
Mother's Day Math
My solution: Take mom out to lunch the FOLLOWING week. Some of my friends tell me NO- you can't just MOVE Mothers day- what are you--- The Master of Space and Time? The key is that my mom AGREES with me and in fact raised me with these values: (1) Never do X when everyone else is doing X, its too crowed, and (2) Learn the polynomial VDW theorem.
While this solution may work for me, it may not work for everyone. Here are some options to alleviate the restaurant crunch:
Declare the second WEEKEND in May to be MOTHERS WEEKEND. People take their moms out to lunch SATURDAY or SUNDAY. This would split the restaurant load in half.
Declare May MOTHERS MONTH. People take their moms out to lunch ONE Sunday in May. This would split the restaurant load by 4.
Declare May MOTHERS MONTH. People take their moms out to lunch ONE Saturday OR Sunday in May. This would split the restaurant load by 8.
Declare May MOTHERS MONTH. People take their moms out to breakfast OR lunch OR Dinner ONE Saturday OR Sunday in May. This would split the restaurant load by 24. How would people DECIDE which day to do:
The last day of April have mom either (depending on which of the above schemes) flip a coin, role a 4-sided die, or role an 8-sided die or role two 12-sided dice to determine which day to be taken to lunch. Fortunately, due to the Dungeons-and-Dragons craze that girls got into about 40 years ago, most mothers have these dice. But in case she does not, here is a nice MATH PROBLEM (I am sure already solved): USE fair coins and fair 6-sided dice to simulate other random choices fairly. In our case 4-sided, 8-sided, and 24-sided. Which random choice can be simulated? Which can't?
Say we do the Saturday/Sunday/breakfast/lunch/dinner solution. Everyone with last name beginning with A goes to breakfast on the first Saturday. Everyone with last name beginning with B goes to lunch on the first Saturday. etc. There are only 24 lunches and 26 letters, so merge P and Q, and merge Y and Z.
How likely is any of this to come about? It would need to evolve naturally as a social custom. It also would have to not be that hard to implement. As such the 24-meal-plan probably won't catch on. Also, if Mother's Day become Mothers one-of-24-meals-day it may lose something. Hence the 2-meal-plan solution is probably the best.
However, the entire tradition of taking mom out to lunch on mothers day may fade. The origin is that mom cooks for the family most days, so this ONE day they take her out. Nice! But more and more households share responsibilities (NOTE- I have no facts or stats to back this up but it has a certain truthiness about it) hence the notion of taking mom out to lunch may seem more and more odd over time. Then again, its still nice being taken out to lunch.
May 9, 2013
GPU Computing
As computer gaming got more intense in the decades that followed, we first had graphics cards designed to speed up the process and later Graphics Processing Units or GPUs, dedicated processors devoted to graphics.
Around the turn of the century, people started using GPUs for more than just graphics. GPUs did certain kinds of vector manipulation quickly and one could use these for a variety of mostly scientific computing. But GPUs weren't really well designed for other purposes. Following the cupholder principle, GPUs began to evolve to allow easier to access APIs from more common programming languages becoming General Purpose GPU or GPGPUs. Several systems researchers at Georgia Tech and elsewhere are now redesigning chip layouts to make the best most efficient uses of CPUs and GPGPUs.
The theory community hasn't seem to catch on yet. There should be some nice theoretical model that captures the vector and other operations of a GPGPU and then we should search for algorithms that make the best use of the hardware. The theory world writes algorithms for non-existent quantum computers but not for the machines that we currently use.
May 6, 2013
Are you smarter than a fifth grader? I'm not.
Are You Smarter than a Fifth Grader? They asked the following Math Question:
What number do you need to add to 3 to get a double fact?I had never heard the term double fact! I really didn't know and there was no way toderive it! I don't recall what my guess was but it was incorrect.See herefor what they are.
Is this a common term? If you Google
"Double fact" mathYou get roughly 6,000 hits. (Down from 17,000 a few months ago when I first sketched out this post.)Is that enough hits to be a real term? Is number-of-hits a good measure?
Are there other math terms that are being taught in elementaryschool that are not that well known to people like us? (Though if you have children perhaps you know them.)Note that no matter how much math you know, there may be terms you don't know and can't derive (though you can make an intelligent guess).
My name is Bill Gasarch, and I am NOT smarter than a fifth grader.
May 2, 2013
Map Coloring Revisited
But I also wanted a natural example that was four-colorable even though every interior region had an even number of neighbors. In my book I ended up making up my own fake country map.
(Sorry for the hand-drawn picture and getting East-West wrong. Looks better in the book)
So once again I'd still like to see a natural example. Here's a simple 7-node graph with every interior node with even degree but not 3-colorable.
There must be some real world map that captures this graph.
I'll make the same deal I made before, an autographed copy of my book for the best example of a real-world example of a non-three colorable map with interior regions with an even number of neighbors. Should be a real political unit--not just a collection of states.
April 30, 2013
Computer Assisted Proofs- still controversial?
Kenneth Appel, of Appel-Haken Four Color Theorem Fame, died recently. See here for an obit.
In 1972 I read that the four-color theorem was an open problem. From what I read it seemed like there was some progress on it (e.g., results like `if its false the graph has to be yah-big) but it seemed to be years away from being solved. I assumed that a new idea was needed to solve it.
Then, in 1976, it was SOLVED by Appel-Haken. From what I read it wasn't so much a new idea but very clever use of old ideas and a computer program. I also heard that it was just at the brink of what computers could do at the time, and that it would have taken 1200 grad student hours. (There is a good description of the proof on Wikipedia here.)
At the time I heard there were objections to the proof. Later when I read some of them they didn't seem like real objections. They boiled down to either
I wish there was a shorter proof. This is true, but not a reason to object.
It can't be hand checked. I trust a computer-checker MORE THAN a human checker
We don't know WHY its true. This is a more reasonable objection- but we do know how they got it down to a finite number of cases, so I'm happy with that.
In 1996 Robertson, Sanders, Seymour, Thomas was obtained a simpler proof. In 2005 Werner and Gontheir formalized the proof inside Coq- a proof assistant. To quote Wikipedia This removed the need to trust the various computer programs used to verify particular cases;it is only necessary to trust the Coq Kernel At this point I doubt anyone seriously doubts that the theorem has been proven.
There have been more computer-assisted proofs since then. See here for a list of some of them. That article also claims that such proofs are controversial and not always accepted. Is this really true? I thought the controversy was gone except for the topic of the next paragraph.
A famous computer assisted proof (or perhaps ``proof'') is the Kepler Conjecture. In 1998 Thomas Hale claims to have proven it. The proof involved rather complex computer calculations. The referees say they are 99% sure its true. Here's hoping an easier proof is found.
Computer assisted proofs may become more common. I just hope we still know WHY things are true.
Was Appel-Haken the first use of computer assisted proofs? I doubt it, but it was likely the first one to have an impact. It was important to know that this kind of proof could be done.
Is there a much shorter proof? A combinatorist once told me that since the function
f(n) = max size of proofs of statements of length n
grows faster than any computable functions, there have to be some statements that have very log proofs; and perhaps the four color theorem is one of them.
April 26, 2013
Ideas in Search of a Blog Post
Some people like to write prose, some people like to write lists, like Bill's last post. Bill will often send me an email that's a list of items. I prefer the prose and usually avoid the lists with today being the "exception that proves the rule" (an expression that I never understood).
I do have to admit that lists are very efficient, when I can respond to Bill like
yes
no
Friday
Did you really expect happy comments on that post?
Marissa Mayer has banned working at home for Yahoo employees. Lots of academics work at home when they aren't teaching. I didn't have any more deep insights here so it didn't become a post.
I have a note to write a blog post on "confusing university names". I wonder what was confusing me.
I'll end this post of uninteresting post ideas with the wine tasting story. At Cornell there was a popular course on wine tasting open only to graduating seniors. Alas it conflicted with graduate complexity which I took from the great Juris Hartmanis. I don't regret that choice but missed the wine.
When I was a grad student at MIT there was a wine tasting course held during the short IAP session during winter break. So we took that course. A fun course. On the last day we all dressed up for the really fine wine. The instructor came to class in his tux even though he was quite ill that day. Two days later everyone in the class got sick as well.
There ought to be a moral to that story but I haven't figured it out yet.
Lance Fortnow's Blog
- Lance Fortnow's profile
- 4 followers
