 Jimmy Carter (President 19761980, lost reelection) was trained as a Nuclear Engineer, so he knew some math a long time before becoming president. (I do not know if he ever actually had a job as an Engineer.) I doubt he knew much when he was president.
 Herbert Hoover (President 19281932, lost reelection) was a Mining Engineer and actually did it for a while and was a success. Even so, I doubt he know much when he was president.
 James Garfield (President 18811881, he was assassinated) Had a classical education and came up with a new proof of the Pythagorean Theorem
 Thomas Jefferson (President 18011809) had a classical education and is regarded by historians as being a brilliant man. He invented a Crypto system in 1795. Note that this is only 6 years before becoming president, so he surely knew some math when he was president.
 Misc: Lyndon B. Johnson was a high school math teacher, Ulysses S. Grant wanted to me one but became president instead. George Washington was a surveyor which needs some math. Many of the early presidents had classical educations which would include Euclid. And lastly, Warren G. Harding got an early draft of Van Der Waerden's theorem, conjectured the polynomial VDW, but was only able to proof the quadratic case (not surprising—he is known as one of our dumber presidents).
Computational Complexity and other fun stuff in math and computer science from Lance Fortnow and Bill Gasarch
Monday, December 31, 2007
Presidential Math
Thursday, December 27, 2007
Oral Homework
 The students are in groups of 3 or 4. The groups are selfselected and permanent (with some minor changes if need be).
 The groups do the HW together.
 They are allowed to use the web, other students, me, other profs.
 The HW is not handed in–they get an Oral Exam on it.
 The HW is usually "read this paper and explain this proof to me."
 Savitch's theorem and ImmermanSzelepcsenyi Theorem.
 Show that VC and HAM are NPC.
 E(X+Y)=E(X)+E(Y), Markov, Chebyshev, Chernoff
 Reg Exp with squaring NOT in P.
 Matrix Group Problem in AM. (Babai's paper "Trading Group Theory for Randomness").
 The students learned ALOT by doing this. They learned the material in the paper, they learned how to read a paper, and they learned how to work together. (Will all of these lessons stick?)
 Some proofs are better done on your own than having a professor tell you them (HAM cycle NPC comes to mind). This is a way to make them learn those theorems without me having to teach it.
 Some theorems are needed for the course, but are not really part of the course (Chernoff Bounds come to mind). The Oral HW makes them learn that.
 This was a graduate course in theory so the students were interested and not too far apart in ability. This would NOT work in an ugrad course if either of those were false.
 This course only had 19 students in it, so was easy enough to administer.
Monday, December 24, 2007
The Twelve Days of Tenure
12 people asking her questions in her office, 11 times taught Intro Programming, 10 journal articles, 9 pieces of software, 8 book chapters, 7 invited panels, 6 submitted articles, 5 million bucks!, 4 invited talks, 3 students, 2 postdocs, and a degree from MIT. 
NOTE: The 12 days of Christmas is (easily) the most satirized song ever. I used to maintain a website of satires of it here but it was too hard to keep up? Why? Because anyone can write one. I wrote the one above in about 10 minutes during a faculty meeting to decide someone's Tenure case.
Friday, December 21, 2007
A Bad Deal
I don't usually watch Deal/No Deal. I like some of the interesting math or dilemmas it brings up, but the show itself is monotonous. As Host Howie Mandel himself says "we don't ask you a bunch of trivia questions, we just ask you one question: DEAL or NO DEAL!" Here is a scenario I saw recently where I thought the contestant made the obviously wrong choice.
 There are two numbers left on the board: $1000 and $200,000.
 She is offered a $110,000 deal.
 She has mentioned that $110,000 is about 5 times her salary (so this amount of money would make a huge difference in her life).
 Usually in this show you have the audience yelling `NO DEAL! NO DEAL!' This time the audience, including her mother, her sister, and some friends, were yelling `TAKE THE DEAL! TAKE THE DEAL!'. While this is not a reason to take the deal, note that the decision to say NO DEAL is NOT a `caught up in the moment' sort of thing.
 If she takes the deal, the worst case is that she gets $110,00 instead of $200,000.
 If she rejects the deal, the worst case is that she gets $1000 instead of $110,000.
Wednesday, December 19, 2007
More on VDW over the Reals
I had claimed that the proof that if you 2color R you get a monochromatic 3AP USED properties of R notably that the midpoint of two elements of R is an element of R. Someone named ANONYMOUS (who would have impressed me if I knew who she was) left a comment pointed out that the proof works over N as well. THIS IS CORRECT:
If you 2color {1,...,9} then there will be a mono 3AP. Just look at {3,5,7}. Two of them are the same color.
 If 3,5 are RED then either 1 is RED and we're done, 4 is RED and we're done, or 7 is RED and we're done, or 1,4,7 are all BLUE and we're done.
 If 5,7 are RED then either 3 is RED and we're done, or 6 is RED and we're done, or 9 is RED and we're done, or 3,6,9 are all BLUE, and we're done.
 If 3,7 are RED then either 1 is RED and we're done, or 5 is RED and we're done, or 9 is RED and we're done, or 1,5,9 are BLUE and we're done.
 More Interesting: If VDWr is proven true using analysis or logic, then we get a NEW proof of VDW!
 Less Interesting: Since it is unlikely to get a new proof of VDW, it is unlikely that there is a proof of VDWr using analysis.
Monday, December 17, 2007
Bad News for American Science Funding/Good News for Australia Science Funding
Good news for Australian Science Funding: click here
Friday, December 14, 2007
Complexity Theory Class Drinking Game
Complexity Theory Class Drinking Game
 Whenever a complexity class is defined that has zero natural problems in it, take one drink.
 Whenever a class is defined that has one natural problem in it, take two drinks.
 Whenever you are asked to vote on whether or not a problem is natural, take three drinks.
 Whenever a mistake is made that can be corrected during that class, take one drink.
 Whenever a mistake is made that can be corrected during the next class, take two drinks.
 Whenever a mistake is made that cannot be corrected because it's just wrong, take three drinks.
 Whenever a probability is amplified, refill your cups since a class with zero or one natural problems in it is on its way.
 Whenever the instructor says that a theorem has an application, take a drink.
 Whenever the instructor says that a theorem has an application, and it actually does, take two drinks.
 Whenever the instructor says that a theorem has an application outside of theory, take two drinks.
 Whenever the instructor says that a theorem has an application outside of theory, and it really does, take four drinks.
Monday, December 10, 2007
An ill define question inspired by that HS question
Each point in the plane is colored either red or green. Let ABC be a fixed triangle. Prove that there is a triangle DEF in the plane such that DEF is similar to ABC and the vertices of DEF all have the same color.The answers to all of the problems on the exam are posted See here for the webpage for the competition. The problem above is problem 5.
One of the key observations needed to solve the problem is the following theorem:
If the reals are 2colored then there exists 3 points that are the same color that are equally spaced.
Before you can say `VDW theorem!' or `Roth's Theorem!' or `Szemeredi's theorem for k=3 !' realize that this was an exam for High School Students who would not know such thing. And indeed there is an easier proof that a HS student could (and in fact some did) use:
Let a,b both be RED. If (a+b)/2 is RED then a,(a+b)/2,b works. If 2ba is RED then a,b,2ba works. If 2ab is RED then 2ab,a,b works. IF none of these hold then 2ab,(a+b)/2,2ba are all BLUE and that works.By VDW the following, which we denote VDWR, is true by just restricting the coloring to N:
VDWR: For any k,c, for any ccoloring of R (yes R) there exists a monochromatic arithmetic progression of length k.
This raises the following illdefined question:
Is there a proof of VDWR that is EASIER than using VDW's theorem. Or at least different perhaps using properties of the reals (the case of c=2, k=3 used that the midpoint of two reals is always a real).
Friday, December 07, 2007
Funny Answers on a Math Olympiad (MD)
Each point in the plane is colored either red or green. Let ABC be a fixed triangle. Prove that there is a triangle DEF in the plane such that DEF is similar to ABC and the vertices of DEF all have the same color.I think I was assigned to grade it since it looks like the kind of problem I would make up, even though I didn't. It was problem 5 (out of 5) and hence it was what we thought was the hardest problem. About 100 people tried it, and less than 5 got it right, and less than 10 got partial credit (and they didn't get much).
I got two funny answers:
All the vertices are red because I can make them whatever color I want. I can also write at a 30 degree angle to the bottom of this paper if thats what I feel like doing at the moment. Just like 2+2=5 if thats what my math teacher says. Math is pretty subjective anyway. (NOTE this was written at a 30 degree angle.)
I like to think that we live in a world where points are not judged by their color, but by the content of their character. Color should be irrelevant in the the plane. To prove that there exists a group of points where only one color is acceptable is a reprehensible act of bigotry and discrimination.Were they serious? Hard to say, but I would guess the first one might have been but the second one was not.
Wednesday, December 05, 2007
Crypto problem inspired by politness
My motherinlaw Margie and her sister Posy had the following conversation:
POSY: Let me treat the lunch.
MARGIE: No, we should pay half.
POSY: No, I want to treat.
MARGIE: No, I insist.
This went on for quite a while. The question is NOT how to avoid infinite loops my solution to that is easy if someone offers to treat, I say YES and if someone offers to pay 1/2 I say YES, not because I'm cheap, but to avoid infinite loops.
Here is the question. It is not clear if Posy really wanted to treat lunch, or is just being polite. Its not clear if Margie really wants to pay half or is just being polite. SO, is their some protocol where the probability of both getting they DO NOT WANT is small (or both getting what they want is large), and the other one does not find out what they really want. Here is an attempt which does not work.
 Margie has a coin. Margies coin is OFFER with prob p, and DO NOT OFFER with prob 1p. If she really wants to make the offer to treat then p is large, else p is small. Could be p=3/4 or p=1/4 for examples.
 Posy has a similar coin.
 Margie flips, Posy Flips.
 If Margie's coin says OFFER, than make the offer. If not the don't.
 Same with Posy.
In solutions you may offer or point me to we can of course assume access to random coins, and that neither Posy nor Margie can factor or take discrete log.
Friday, November 30, 2007
Sending out Job Applications
(Guest Post by Claire Kenyon)
This is the time of year when job candidates are getting ready to send out their applications. I have done this many times over the years. Here are a few suggestions based on my experience.
Candidates want to find a job where they will be successful; department want to hire candidates who will be successful in their job: this is not inherently adversarial; it's just a question of finding the right match.
Cover letter:
1) Don't call a place "College" if it's a "University", and viceversa. Get the names of committees and of people right. Obvious, yet, it took me a few years to learn this!
2)How to get the reader to look beyond the cover letter? Catch their attention. Give a specific reason why you are interested in that place; preferably personal (something that says something about you, and that few other candidates are likely to say.) "I am interested in the computer science department at University Lambda because of its unique research interest in Reducing the Number of Greek Symbols in Analysis of Stuff, and its joint project with the Humanities department on that subject. My publications have a lot of greek symbols in them (see [1,2,3,4,5] for example), and I would be very interested in applying the lambda methodology to my work."
3) How to get the reader to forward your application to the right person? Give specific names. For example:
Professor Big Shot, who I met during the 2007 Symposium on Theory of Unreasonable Protocols for Integer Data (see [3]), encouraged me to apply.That context will help Big Shot place you in their memory when they get the application.
4) Be selfconsistent. Do not tell UC Big
I just love the idea of public service in the rich environment of a large university
and simultaneously tell Happy University
I love the idea of mentoring a small group of select students in the focused environment of a small highquality university.
The reasons are that this may become known (we do talk to one another) and would cost you your credibility; that you won't be able to follow through by arguing convincingly both ways; and that such blatant misrepresentation of yourself makes it more difficult to find the right match.
5) Read the ad, and address obvious issues upfront.
You said you're looking to hire a researcher in humancomputer interaction using ergonomic mouse pads, and my area, cryptanalysis of publickey cryptosystems using elliptic curves, may at first sight look somewhat remote; however there are surprising connections that I intend to reveal in my future research: elliptic curves
Thursday, November 29, 2007
Googlestupid
The article told the story of a women who got married and took her husbands name, hence going from an uncommon, firstpagegooglename, to a common 85thpagegooglename. This hurt her career. When considering what to name her children she used Google to make sure that her kids would have names that pop up on the first page of a Google search.
When considering naming your child how do the following rank in importance?
 Honoring a family member.
 Carrying on a tradition.
 If you are religous, using a name from your faith (e.g., I know a Christian who uses only biblical names for his four kids alternating Old Testament and New Testament).
 First Page on a Google Search.
Uncle Bill, did people really name their children after themselves? Thats just googlestupid.
Wednesday, November 28, 2007
Unrefereed DOES NOT EQUAL bogus
 STOC, FOCS, SODA, CCC, LICS, MFCS, ICALP, COLT, CRYPTO, EUROCRYPT, STACS, SCG (I'm sure there are others). Strongly Refereed (acceptance rates all under 50 percent, some much lower), there is a proceedings, there may or may not be guest speakers. Registration 400600 dollars. Authors not forced to pay for the honor of being authors. This notion would strike every particpant as unusual to say the least.
 Annual AMS meeting. There are a large number of contributed papers (unrefereed) in specialized areas. No proceedings. There are guest speakers. Registration 400500 dollars. Note that while the contributed papers are not refereed there is no claim that they are. Alot of the math community goes to this. There is a pamphlet of what the contributed talks will be (there are multiple parallel sessions) so you can pick and choose what to goto. Even though the contributed papers are not refereed, some of them are worth hearing Authors not forced to register.
 Southeastern International Conference on Combinatorics, Graph Theory, and Computing. this is last years conference Similar to AMS meetings but more specialized. Registration about 200 dollars. (`Southeastern International' is oximoronic and makes it SOUND like a bogus conference, but at that price and no claim to refereeing, its fine.)
As a community we seem to have lost the ability to have an informal meeting (exception: Dagstuhl and others like it, which are informal BUT you have to be invited to them.)
SO, what does make a conference bogus?
 They CLAIM that its refereed and it is not.
 They seem to be overcharging OR charging for very odd things.
Tuesday, November 27, 2007
Bogus or not You decide
I emailed Mike Sipser. Below is his response, which includes a response from the conference organizers. (I have edited it down a bit but have not changed the content. I also have one clarifying remark.)
Hi Bill, I'm sending you the response from one of the conference organizers. From what they say this practice occurs at other conferences. I believe the conference is a real one, though I don't directly know the primary individuals involved. My personal role has been minor, just answering a few emails and giving a little advice.  Mike
(REMARK FROM BILL: THIS EMAIL BELOW IS FROM THE CONF ORGANIZER TO SOMEONE WHO GOT PAPERS IN AND INQUIRED ABOUT IT.)
From: Bhanu Prasad
Subject: Is TMFCS08 a real conference?
This email is in response to your email sent to Prof. Sipser. Prof. Sipser asked me to look into this. Hence I am responding.
I learned that you submitted two papers and requested the conference people to conduct the review fast. They (conference people) have informed you the acceptance, along with the review results as soon as they received from the reviewers. Then you asked them to send the invoice for payment of fee using PayPal. They have sent it. Then you asked if the fee is for both the papers or for one paper. They informed that the fee is for one paper but they reduced the fee for the 2nd paper by 30%.
For your information, I am aware of several conferences where they do not even reduce the fee for the 2nd paper. See for example, http://conferences.computer.org/scc/2007/registr.html . They clearly indicated the following: "Each paper needs at least one FULL registration, before the cameraready manuscript can be included in the proceedings. There is no student rate for the author who is responsible for registration for his/her published paper. If you have more than one accepted paper, you need to register for each one individually. There is no discount if you have two or more papers accepted."
For your information, it is a real conference (because the people in that are real and I was there in 2007 conference, and it will have proceedings, etc.).
I don't think a fake conference will become real just because they collect one fee for both the papers.
Best regards, Bhanu Prasad, Organizing committee
Theoretical and Mathematical Foundations of Bogosity
I sent to papers to a conference TMFCS08 (Theoretical and Mathematical Foundations of Computer Science) and got accepted, however, they ask me to pay the registration fee twice, one for each paper (2x$550), is that normal?
 I emailed her that this IS normal for bogus conferences that are complete ripoffs, but not normal otherwise.
 I'm surprised anyone falls for this kind of thing. Then again, it may be that the school that the prof is at also does not know the difference, so it does help the resume.
 I looked on the web for more info on this conference and could not find anything saying it was bogus (By contrast you can find stuff about WSEAS being bogus). Anyone have any more information?
Monday, November 26, 2007
Reading Math over Thanksgiving
It is sometimes easier to learn stuff when you are AWAY from your computer. Less distractions. BUT if you need to look something up, its harder. BUT this may force you to think harder. BUT maybe you need to look something up and can't derive it yourself BUT, BUT, BUT... However, it worked this time.
I also came up with a trivial math problem based on real life. I got into an elevator that had 23 floors and was going to the 4th floor. Two people got in and BOTH pushed buttons that were LESS than the 4th floor and diff from each other. I later thought `Gee, you would think being on the 4th floor you wouldn't stop twice to get there. What is the probability of that happening?' I had the answer in about 1 minute. Much easier than understanding Szemeredi's Regularity lemma. ~
Monday, November 19, 2007
Advice about NSF grants (not from me)
Thursday, November 15, 2007
More on the Tables Problem
n couples go to a resturant. They will sit at a rectangular table that has room for n on each side. Each person sits either next to across from their darling. How many ways can they sit?Most people got the correct answer in the comments on my last blog. But some other interesting points were raised that I will address.
 I had commented that this was asked on the 2007 Maryland High School Math Olympiad, Part I,, problem 23, which is with Multiple Choice, for the case of n=5. Some commenter wanted to know what the choices were: 360, 768, 5040, 19200, 30720.

Someone commented that the problem `was not new'
and gave this, problem 4,
as a pointer to where it had been asked before.
Here is the problem they were referring to:
Define a domino to be a 1x2 rectangle. In how many ways can a nx2 rectangle be tiled by dominos?
This raises an interesting question: When are two problems equivalent? Does phrasing matter (I had people, they have dominos)? Does making certain things distinguiable or not matter (Dominos are not distinguiable, couples are)? Does having different answers matter (his is Fib(n+1) mine is a Fib(n+1) x 2^n x n!)? More generally, its not clear when a problem is new.  Just to reiterate there is math all around you if you know where to look.
Wednesday, November 14, 2007
Math Problems from everyday life
Here is one that inspired a problem that ended up on the Maryland Math Olympiad, Part I (which is 25 multiple choices questions). (5 choices, 4 points for a correct answer, 2 points for a wrong answer. You really really do not want to guess.)
Here is what happened: I went to dinner with my darling, and my two sisterinlaws and their husbands. I sat across from my darling but the other couples sat next to each other. So here is the question: I immediately thought about the following question:
$n$ couples go to dinner. They sit at a rectangular table, but nobody sits at the ends. Each couple either sits ACROSS FROM or NEXT TO their darling. How many ways can they be seated?The problem on the exam was asked for 5 couples and gave choices.
Its not a hard problem for the readers of this blog, so I leave it to my commenters to solve it. (If nobody does I'll post the solution later.) Note that it would be hard for a high school student very few got it correct. (We suspected this would be the case. We try to order the questions by difficulty and this was question 23.)
Monday, November 12, 2007
COMPUTATIONAL COMPLEXITY CONF 2008 SUBMISSIONS WEBSITE OPEN!
 Submission deadline is Dec 6, 2007, 17:59 PST
 Notification will be by Feb 8, 2008.
 Conference will be in College Park Maryland (details on that will be on the conference website soon)
 It will be awesome!
Trivial question: Name everyone who has been to every single COMPLEXITY conference, including when it as called STRUCTURES? (I've been to all but one, Jack Lutz has been to all but two, so we do not qualify.)
Friday, November 09, 2007
Richard Beigel is at NSF
Lets all wish him well on the job if he does well, we do well.
Wednesday, November 07, 2007
Resubmitting Rejected FOCS paper to STOC
If your paper was rejected by FOCS and you're submitting it to STOC, here are my thoughts on how you can increase your chances of acceptance. Given the low acceptance rate for FOCS, I am sure many of us will be resubmitting our rejected papers to STOC. Many of us will be incorporating the FOCS PC comments. And there's also a realistic chance that FOCS PC misunderstood our papers. So what should we do so that STOC committee does not repeat the misunderstanding?
Let me first describe the general methods to contain the chances of misunderstanding. I will then describe why the chance of misunderstanding has increased for STOC PC on resubmitted papers by giving you an insider view of FOCS 2007 PC. We can then discuss what we could do to minimize that.
Contain the chances of misunderstanding
Well of course removing the items from the paper which gave rise to misunderstanding could be beneficial. These items could arise either due to lack of explanation, positioning of clarification, or overselling the results. Lack of explanation happens because we fail to realize as authors that our mind is preconditioned while researching on the paper and the reviewer's mind won't be preconditioned in the same way. Therefore things which look clear to us may be confusing to a reviewer. Positioning of clarification is very important because not every paper is read word to word. So it is very important to put the clarification or a pointer to it as close as possible to the place where confusion could potentially arise. Overselling does not improve the chances of a paper getting accepted. Overselling of results typically puts the reviewer in a defensive position. A reviewer could look at other existing papers that have introduced similar techniques and be at a loss for what is new, unique, and real about what this paper promises.
So how do you address these problems? One thing is to prepare the paper early and seek feedback. Do not expect somebody, who is not genuinely interested in your work, to provide you good quality feedback for free. You would need to pay. How? Offer the same high quality service on their papers as you expect on your own papers. Posting your papers online, e.g., as a technical report in some archive could also bring some early readership, which may provide you feedback and opportunities to exchange feedback.
If you really need to sell your paper, what's the best way? Give talks  as many as possible. Try to accept every invitation and try to get yourself invited by marketing the results. In order to market the paper be open to discussing your results in small chats without pen and paper, e.g., over a lunch table. Acknowledge all prepublication discussions, including those which were not explicitly used in the paper. Mentioning the names of the people is very important, and in case of explicit usefulness, mentioning it explicitly is equally important too. This is so that your colleagues feel acknowledged and positively reinforced to collaborate with you in the future. In the short term, these colleagues are also likely to see the papers more positively vs the case if they find their assistance is not fully acknowledged.
What else can you do if you do not yet have enough opportunities to talk about your paper? We have not done so, but there are cheap as well as free software using which we can easily make a high quality screencast. For me personally, a high quality screencast provides 80% of the benefit of watching the talk in person. Much of the benefit of the remaining 20% can also be obtained if there is an open forum associated with the screencast to ask questions which can either be answered by the authors or other viewers in a relatively short time. Readers do not have the patience unless they are genuinely interested in your result. And expect to count the number of the latter on your fingers.:)
An insider's view of FOCS:
What's specific about paper reviewing these days? As part of the FOCS committee we had access to reviews submitted by the previous STOC committee. We paid a great deal of attention to whether the version we had had responded to the STOC PC's reasons of rejecting the papers. Similarly expect STOC 2008 PC to have FOCS 2007 PC's reviews available. The intersection between STOC 2008 PC and FOCS 2007 PC is nonempty. Even if you think FOCS PC misunderstood your paper, and responding to those misunderstandings would make the paper less readable, you should still try to respond to those misunderstandings instead of ignoring them. In such cases you can respond to those misunderstandings either in appropriate footnotes or in a one page appendix in the end. If your footnotes and appendix are just for STOC PC, do mention "for the reviewers only, will be removed from the published version."
What about the feedback that FOCS PC kept confidential and did not transmit to the authors? This part of the feedback must not be used by STOC committee for three reasons. First, it was understood that only FOCS PC share that feedback. Second, this part of the feedback was a part of the process and not the net outcome. The net outcome ideally must be included in the "send to author" part of the feedback. Third, since this part of the feedback was not transmitted to the authors, they can't be expected to respond. If this part of the feedback did contain a reason why the paper should be rejected then authors must be sent the reason. If this was not done in some cases, then STOC PC must work hard to rediscover the same reason for rejection.
This is my view from both having submitted (and received rejections) papers as well as been part of various PCs. I hope these give you additional practical tical tips on how to best position your papers. I welcome other ideas so that we could continue to improve the quality of our submissions.
Thanks,
Kamal Jain.
Note: FOCS means FOCS 2007. STOC means STOC 2008. Previous STOC means STOC = 2007.
Monday, November 05, 2007
It was a stupid question!!!!!!!!!! or...
For every coloring of R (the reals) with a countable number of colors there exists x,y,z,w of the same color such that x+y=z+w.
And I pointed out that when I asked this in seminar I got 5 thought it was TRUE, 4 thought it was FALSE, 5 thought it was a STUPID QUESTION.
The answer is: ITS A STUPID QUESTION. More rigorously the following is true and was proven by Erdos:
The statment above is true iff the Continuum Hypothesis is false. (See this (pdf) or this (ps). for an exposition of the proof.
SO, what to make of this? This is a natural question that is ind of ZFC. How Natural is it? Erdos worked on it, not some logician looking around for a problem to be ind of ZFC.
Does this make us think CH is true or false? Actually, more is known:
Let L(x_{1},..., x_{n}) be a linear form over the reals (but not x_{1}x_{2}). If CH is true then there is a coloring of the reals with a countable number of colors such that there is no e_{1},..., e_{n} which are all the same color such that L(e_{1},..., e_{n})=0. (Exposition of proof in same document linked to above.)If CH is true then the entire theory of countable colorings and linear forms is known. And boring. If CH is false then much more interesting things happen. Jacob Fox proved the following:
Let STAT(s) be the statement
For every coloring of R with a countable number of colors there exists x_{1}, x_{2}, ..., x_{{s+3}} such that they are all the same color, and x_{1} + sx_{2} = x_{3} + x_{4} + ... + x_{{s+3}}THEN STAT(s) is true iff 2^{ℵ0} > ℵ_{s}
Jacob Fox is also (judging from his resume) not a logician. He is a combinatorist. Actually he's a graduate student so it may be too early to say what he is.
To determine CH should we use its consequences as reasons for or against assuming it? Even if we do, do you want the entire theory to be known and boring? I ask this nonrhetorically. See Opinion 68 of Zeilberg's blog or The papers of Penelope Maddy: believing the axioms I. and believing the axioms II.
Friday, November 02, 2007
Equations and Colorings: Rado's theorem
For every 17coloring of N (the naturals not including 0) there exists x, y, z such that x,y,z are distinct x,y,z that are same color such that 2x+3x6z = 0It turns out that this is FALSE. We'll call a set b_{1},...,b_{n} REGULAR if
for every c, for every ccoloring of N, there exists x_{1},....,x_{n} such that x_{1},....,x_{n} are all the same color, and b_{1}x_{1} + ... + b_{n}x_{n} = 0The following is known as (abridged) Rado's Theorem. Rado proved it in 1933.
(b_{1},...,b_{n}) is regular iff some nonempty subset of the b_{i}'s sum to 0.For an exposition of the proof see Ramsey Theory by Graham, Rothchild,and Spencer or see my writeup
NOW here is a question to which the answer is known, and I'll tell you the answer in my next post.
TRUE OR FALSE:
For every coloring of R (the reals) with a countable number of colors there exists distinct x,y,z,w x,y,z,w same color x+y=z+w.When I asked this in seminar I got
 5 thought it was TRUE
 4 thought it was FALSE
 5 thought it was a STUPID QUESTION.
Thursday, November 01, 2007
Do we root for how a problem will go?
When you are working on a problem do you have a rooting interest in which way it goes? Sometimes yes, sometimes no. A story:
A 3free set is a set with no arithmetic progressions of length 3. Large 3free sets of {1,...,n } were used in the best known Matrix Multiplication algorithm. It is known that there are such sets of size n^{1o(1)} but there cannot be such sets of size &Omega(n) (slight tighter results are known).
I was finishing up a paper on large 3free sets. The paper was not about applying these to anything; however, there was a short sections that mentioned some applications. I needed to know, just for some refs and background knowledge, if larger 3free sets would lead to better Matrix Multiplication algorithms. So I emailed some people involved with Matrix Mult and one of them, Robert Kleinberg, responded. To paraphase the emails back and fourth he said the following (italics are mine):
The known algorithm uses that there are 3free sets of {1,...,n} of size n^{{1o(1)}}. Improvements to the current constructions of large 3free sets will not help matrix mult algorithms. To improve matrix mult algorithms you need sets with more complicated conditions on them. Sorry the answer is not what you wanted it to beActually I was happy to know this. I did not really have a rooting interest. Do we root for a result do go a certain way? Do we want to see P=NP (better algorithms) or P\ne NP (better crypto)? (I'd go for better algorithms and let the crypto people find other problems to base systems on some of which I think has already happened.) Do we want to see P=BPP (confirm our current intuition) or P\ne BPP (confirm our 1980 intuition)? Do we want to see GI\in P or GI \notin P? Do we want to see PH collapse or not collapse? Do we have a rooting interest in any of these problems?
I would think algorithms people root for finding faster algorithms rather than showing a problem is NP complete. Complexity people are happy to either seperate or collapse classes. If only we do it more often.
Monday, October 29, 2007
Stoc seeking papers that...
Since I was explicitly asked to publicize this, I assume they really mean it.
Submision Deadline: 7:59PM, EST, Nov 19.
Friday, October 26, 2007
THANKS to Nicole's FOCS blogs and her positive outlook
THANK YOU NICOLE!(Would have done this yesterday but if I had delayed getting the WOLFRAM PRIZE information out there I would have gotten at least 10 more emails telling me to post it.)
The one thing that struck me the most about Nicoles FOCS blogs is the positive outlook usually missing from discussions about theory. If you look at this blog, other blogs, or just talk to people in theory, you usually read or hear negative comments like these:
 FOCS is biased
 STOC is too expensive
 Theory is underfunded
 Australian actresses are plagiarizing my quantum mechanics lectures to sell printers.
 Back in the good old days people worked on important problems. Now they just get incremental results.
 Bring back Lance!
Thursday, October 25, 2007
Wolfram Prize won! There IS a (2,3)UTM
Congrads to Stuart Kurtz, Lance Fortnow, and Kathryn Cramer, Jon Katz, and Katrina LaCurts NOT for winning the prize but for being the first ones to tell me who won the prize so I could post it. For that they win... a mention in this blog.
Here are some websites about it, most of them emailed to me by Kathryn Cramer.
 write up in nature
 Stephen Wolfram's blog!
 Smith's 44 page proof!
 New Scientist Story
 Alex Smith's Photo!
 Geomblog scooped me here
 Live Journal
BACK TO BILL:
How important is the result? Alex Smith got $25,000 for it. The market has spoken, the result is important.
Wednesday, October 24, 2007
FOCS VIII
And it's over! The 48th FOCS ended at 6.10pm with a talk on "The Computational Hardness of Estimating Edit Distance". About 50 brave souls lasted the whole three days.
Overall it was a really great FOCS. The results were good. The company was good. I have to admit, even the food was generally pretty good!
See you all next spring at STOC in Victoria.
FOCS VII : Funding? NSF? whats it all about?
Funding status report: I'm not really the right person to blog about funding since I have never yet applied for a grant. From the business meeting, it seems like a lot of people are doing a lot of hard work to funnel more of the NSF budget into our hands. They seem to have had some success. There are two new initiatives  CDI, Expeditions  and several old ones which now have more money than before  ToC, SING. Funding rates seem to be around 25% (33% for CAREER). (An aside, maybe we should also try in an organized way to funnel more of the federal budget into the NSF by, e.g., writing our representatives in congress  you don't have to be a citizen to do this  or through PR campaigns.)
But you can find all this info on the NSF website. What you can't find on the NSF website is how it affects us young academics. I am about to start my first faculty job, and funding has suddenly become a very real issue for me. I see these numbers, I hear about these politics, and I am totally in the dark. I have never written a proposal, never even read a proposal. I don't know how to play the game. I know my senior colleagues will help me through this process, but that does not reduce the anxiety. I suppose every career path has rites of passage like these. The thing is some rites of passage are fun. I could be wrong, but I'm not looking forward to this one. ~
FOCS VI Local Arrangements AND the future of FOCS!
The business meeting was fun thanks to Mihai!
Local arrangements: First, let me say how wonderful the local arrangements
were this year, a sentiment I've heard from many others here. Thanks so
much for making this FOCS happen.
Claire gave a very detailed account of the local arrangements. The general
message seemed to be that things are expensive. Expenditures this year
reached $100K. The usual culprits were at fault  food ($265 per person,
total of $66,000), paper proceedings ($32 per person, total of $11,700), PC
meeting/registration fees ($12,000), room/equipment rental ($4,200).
Everything sunk in when it was announced that we're looking at a $525
registration fee for STOC 2008 in Victoria, admittedly thanks in part to
the falling dollar.
The usual debates ensued  paper vs CD vs online proceedings,
catered lunch vs onyourown, alternate conference venues.
Let me capitalize on my journalistic duties to further my personal
opinion on these matters: online proceedings (and ideally someday
online PC meetings) are much more environmentally friendly.
For me, this is enough. But, besides environmental and monetary costs,
online proceedings are also easier to access after the meeting and can
include media beyond print, e.g. slide presentations, videos of talks,
etc. (see, for example, the excellent wiki of FOCS 06 built by
Amin Saberi).
People who really want paper proceedings can go to Kinko's with a
printout of all the papers and pay $50 to bind them.
But honestly, I'm getting tired of this annual debate.
Let's just do it my way. ;)
Tuesday, October 23, 2007
FOCS V Report from Prog Comm.
(Note from Bill G: This is one of several posts Nicole will be making from the Business meeting.)
Program committee report: Another congrats is in order. No matter what you think about the distribution of topics (see below), you can't deny that the PC did a great job this year. I was especially impressed by the extensive feedback, both internal and external, on submissions; the comments were thorough and explicitly stated the PCs reasons for their decision. Now for the statistics, well, here's the list that was presented at the business meeting: The number of submissions: 302. The number of accepts: 66. Below is a topic that there were papers submitted on, followed by how many submitted,and how many accepted.
 Algebraic/Numerical Computation (14, 1)
 Algorithmic Game Theory (27, 5)

Algorithms 85
 Approximation (35, 9)
 Geometric (8, 2)
 Graph (17, 1)
 Randomized (14, 4)
 Streaming (6, 2)
 Misc. (15, 0)
 Combinatorics (2, 0)
 Computational Biology (2, 0)
 Computational Complexity (30, 14)
 Cryptography (20, 7)
 Data Structures (6, 2)
 Geometry (13, 3)
 Learning (7, 0)
 Logic/Proof Complexity (11, 2)
 Parallel/Distributed Computation (15, 1)
 Property Testing (10, 5)
 Quantum Computing/Crypto (25, 6)
 Random Structures (7, 2)
 Misc. (11, 0)
 Out of Scope (6, 0)
 P = NP (1, 0)
FOCS IV
I remember taking writing classes in high school. We had a series of assignments emphasizing different writing techniques and topics. But each assignment started with the same question, the question which set the tone for the entire piece of work. Who is your audience? The importance of this question was the most valuable lesson I learned in those classes.
I've now attended about a quarter of the FOCS talks  all the ones close to my area and a smattering of those completely outside my area  and it seems to me that there are two types of audiences in every talk. There are the locals, those that are intimately familiar with the research area of the talk; and there are the tourists, those that want to explore something new.
How do you speak to such an audience? Most speakers seem to split the talk into two parts: accessible introduction/overview/problem statement and areaspecific implications/proof techniques. And then they have to pack it all into 20 minutes. The result? Minds wander. What can be done about this? Longer talks to allow for a smoother rampup to the technical details (and hence fewer papers overall)? Parallel sessions (something FOCS has toyed with in the past)? Or maybe nothing? As my grandmother used to say, "you can please all of the people some of the time and some of the people all of the time but never all of the people all of the time."
Monday, October 22, 2007
FOCS III
The first day of FOCS is over. The highlight of the afternoon was the talk by Nancy Lynch, winner of the Knuth Prize. She began with, as one attendee put it, a nostalgic synopsis of FOCS/STOC from her first Denver 1972 conference in a cheap hotel across from a dirty movie theater on through the splintering of theory and distributed computing in the 80s. She then launched into a very accessible description of her famous paper on the impossibility of distributed consensus. The talk ended with an overview of current and future work in the field.
I think everyone in the audience was pretty satisfied with her outlined research agenda involving models of distributed computing on mobile networks until the air traffic controller example. She primed us by suggesting that her research could replace traffic lights with virtual traffic lights, which made me tense up slightly. Then she suggested we could even replace human air traffic controllers with virtual ones. While we all understand the benefits (e.g., you can have controllers over the ocean, machines don't get tired, etc.), I think we all had a sort of collective gasp. I guess at the end of the day, I just want to know there's a human behind it all, attentive and directly in charge.
One more thing I think is worth mentioning – this is the first Knuth prize (out of 8) awarded to a woman. This same year was the first year (out of 41) that a woman, Fran Allen, won the Turing award. This trend is both alarming (it took 41 years?) and encouraging (ample research and personal experience demonstrates the significance of female role models for professional women). Congratulations and my sincere gratitude to you both for paving the way.
Sunday, October 21, 2007
FOCS II
Just finished the morning sessions of day one. I guess it's time for the standard disclaimer – the talks I blog about are those I happened to attend and should not be interpreted as the "best" or even my personal "favorite" results, etc. etc. etc.
So about the sessions. Session one started at 8.30 AM and I'm embarrassed to admit that despite being the "guest blogger" of FOCS I missed the first talk. Somehow research before 9.00 AM is akin to hard liquor before breakfast for me. I just can't stomach it. I caught the end of the talk though, and was shocked that the room was packed! I took a picture, try and see who isn't there. :)
The second session was much closer to my research area – algorithmic game theory – and hence I got much more from those talks. One particular nice result was that from the paper Mechanism Design via Differential Privacy. The authors introduce a new solution concept for mechanism design which resolves many of our frustrations with dominant strategy mechanism design, and they do so through a creative connection to a seemingly unrelated field – privacy.
FOCS I
I wake up blearyeyed and jetlagged at 6 AM begging of myself WHY? Why do I subject my body to such torturous transatlantic flight for three days of, of what? Of talks of which I will attend at most a quarter? Of hotel banquet food? Of aching back muscles from lugging around massive proceedings and laptops bundled together in free canvas tote bags that I don't really want anyway?
For me, the answer is the people, my friends, my colleagues, their quirky interests and insightful comments. It's the research in the corridors, the animated technical arguments over the lunch tables, the great stories that get told by a diverse set of people from a diverse set of backgrounds.
Basically, it's like a big family reunion. But families you are born into. How do you get born into the FOCS family? I remember my first FOCS – Las Vegas 2001 – feeling alone, isolated, shy. Now I feel a part of the family, accepted into this community due in part to my papers, yes, but also labels that were really a matter of luck. What becomes of all those people that didn't have my luck?
Wednesday, October 17, 2007
Why do I find this result interesting MOD 17 SAT
Let SAT_{17} be the set of formulas such that the number of satisfying assignments is a multiple of 17.
If SAT_{17} ≤_{m} S, S sparse, then SAT_{17} ∈ P.This is one of those results where the proof in the literature is hard because they prove something far more powerful (btt reductions and more). Hence I have my own exposition that I made for my class here.
I presented it in class recently and the students questioned why it was interesting. I can usually answer questions like this (even about such things as the Polynomial VDW theorem) but this one is harder to say. I DO find it interesting (not just the proof, but the result) but can't quite say why.
SO, here is my challenge: either tell me a reason the result is interesting OR tell me a result that YOU find interesting but can't quite say why.
Monday, October 15, 2007
A more intelligent SPAM discussion
Is Spam a big problem? I contend that it is and that it is going to get worse. Some random thoughts, some of which are what to do about it.
 Make it illegal or make the penalties tougher. I don't know what the current legal status is, but even with tough laws this is hard to enforce because (1) What is spam? and (2) it would require international cooperation.
 We could try just making spam that is trying to rip you off illegal. I'm sure it is. But sometimes its hard to tell what is a rip off and what is not. The ``Nigerian Billionaire'' scam is clearly a ripoff (does anyone still fall for that?) but the ``you can get viagra at a cheap price'' might not be. The ``we can get you out of debt'' is much harder to judge since (from what I understand) they pay your debts, charge you an enormous interest, but let you pay it off over a much longer period of time. It may well be legal but unethical. It may even be legal and ethical.
 Keep designing better software to block spam. This is the current solution, and it works pretty well, but its getting harder, and too much real email is being blocked. Also, this is more of why I think its a big problem we (as a society) spend an awful lot of time and effort on this.
 As more people know that these are scams and less people fall for them, will the scamspams stop? Can we educate people so they know better?
 Fighting back there was an article in the Atlantic Monthly about people who scam the scammers with success. But there are not enough of them, and they are not that effective, to be a real deterrent.
Friday, October 12, 2007
Spam Assassin
Is this a crime? Should it be? Consider the contrast:
 Killing one person. How many people suffer and how much? The victim of course. Maybe his family and friends. But not that many people. So this is High Impact on a Few People.

Spamming 100,000,000 people. How many people suffer
and how much? Far more than 100,000,000 suffer.
Why so many? The following suffer:
 Software is more expensive because you need to put in spamassassin's.
 People who send legit email that is blocked. This has caused confusion not worthy of a bad sitcom.
 The people who fall for these spamscams.
 The Nigerian billionaires who really do want to give me $5,800,000 dollars. Its hard to tell the real ones from the fake ones.
{ s_{1}, s_{2}, ..., s_{n} } is the people that suffer by the spammers death. Person s_{i} suffers a_{i}.
{ t_{1}, t_{2}, ..., t_{N} } is the people that suffer by the spammers action. Person t_{i} suffers b_{i}.
Its safe to assume that n is MUCH LESS THAN N and that b_{i} is MUCH LESS THAN a_{i}. If
a_{1} + a_{2} + a_{3} + ... + a_{n} < b_{1} + b_{2} + b_{3} + ... + b_{N}
then the spam assassin should not be charged with a crime.
The more serious question here is how to deal with spammers who transcend boundaries and seem outside of the law. The Russians may be onto a solution...
Wednesday, October 10, 2007
Is Computer Science a Science?
 Calling something science, engineering, art, or business is not an insult or a compliment.
 A topic is a science if it has a lab where there is the potential for danger. Physics has radiation, Chemistry has explotions, Biology has germs. So they are sciences. Neither Math nor Computer Science has those.
 Hence, asking if Richard Stallman is a computer scientist is not really a question. So perhaps we need a different term. `Computer Programmer' is a fine term and we know what it means. How about if we call ourselves `Computer nonprogrammers'? Depends if you consider LaTeX a programming language (it is TuringComplete).
Friday, October 05, 2007
The Free Software Foundation and Richard Stallman
 He talked for 1 hour 45 minutes. This is probably 45 minutes too long.
 When I say he talked for 1 hour 45 minutes I am being literal no slides, no blackboard presentation, just talking. This may be because to use technology he would have had to use Software from a company that he does not approve of.
 He speaks of free software as a human right. He speaks of it as the worst evil in the world. There are worse evils in the world; however, all good causes need true believers, and he is one.
P.S. Richard Stallman is not the most famous computer scientist who knows me. Serge Brin, cofounder of Google, had two courses from me as an Undergraduate. I definitly wish I had gotten involved with Google early early on since its a good product and it would be nice to be able to contribute to my bank account in this way.
Wednesday, October 03, 2007
If pigs could fly then bacon would be cheaper
SAT has poly size circuits.
The Poly Hierarchy collapses.You probably think both are false. Which statements truth would surprise you more? Personally I think SAT has poly size circuits would surprise me more.
KarpLipton Theorem:
If SAT has poly size circuits then Poly Hierarchy Collapses.Does this really make your belief that SAT does not have poly sized circuits stronger? You already believed that. I know of one theorists who tells me that she believes SAT does not have poly sized circuits MUCH MORE than she believes that PH does not collapse. Hence this theorem does not tell her anything.
If you have
(unbelievable statement A) > (unbelievable statement B)what do we then know that we didn't know before? We know that A is MORE unbelievable than B, I suppose. We seem to have taken
BLAH > P=NPas the gold standard in showing that we believe BLAH is false and
BLAH > PH=\Sigma_2^p
BLAH > PH=\Sigma_2^petc. as forming a hierarchy of nonbelief.
This is a nice picture, but it may be that BLAH is just not that believable in its own right and does not need to imply something like $\PH = \Sigma_3^p$ to give NOT(BLAH) street cred.
Monday, October 01, 2007
DealNo Deal: MORE $ = LESS Interesting
The episode I saw showed something wrong (at least in my opinion) with the way they are promoting the show during premiere week. They have upped the amount of money to be a max of $4,000,000 (instead of $1,000,000). I saw the following (this might not be quite accurate but makes the point) There were 6 numbers left:
 $5,000
 $10,000
 $20,000
 $100,000
 $1,000,000
 $4,000,000
A question like `would you take $70,000 or take the chance that you get $400,000' is mildly interesting. But the $700,000 is to large to not take. Hence the game gets less interesting mathemtatically.
Given a persons utility function (or something like it) what would be the optimal max amount (and optimal set of amounts) to maximize the games INTEREST? This question might be interesting.
Thursday, September 27, 2007
WHERE to apply to grad school?
Today's topic is WHERE TO APPLY?
I would like YOU (the readers, and time magazines MAN OF THE YEAR for 2006) to comment on:
 IF a student wants to do COMPLEXITY THEORY where should she go?
 IF a student wants to do COMBINATORICS (in a math dept) where should he go?
 IF a student wants to do XXX (in a YYY dept) where should ZZZ go?
Tuesday, September 25, 2007
Andrej (Andrey) Muchnika late memorial
Andrej (Andrey) Muchnik died unexpectly last March, but the news didn't spread out, so I am thankful to Lance Fortnow and Bill Gasarch who give me the opportunity to write a few words about him. His death was a sudden blow not only for his family (his parents, Albert A. Muchnik, of Muchnik  Friedberg solution of Post problem, and Nadezhda M. Ermolaeva; both were students of Petr S. Novikov; and his brother Ilya) but also for all his colleagues.
Andrej, whom I knew since our undergraduate studies, was not only the brilliant mathematician, but a deep thinker. He lived in his own world  a very rich one that was not completely unrelated to a "real life" (i.e., the mess around us), but still clearly separated from it, and the interactions between these two worlds were quite difficult and often painful. His mathematical interests were driven by internal logic of the subject, not the current "fashion"; sometimes he rediscovered an old result not knowing about it; at some other times his results (being not published or published only in a short note) were rediscovered later by others. Probably his most known result is an elementary proof of Rabin's theorem (decidability of secondorder monadic theory of two successors), invented while Andrej was a fourthyear student, and its generalizations; my personal favourite is one of his last results saying that for any strings A and B there is a string C such that C [length] is about K (AB) [conditional Kolmogorov complexity]; K(CA) is negligible and K (AB,C) is negligible (all up to logarithmic terms).
a seminar in Moscow that was started by Kolmogorov himself; the work of this seminar and its participants was deeply influenced by Andrej, and I think that all we agree that most nontrivial ideas discussed in this seminar and most interesting results obtained by the participants of the seminar were due to Andrej (or at least inspired by him). Personally I am extremely grateful to him for all his support and encouragement and very sorry that I didn't tell this to him explicitly and didn't help him enough while he was alive.
See the seminar site note (both Russian and English) (written mostly by Andrej's teacher and friend, how helped him a lot, Alexey Semenov)
some papers of Andrej (not all  we are still trying to prepare some unfinished papers for publication) can be found here
Monday, September 24, 2007
The Amish and Cell Phones
A long time ago they banned phones. They later made some allowances for having a phone booth for emergencies, but no phones in the house, for it would disrupt family time (the ultimate DONOTCALL list). But more and more Amish are doing business with the outside world and as such phones are needed. More and more of them are using Cell phones (see Look whose talking).
I do not think Cell Phones are the real issue here. The real issue is that we now have technologies that an individual can use without the permision of the community. We also have dualuse technologies, so rules like `you can use it for business but not for entertainment or gossip' may be hard to control.
I was told by an Amish Man that the Bishops have ruled against Cell Phones and computers. But as batteries get better (and most of them have contacts on the outside who can recharge for them) I'll be curious how well this holds up. Will the authority of the bishops and the desire to hold the community together be enough to make the rules selfenforcing?
Friday, September 21, 2007
Math on TV
 The list of suspects looks random but we know that its not. To solve the case we use the NisanWigderson derandomization technique.
 We know the murder took place within this 5 block by 5 block area. We know that there were 10 people interacting to plan it. We can solve the case by looking at both the space and the interactions and then applying the LundFortnowKarloffNisan theorem that changes space into interactions.
Monday, September 17, 2007
Is Immunity Interesting?
For all computable T there exists a decidable set A such that A ¬in DTIME(T(n)).I then had on the homework
For all computable T there exists a decidable set A such that, for all Turing Machines M that run in T(n) time there exists an infinite number of strings x such that A(x) &ne M(x)I then had extra credit
For all computable T there exists a decidable set A such that, for all Turing Machines M that decide A, for almost all inputs x, M(x) takes more than T(x) steps.Katrina LaCurts, one of my students (who is thrilled to be mentioned by name in this blog!) asked the following: Is the HW and Extra Credit just to reinforce knowledge OR is the notion of differing infinitly often an important topic within complexity theory?
How important is the notion of sets differing infinitly often? A quickanddirty measure is to find the number of papers on this topic. A quickandditry way to do that is to grep `immunity' in Joel Seifras's Theory Database and then edit. Once done I get the following list
So I could answer Katrina, there are at least 21 papers on this topic That shows people have worked on it (and some quite recently) but does not quite answer the question. Hence I ask my readers:
Once we have that, for all time bounds T, there is a computable set A ¬in DTIME(T(n)), why do we care about getting an A that differ infinitely often, or other variants? More generally, why is the notion of having two sets differ infinitely often important. I ask nonrhetorically and politely. Note that, no matter how you answer, Katrina still has to do the HW.
Thursday, September 13, 2007
Question and Metaquestion about Students emailing you problems
Hi Bill,This email raises several questions and metaquestions
I am a grad student in combinatorial optimization, and I have a question that I was hoping you could answer: does "FOO is APXcomplete" imply "FOO is MAX SNPcomplete", viceversa, or neither?
To be honest this might be very simple... but given that this is essentially the domain of computational complexity I was hoping that either you would know the answer, or otherwise that your blog's readers might have some suggestions. (Basically your blog is currently the main source of computational complexity to my brain, so it seemed natural to ask you when I became confused.)
My impressions from reading up are the following:
 APX is the subset of NP optimization problems with constantfactor polytime approximations
 MAX SNP has a much more complicated definition
 APX contains MAX SNP but I don't know if the containment is known to be strict
To motivate my question, many papers say "the FOO problem is MAX SNPhard and also APXhard" but is there currently a point in stating both? As I researched the topic, I found that the reductions allowed in the definition of "APXhard" and "MAX SNPhard" are apparently slightly different... and around here my confusion set in.
One compendium, at least, uses simply "APXhard" by convention: here
I hope this is up your alley, but if not then no worries.
Sincerely,
NAME DELETED FOR THIS BLOG POSTING
 The question on APX might be interesting.

Is this a HW question? Is she cheating on it by asking me?
Should I answer it? My inclination on this one is that
its NOT a HW, it is legit. However, I don't know the
answer, but if one of you does, by all means post
(she knows I am posting this to the blog).
By contrast, someone once
posted to a readnews group (remember those?)
Someone out there please help me with this problem: why is {a^n  n prime} not regular? I'm not a student asking for the solution to HW 4, problem 2. Honest I'm not!!
Looks like a student doing a HW problem.
 ``your blog is my main source for complexity theory'' A scary thought. She needs to get more sources like Luca and Scott's blog. Or maybe books (remember those?).
Wednesday, September 12, 2007
SODA papers are out. Plus...
This raises the questions of which conferences have the most complexity theory in them (say by percent). Here is my rough guess.
 COMPLEXITY
 MFCS
 ICALP
 FOCS/STOC
 LICS has an occasional article on descriptive complexity)
 SODA has an occasional lower bound. The few SODA papers I've been asked to subreferee have all ended up being rejected. The very fact that I am being asked to subreferee is an indicator that they are out of scope.
 COLT/ALT and the other Learning Theory Conferences.
Tuesday, September 11, 2007
Search Engines gone wild!
 Bounded Queries in Recursion Theory by Gasarch and Martin. This hit makes sense.
 Handbook of Discrete and Combinatorial Mathematics edited by I have a 4page chapter on computability. Does this hit make sense? If I say NO then I have to say say how long a book chapter has to be before it makes sense to have a hit. So I'll say YES.
 The Complexity Theory Companion by Hemaspaandra and Ogiwara. I was acknowledged in the acknowledgments. Is this hit deserved? NO! (I got quite a few more of these types of hits, some for proceedings where one article acknolwedged me.)
 An Introduction to Quantum Computing by Pittenger. This book is in the same series as my Bounded Queries books, so the back of the book has a list of all the books in this series. Hence I got a hit. This is nuts!
amazon needs to fix its search engines to be LESS good. ~
Friday, September 07, 2007
Quantum Computing and Quantum Phy.
You don't have to understand Quantum Mechanics to work in Quantum Computing.Thats a good thing since I've also been told
Nobody really understands Quantum Mechanics.I've also been told
You don't have to have studied Quantum Mechanics to work in Quantum Computing.I am skeptical of that. However, I was wondering about the other end if you do have a background in Physics does it help? So I asked Fred Green (of Green's Conjecture) about this since he has a PhD in Physics, works in a computer science department, and works on Quantum Computing. Here is what he said.
Learning quantum computing helped me understand quantum mechanics better. As a physicist I never thought about measurement theory or entanglement, which were foundational issues, irrelevant to what I was doing. In quantum computing, we reason directly about these things all the time.He didn't quite answer my question, but he raised a more interesting question. Should quantum physicists learn quantum computing?
In an earlier post I noted that Jerry Seinfeld said Comedians should do lots of proofs. Not for their actual routines, but to better practice their craft. Perhaps its also good advice for people who want to be quantum mechanics (like auto mechanics, but on smaller cars) to learn some Quantum Computing. Not for their actual research, but to better practice their craft.
Tuesday, September 04, 2007
Social Process and Proofs of Theorems and Programs
 When a theorem in math is proven that is just the start of the process. If it is important enough it will be passed around the community and checked and rechecked. At some point if it survives scrutiny it will be accepted. (Makes you wonder about proofs in the literature that nobody reads could they be false?)
 The people working in Program Verification want to give programcorrectness the same confidence that we have in Math Theorems.
 This is not a good idea since Programs cannot be passed around the same way Math Theorem proofs can. (Makes you wonder about the Classification of Finite Simple Groups, or the Four Color Theorem which also cannot be passed around that easily.)
The comments on Program Verification do not really apply anymore since those people seem to have scaled down their claims to building tools to find bugs, and to automatic verification of Protocols written in a SPEC language, which seems far more plausible. (I'm not in the Program Verification Field so if someone wants to tell me I'm wrong, leave an intelligent comment.)
When I first read this article as a young grad students I was very impressed with what it said about math. YES, the proof is just the beginning, but constant checks and rechecks are needed.
Friday, August 31, 2007
The Koblitz Controversy: A reaction
Like many others, I was very upset by a recent article by Neal Koblitz that appears in the Notices of the AMS. I'll say at the outset that I actually think the earlier papers by Koblitz (and Menezes) contained some valid points  I don't agree with their conclusions, and I find their tone objectionable, but I still think they raise some issues worthy of further thought.
What really bugs me, however, is how much publicity Koblitz has managed to get out of this. I see him invited to give talks at many venues, but never see anyone invited to present a counterargument. (For that matter, I don't see invited speakers at cryptography conferences poking fun at the cryptographic work that mathematicians do.) This does not matter so much when Koblitz speaks at a TCSvenue (any intelligent cryptographer knows that his arguments are overblown), but I think it matters greatly when he speaks in front of an "outside" audience.
For this reason, I thought publication of his article in the Notices of the AMS was inexcusable. Even worse, this latest incarnation of his essay goes beyond being a mere "academic" argument and degenerates to namecalling and belittlement of an entire field and all the people who work in it. (And it seems pretty clear that his feelings extend beyond crypto to CS at large.)
As promised, I have written a letter of complaint to the editors of the Notices. I don't know if it will get published (it is also a bit long), but it is available here (pdf) or here (ps)
P.S. After sending this post to Bill I noticed that Oded also wrote a letter to the Notices of the AMS.
Wednesday, August 29, 2007
Theory Starts Here! (Informatics Olympiad)
A while ago, I promised the community around the International Olympiad in Informatics that I would bring them into the conscience of the theory community, and now I am trying to fulfil this promise. I have written a short " practical guide " of what we, as the theory community, should know and why we should care. Below is your executive summary:
Understand. What happens when you cross homo ludens with scientists? Imagine the Olympic Games, where you throw Computer Science into the arena. In short, you ask each country to send their best 4 high school students, who then compete in solving algorithmic questions.
Appreciate. The problems given in the contest are meant to challenge the brightest young minds in Computer Science. For a quick reference, problems in [CLRS] are "easy". Many questions asked are truly original, and thus can be fun even for a mature audience. Many questions can also make excellent assignments in algorithms courses (with or without a programming component).
Care. Informatics Olympiads are part of our intellectual tradition, and a part that should make us proud. The parallel olympiad in Mathematics is highly regarded in that community. A theory community that embraces the Olympiad is a stronger theory community.
More practically, the Olympiad gives us outreach to the high school level for free. We need a healthy flow of new talent, and the olympiad is already motivating hundreds of the smartest kids to learn theory. Our awareness can tell them that they are on the right path.
Most practically, we should be paying attention to it in the admissions process. The International Mathematics Olympiad, which has been running since 1959, has had a very significant impact on theory.
Our very own Informatics Olympiad is much younger (1989) and the contestant are only now coming of age. However, check out this list for notable theorists coming straight out of the Olympiad. If you want to know how well people are doing on average (and be impressed!), check this out. It is a statistic about the career paths of all Romanians who ever participated in the Olympiad.
Monday, August 27, 2007
RANT about Electronic Refereeing
I got a request to referee a paper that I really could not turn down since I'm one of the few people who is qualified This may be reason enough to reject if very few people could referee it then perhaps the topic is too obscure. However, obsurity of research is not todays topic. Today's posting is a rant!!
BEGIN RANT
The request to referee was an automatic email. I then had to do the following:
 Goto a website to accept.
 Receive an email telling me how to access the paper.
 Goto another website, click on something to receive another email telling me my password and login.
 Change my password to one that I could remember. This took a while since they didn't state their rules for passwords, nor did there error messages tell me what the rules were.
 Goto another website with that password and login and register by giving my name (gee, I think they would already have that), email (ditto), school address, areas of interest, key words of interest (that was really hard it was a long list and nothing quite fit), my right thumb print, and my left eye retina scan.
 To get the paper itself the website kept on doing odd things. I called them (by telephone!) and the editor said that I was not being an idiot, the website had problems that day, and they would try to send me the paper, but they were not sure they could access it. I told them that if they did not get me the paper within 24 hours I would not referee it. They got it to me 23 hours 45 minutes later.
 I am looking forward to seeing if the website will be working when I fill in the referees report, which must be done on the web.
END RANT
I do not think I'm being a luddite to complain about this. Being a luddite (different link) is not the topic of todays post. I do not think that electronic refereeing systems using the web are a bad idea. But electronic refereeing systems are not todays posting. Todays posting was a rant!.
Wednesday, August 22, 2007
Impact of Facebook platform on CS enrollment
So why is the Facebook platform interesting? And what does it have to do with CS enrollment?
Web 2.0 entrepreneurs aim to attract millions of users to their service. The Facebook platform facilitates this by creating a highly viral environment for spreading a web service by leveraging the social network graph. In particular, when a Facebook user uses an application, his/her friends in the social network graph will know about it automatically and they might use it too, thus automatically informing their friends, and so on.
The Facebook platform may very well boost CS enrollment. After all, who cares about an uncertain job market when what you really want to do is to pursue your own startup and make millions?
For more on the Facebook platform and its potential, see this excellent keynote by Facebook's CEO Mark Zuckerberg: excellent keynote by Facebook's CEO Mark Zuckerberg
Now a question for you: as educators, what can you do to take advantage of this phenomenon to increase CS enrollment?
Tuesday, August 21, 2007
Checkers Clarification by Schaefer
Sterling: Please clarify what you mean by checkers being solved. As you can see from the discussion, there is lack of agreement on what the Science article really meant.
Schaefer: Checkers has been weakly solved. The game is a proven draw and the proof online gives the sequence of moves for white and black to achieve the draw.
Sterling: More pointedly: what percentage of the total gametree is now determined?
Schaefer: We considered 10^{14} positions out of the total search space of 10^{20}.
Sterling: If the search area was pruned, what were the criteria used for that?
Schaefer: Lines of play that were provably irrelevant to determining the final result were ignored.
Sterling: Is there even a shred of possibility that a "supposedly losing" move could in fact lead to a won position, and so certain game lines were improperly excluded from search?
Schaefer: None.
Sterling: Most significantly, perhaps, is this only a statement about 8x8 checkers, or does it generalize in any way?
Schaefer: 8x8 checkers only. The program can, however, be used to solve any game of checkers (it does, in fact, work for an 8x8 variant and 10x10 international checkers).
Monday, August 20, 2007
FOCS registration Open
Registration has opened for FOCS 2007, which will take place in Providence on October 2023. Please go to
http://focs2007.orgNote that the early registration deadline is September 20, and the deadline for reserving a room at the hotel at the conference rate is also September 20. (The hotel's regular rate is much higher.)
The Knuth Prize lecture will be given by Nancy Lynch on October 21.
A program of tutorials takes place on October 20, the Saturday before the regular conference program begins. The tutorial talks are as follows:
Combinatorial Number Theory
Recent Developments in Cryptography
Theory and Applications of Graph Spectra
Abstracts for the tutorials should be available soon.
Friday, August 17, 2007
A New Job and Journal
As an anonymous commentor mentioned on Monday, I am moving to Northwestern University EECS in January. Northwestern also hired Jason Hartline and Nicole Immorlica so I have an exciting opportunity to join an up and coming theory group without having to move my family.
In other news the ACM Transactions on Computation Theory has been approved and will be starting up soon with yours truly as editorinchief. Watch for details and get your papers ready.
Wednesday, August 15, 2007
Graduate Complexity Theory Course
 Defining TM's, TimeHierarchy Theorem. NL=coNL. Savitch's theorem.
 Cooks Theorem, some NPC reductions. Mahaney's theorem, PH, KarpLipton theorem.
 If GI is NPC then PH collapses. (This will use PH, KarpLipton. Will also need hash functions, AM protocol for GIbar.)
 If PARITYSAT is in P then SAT is in R. (This will use some of the machiney devoloped for GI.)
 Everything in PH is \le_T^p #SAT. (Toda's theorem.)
 If CLIQUE can be approximated then P=NP. (STATE PCP, give proof of some easier cases, but do not proof the full theorem or even try.)
Other topics that would be reasonable to cover: BakerGillSolovay Oracle, Hard vs Random stuff, PARITY not in constant depth, and CLIQUE not in Monotone P. Not doing BGSoracle since I'm not doing enough proofs that relativize in the first place. Not doing Hard vs Random since its a bit hard and a bit random for this level of course. Not doing Circuit Stuff since that does not fit in that well with these topics (concrete vs. abstract complexity). Any of these points are debatable.
I'll be giving out my own notes. My experience is that using other peoples notes does not work, and others using mine does not work. My notes work for students taking my course, who see my lectures, and who have access to me. But they would not be good for anybody else.