Thursday, March 28, 2019


At Dagstuhl I got a few ideas for future posts but then...

We had some discussions about STOC allowing program committee members to submit papers that I planned to post about. But then Suresh wrote a fine post on the same issue for SODA. My thoughts: PC members should not submit--no matter how you try to avoid the conflict of interest, there will always be a cloud on the process. Suresh suggest blind reviews that other non-theory conferences use, but I prefer the tiered PC system. It's fine to have PC members submit papers if the top of the tier, a senior PC or the PC chairs, makes the final calls.

I was also going to post about Yann LeCun's Facebook rant about stodgy CS departments but then Yann goes ahead and wins a Turing award with Geoffrey Hinton and Yoshua Bengio for their work on machine learning. I knew Yann from when we worked together at NEC Research in the early 2000's and let's just congratulate him and the others and let them bask in glory for truly transforming how we think of computing today. I'll get back to his post soon enough.

Sunday, March 24, 2019

Random Thoughts on the admissions scandal

In light of the recent academic scandal I am going to list ways I've heard to help get your kid into college and thoughts on how ethical they are (hint: bribing a coach to claim your kid is on the rowing team is not ethical).

1) Your kid likes (1) helping the homeless and (2)  Ramsey Theory and (3)  helping the homeless learn Ramsey Theory. Or perhaps they like  rowing or Latin or fencing or Pig Latin or....  Great! encourage them, get them books and tutors,  and whatever they need. You have an eye towards how this will look on for college admissions; however, it is your kids choice as to what they like. Also note that these activities are in addition to doing well in school, SATs, etc, not instead of it.  Perfectly ethical, though I note that this avenue is not open to poor families and in some cases even middle class families.

2) Item 1 is the extreme on a spectrum in terms of how much are the extra things the kid does there idea OR planned by you to GET INTO A GOOD COLLEGE. This item will be the other extreme, but realize there is a continuum (actually I doubt there are a continuum number of options here, but there are many in between. Maybe its omega + omega*.) You have heard that being on the chess boxing teams is good on a college application so you TELL YOUR KID that they  likes both Chess AND Boxing and should be on the team. You also hear this about being on the fencing team and knowing pig latin, so your kid can taunt their opponents like this:

youah, aint-kay ence-fay orth-way eans-bay

This might not be as bad as it sounds if the kid learns to like Chess-Boxing.  But it may be worse than it sounds if the kid rebels against all of this and becomes a crack whore.

Is this ethical? It may be bad for the kid, but it may push him into things he ends up liking. One drawback: you've HEARD that being on the chess boxing team is good for college admissions, but is it true?

And again, not open to some families.

3) Item 2 (or even 1) but with an addition: Hire a college adviser to help you. Someone who knows (or claims to know) what colleges look for- Trombone, Latin, Chess-boxing, whatever. Still ethical but I again worry about the kids future rehab bills.

4) Here is where it gets murky. The college adviser helps:

a) Polish the kids essay (my parents, who are both in English, helped polish my essay to get into graduate school (I don't recall if there was one for ugrad). They told me to use lots of `ing' words so it sounds like I am actively doing things. They also helped me figure out when recursion-theoretic is hyphenated. I got into Harvard but not MIT, so make of that what you will.) Polishing, proofreading, that could be okay. But it can slip into b or c below.

b) The adviser (or the parents) talk to the kids to find out what to write, but then writes it. Maybe the kid proofreads and polishes. Maybe not even. The adviser is  a ghostwriter. Clearly unethical but the line between helping-to-polish and adviser-wrote-it is again a continuum.

c) Adviser writes it and it is completely fictional. I once heard a rumor that a particular sample of an essay to get into med school was used  by several  med school applicant. Gee,they can't all have gotten inspired by watching their grandfather in his pajamas die of cancer. This is awful of course, but I wonder- what if the student writes a fictional essay all by themselves! Some combination of how much the essay is true and how much help you got on it is unethical. But some might be okay. Is it bad to polish stories that are basically true to make them flow more easily?  Prob not. But there is a 2-dim continuum based on both accuracy and how much help the student got.

As a side note- how much does the personal statement matter for admissions? I suspect that if an elite school gets LOTS of REALLY QUALIFIED applicants, the essay may be all that distinguishes them.So it can be important. I also wonder if people on admissions can tell if an essay is not written by the applicant. Or maybe if there is an interview that can help detect it.

5) Parents give X amount of money to the college and the kid gets in. This is talked about a lot though I don't know how common it is for someone NOT qualified to GET IN based on money. College admissions has many factors so its not quite so clear cut what NOT qualified means. Even so, if seems odd that this is not in any way shape or form illegal. It IS transparent, so I guess thats a plus. The argument I've heard is that the money is used for scholarships to fund students who get in but can't afford to go. I do not know if this is true. And this one  is only available to the top Z %, not sure what Z is, but there are people who can do 1,2,3,4 who can't do 5. I would call this unethical though colleges don't seem to think so. Or they do but they do it anyway.

6) Before I list the current scandal I want to list another issue: having a psychologist (or whoever it is who judges these things) say your kid is Learning Disabled so they get more time on the SATs. Perhaps bribing them, or perhaps its understood what you want.  Again, I do not know how common this is.  An alternative if you can't afford some of the above options, or done in conjunction with a lot of the above options.

7) The current scandal. Obviously unethical. A few things I wonder about:

a) One story was that they bribed someone to say their daughter was Learning Disabled and had to take the SAT (or whatever it was) in a separate room, making it easier to change the answers to the correct ones.  So twice unethical.

b) Some of the students  were clearly NOT qualified.

c) A parent does unethical things to get the kid into college.

The kid later lies to the parents about their grades or their plans

The parents are SHOCKED that their kids lie and wonder where the learned such behaviour!

8) Actually Item 2 --Parent has kid do things to plan to get into college-- is interesting for another reason. Are you your resume?

Imagine that Alice helps the homeless her Sophmore year in High School NOT because she cares about the homeless but because its good for college admissions.

Alice goes on to do other things that look good for college, NOT because she likes them or cares, but just to get into a good college.

She gets into an elite college

Did they take her in the hope she would KEEP doing these things or because she is the KIND OF PERSON who does these things?

And it gets weirder- she DOES keep doing these things since she's heard its good for Business School (disclaimer- I do not know if its good for B-school)

More generally, she keeps doing things she doesn't care about to advance. So her outward self really is doing good deeds and such, but her heart is not in it. So if her college or B-school or Job hired her because she DOES these things, that is NOT a lie. If they hired her because they want this KIND OF PERSON then... its a lie but I'm not sure what to make of that.

9) Is there ANY reason to have legacy matter for admissions? This seems like the dumbest and most easily fixed aspect of the whole process.  I have never heard a good argument for it. Ever.

10) College Sports--- that's an entire blog post or book all by itself, so I won't go there.

11) One can argue whether helping the homeless, or being on the rowing team, or teaching the homeless how to row, should matter for college anyway. But lets assume that its legit to want people at your college who have lead interesting lives. So charity work or sports might be a MEASURE of that. But beware Goodhart's law:

                          When a measure becomes a target is ceases to be a measure.

The recent scandal is Goodhart's law on steroids.
(NOTE- I had in earlier version `Goodwin's law' but a commenter corrected me and reminded me that Goodwin's law is that if an internet discussion goes on long enough someone will be compared to Hitler. I wonder if that also applies in discussions by Nazi's.)

12) Does getting into an Elite College really increase your income or happiness (these are two very different questions) over the course of your life? I do not know-- if you do, please comment.

13) (ADDED LATER) A commenter pointed out that one could also go to a school outside of  the USA that values proficiency in the chosen discipline over the items above. Excellent question that raises a few more:

Do schools outside of the USA hold Americans (or for that matter any non-citizen of their country) to a higher standard for admissions? I ask non-rhetorically.

If you get a degree from outside of the USA will that help or hurt your job prospects in the USA? Of course this depends on the school you goto, but even with that I do not know the answer.

Thursday, March 21, 2019

Back at Dagstuhl

Participants and Their Research Interests

This week I'm in Germany for the Dagstuhl workshop on Computational Complexity of Discrete Problems well timed for Georgia Tech spring break. No Bill, so no typecast, no family, just a bunch of fellow theorists. New this year, beer.

Dagstuhl always had bottled beer (and wine), after all this is Germany. However, Ronen Shaltiel is living his lifelong dream of bringing a keg to Dagstuhl. Turns out Dagstuhl had a refrigerator/tap for a beer keg, one only needs to order and pay for the beer. Ronen's daughter designed a special logo, though the keg contains Bitburger, a fine German pilsner. Prost to Ronen and thanks for the beer.

Of course the fun is hanging with colleagues old and new. Talking about open problems old and new. Used to solve more of them back in the day, now it seems harder.

I did learn a new old theorem, planarity testing, whether you can embed a given graph in the plane so no two edges cross, is computable in log space. In 2000 Eric Allender and Meena Mahajan showed that you can test for planarity in symmetric log space, basically the complexity class whose complete problem is undirected connectivity. In 2005, Omer Reingold famously showed that undirected connectivity is computable in log-space. Thus planarity testing is in log-space, a result you might have missed if you didn't know both papers.

This came out in Eric's talk on his work with Archit Chauhan, Samir Datta and Anish Mukherjee showing that checked whether there is a directed path from a given node s to a given node t in planar graphs can be computed by concurrent-read exclusive-write on parallel random-access machines in logarithmic time, and thus likely weaker than directed s-t paths on general graphs.

Sunday, March 17, 2019

Third Poll on P vs NP and related Questions is out now! And the winner is Harambe!

I took a poll of the theory community (and others) about P vs NP and related issues in 2002, 2012, and 2019 (sorry its not an arithmetic  sequence --- read the third poll article to see why). The 2002 and 2012 polls are on the web (see here and here ), and now the third poll is out and its here or here . All three appear in Lane's Complexity Column in SIGACT News.

I'll give some highlights and thought about the third poll, but for more read the article. Or read all three and see how opinions have changed over time.

0) How many respondents: 100 the first time, and 152 the second time, 124 the third time.

1) P≠NP is at about 80%. When restricted to people who have thought about the problem a lot (my judgement) then it goes to 99%. The strongest P≠NP is by Lance who says

                                People who think P=NP are like people who believe Elvis is alive.

I disagree. I think Elvis is alive and is trying to prove P=NP.

2) When will it be solved? 66% thought it would be solved before 2100, a bit more than in prior years. But also more thought it would never be solved. Some commented that a computer might solve it.  I doubt that, but I do think this poll will be done by a computer in 10 years.

3) Because I used Survey monkey (1) each question got more answers, and (2) most  questions got a forced YES or NO  so less funny comments or room for creative answers. People could still leave comments, and some did.

4) Related to point (3): The last time I did the poll P=BPP was thought by everyone who answered the question. This year far more people answered it and quite a few thought P≠BPP. This may be because Survey monkey had a psychological affect of making people vote even if they didn't really know (people who have thought a lot about P vs NP  all thought P=BPP). Has  there been evidence that P≠BPP that I am unaware of? Or since there has not been that much progress on it maybe they are unequal. 10 years ago I would have thought we would have L=RL by now.

5) The last time I did the poll 10 people thought factoring IS in P and the NSA or the KGB knows that. This time around nobody thought that. Why? Those 10 people have vanished mysteriously.

6) Five people thought P vs NP will be resolved by Harambe. That is more than any person got.

7)  Is this poll worth doing? I would say yes (gee, I have to having done his poll three times) because it is good to have an objective record of subjective opinion.

8) I'll give some of my answers: P≠NP, Elvis is dead, and both will be proven in the year 2525. For more about the future see this.

Thursday, March 14, 2019

Captain Einstein

If the president of the United States uses "complexity" in a tweet, I can't leave it alone.

I got my MIT degree in Applied Mathematics so I don't count, but I know plenty of MIT computer scientists and the one undeniable truth is that I don't want any of them flying my plane.

I also agree with the Donald that a complex environment can often lead to confusion, especially in an emergency. HCI matters.

But that's where it stops. Better technology in the plane and on the ground, combined with better procedures have all but eliminated deadly major commercial airplane crashes in the US and quite rare in the world at large. I'll call that more than a "little gain". I remember the "old and simpler" days where we had deadly airline crashes every few months. No thanks.

I've had great discussions with some of the aerospace engineering professors at Georgia Tech. The amount of effort to get the "front-of-the-plane" software right via formal methods and rigorous testings has become harder to engineer than the plane itself. The "back-of-the-plane" software that controls the video screens and WiFi gets less attention. I can live with safety over movies.

When technology makes things much safer, whether it be planes or self-driving cars, the rare accidents become far more noticeable. while we should use these opportunities to learn and make things safer, the rare accidents help us realize just how much more safer technology can make us.

Sunday, March 10, 2019

Richard Karp: His influence and how to honor him

When I first saw the definition of NP-Complete I first thought if there are NP-complete problems I suspect they are contrived. When I saw the proof that  SAT is NP-complete I thought okay, so there is one natural problem  NP-complete by a trick of encoding, but I suspect there aren't any more.  I then read Karp's article that had 22 NP-complete problems. I thought okay, there are 22, but I suspect there are no more. No I didn't think that. But the point is that Cook and Karp together birthed modern complexity theory by introduction NP-completeness and showing that there are MANY natural problems that are NP-complete.

How many people has Richard Karp inspired? I don't know but I suspect it's a  cardinal between countable and the reals so it may depend on your model of set theory. Later in this post I will present Samir Khuller's story of how Richard Karp inspired him.

How to honor him?  The Simons inst. is currently welcoming contributions to the Richard M Karp Fund, which honors the scientific contributions of Founding Director Dick Karp. The fund will provide vital support for the mission and activities of the Simons institute. They have a deadline of Pi-Day. You can go here to contribute and/or here for a letter from Shafi Goldwasser, Prabhakar Raghavan, and Umesh Vazirani about the fund.

OKAY, Samir's story:

Mentoring and Influence via a Train Journey...

Almost to the day, 33 years ago I was running from my dorm room to catch an unreliable bus to the train station as I headed home for a mid-semester break.  On the way,I  stopped by the mailroom, and not knowing where to put the CACM that had just arrived,  stuffed it into the side of my bag and in the process, dropping my   notebook in the process. On the train, when I looked for my  notebook to go over  some material I realized it was missing! All I had was a CACM and a very long train ride. Skimming through the journal, I found Karp’s Turing Award article “Combinatorics, Complexity, and Randomness“. I  started reading this article, and was riveted! It was one of those life changing moments for me, when my immediate future became clear - I wanted to study Theoretical Computer Science and specifically the complexity of combinatorial problems. Without ever having met Dick Karp, he changed my life forever.

I met Dick long after he influenced me via his Turing Award Lecture and it was a real privilege to have had the opportunity to interview him via a fireside chat at Simons. See here.

I am delighted about the fund Bill mentions above as the money that goes to it will help inspire others as Karp inspired me.

Friday, March 08, 2019


Via Scott, John Horgan wrote a blog post following on his 1993 Scientific American article The Death of Proof. The article talked about computer-generated proofs, experimental mathematics and even mentioned some of our work on transparent proofs (basically time-efficient probabilistically checkable proofs). I got (sarcastically I think) accused of killing mathematics after that article but of course we had traditional proofs about probabilistically check proofs. Andrew Wiles got a sidebar titled "A Splendid Anachronism?" for merely solving the most famous open problem in all of mathematics. Somehow traditional mathematical proofs survived the article.

Meanwhile in CACM, Moshe Vardi writes Lost in Math? 
TCS is surely blessed with mathematical beauty. As a graduate student a long time ago, it was mathematical beauty that attracted me to TCS, and continued to lead my research for many years. I find computational complexity theory (or complexity theory, for short), with its theorems (for example, the time-hierarchy and space-hierarchy theorems) and its open questions (for example, P vs NP), to be hauntingly beautiful. Beauty, yes; but what about truth?
Here here on the beauty of complexity. So what about truth? I cover much of this in my P v NP survey. In short the P v NP captures the most critical aspects of what is efficiently computable but it is not the endpoint. Nevertheless P v NP captures both truth and beauty and that's why the problem has so captivated and guided me throughout my research career.

Monday, March 04, 2019

How are there 20 copies of my new book through other booksellers and why are they so highly priced

(This is about my book PROBLEMS WITH A POINT: exploring Math and computer science
by Gasarch and Kruskal, here. This post is NOT a plug.)

I often see weird pricing on amazon but don't have enough inside information to explain it. This time I have seen some weird pricing on amazon but DO have enough information to be truly baffled.

My book is on amazon. You can buy it

Softcover new: $38.00

Hardcover new: $68.00

Okay, that all makes sense.

OR you can buy it from some other source.

There are 10 copies of the softcover, they claim new,  ranging from $38.00 to $57.00.

There are 2 copies of the softcover, they claim used (how used could it be?), $49 and $53

There are 9 copies of the hardcover, they claim new, ranging from $68.00 to $91.00

There are 2 copies of the hardcover, they claim used, $84.00 and $88.00

This raises two questions

1) I have a copy, Clyde got a copy, and two copy's were send to reviewers. Neither Clyde nor I have sold our copy. So how did 20 or so copies get out there?

2) Why do they cost MORE than list price.

I've asked around and got some answers, but I INVITE you to give more possible answers. If your answer is not just speculation (e.g., `I used to be in the black market  book business and here's the real scoop') then that would be great; however, I will take specuation


1) Clyde and I haven't gotten our free copies yet. Hijacked?  Here's hoping the hijackers read it and enjoyed it before posting it. However, this theory is unlikely since I inquired with World Scientific (our publisher) and found out we'll be getting our free copies in 2 weeks. So this theory will either be confirmed or denied in 2 weeks. I would bet against OR those are some really bad hijackers.

2) Complete ripoff. You pay the money and get NOTHING. I think this was more likely in the early days of amazon (or e-bay or....) but now things are pretty well monitored. I have sold books on amazon and am very impressed with how foolproof it is. Still --- could be.

3) Someone hacked my computer. Really? Where did they get the orange covers? Why would they bother? This is not Harry Potter. Plus I asked our staff and NO this could not happen.

4) Some of the shipment dates are fairly far in the future, so they plan to get an order, then
order the book, and have it send to the buyer, at a profit. Seems like too much sugar for a satoshi, BUT could be profitable if its a bot and its automated to do this with lots of books.

5) My publisher also send the book to other sellers. That does not explain the higher prices.


1) They are counting on people assuming that other sellers are cheaper without checking. Would people do that? People still fall for the Nigerian billionaire scam, so maybe yes.

2) The seller themselves, which is possibly an army of bots, didn't bother checking but priced it
similar to other books. This is plausible since $38.00 is fairly cheap, so looking at similar books may get you a higher price.

Any speculation is welcome so long as it does not involve space aliens or astrology.