Saturday, March 26, 2022

I don't care about Ketanji Brown Jackson's LSAT scores and she does not care about my GRE scores

Tucker Carlson has asked to see Ketanji Brown Jacksons's LSATs. 

When I applied to College they (not sure who they are) wanted to see my SAT scores. Putting aside the issue of whether the test means anything, they viewed the SATs (and my HS grades and letters from teachers) as a sign of my 

                                                       potential. 

When I applied to Grad school they (a different they) wanted to see my GRE scores. Putting aside the issue of whether the test means anything, they viewed the GREs (and my college grades and letters from professors) as a sign of my

                                                       potential. 

When I applied for jobs as a professor they (another they) wanted to see my resume (papers I wrote) and letters from my advisor and others (I think). They did not look at my grades (just as well- I got a B in both compiler design and operating systems. Darling is amazed I even took operating systems). This was probably the oddest of the application processes since they were looking for both

                                                    potential and achievement.

That is, the evidence that I could do research was that I had done some research. This was before the current  era where grad students had to have x papers in prestige conferences to get a job at a top y school. The letter from my advisor may well have spoken of my potential. 

When I went up for tenure ALL they cared about was PAPERS (and letters saying they were good papers), and some teaching and service. It was based just  on 

                                                          achievement.

A wise man named Lance Fortnow once told me:

The worst thing a letter of recommendation for a tenure case can say is `this person has great potential'


It would have been rather odd for Tucker Carlson to ask to see my SAT scores or GRE scores or by HS, College, or Grad School grades as a criteria for Tenure. Those tests and those grades are there to measure potential to DO something, whereas if you are going up for tenure or a Supreme Court seat, you've already DONE stuff. 

After I got into grad school one of my first thoughts was

Nobody will ever want to see my GRE's again. ( I was right.) 

After KBJ got into Law School she might have thought

Nobody will ever want to see my LSAT scores again. (She was wrong.)




Sunday, March 20, 2022

Do you want to be the SIGACT NEWS book review editor?

I ran the SIGACT Book Review Column from 1997-2015 (18 years). You can find all of my columns, plus reviews I did for Fred, here.

When I handed it off to Fred Green I gave him this sage advice:

                   Nobody should do this kind of job for more than about 5 years.

He ran the SIGACT Book Review Column since the end of 2015. You can find some of his columns here.

Fred is taking my advice and looking for a successor.

SO, this blog is a call to ask

                 DO YOU WANT TO BE THE SIGACT NEWS BOOK REVIEW EDITOR?

If so then email

Fred: fgreen@clarku.edu


DO NOT BE SHY! I suspect he won't get many applicants, so if you want the job its probably yours.


PROS

1) You get to skim lots of books and read some of  them.

2) You get some free books.

3) You get plugged into the book community (this helped me when I wrote my two books).

4) You'll have two Veteran Book Review Editors happy to review for you.

5) You get to decide the direction the column goes in.

Both Fred and I did mostly CS theory books. However:

a) I did more combinatorics, educational, history, and Computers & Society books than usual.

b) Fred did more Number Theory and Physics than usual.

(Since I did the job 18 years and Fred for 6, its not clear what usual means.) 


CONS

1) You have to get out a book review column 4 times a year.

2) You have to find reviewers for books and then email them when the reviews are due.

(I think Fred is still waiting for me to review a Biography of Napier. Oh well. On the other hand, I was the one who liked having history books, which may explain why Fred never hassled me about it.) 


ADVICE

Prob should be done by someone who already has Tenure. While seeing and skimming thosebooks is GOOD for your research career, and good in the long-termsomeone pre-tenure really needs to get papers out in the short term. Also, when you get a book think about who might be good to review it--- don't take on to many yourself. 


PARTING GIFT OR WELCOME GIFT

In a recent column I had a review of a 5-book set from the LESS WRONG blog. I amcurrently working on a review of a 4-book set set from the LESS WRONG blog. This willeither be a parting gift for Fred or a Welcome gift to his successor.


Thursday, March 17, 2022

The War and Math

During the early parts of the cold war of the 20th century, we saw two almost independent developments of computational complexity, in the west and in the then USSR. There was little communication between the two groups, and countless theorems proven twice, most notably the seminal NP-complete papers of Cook and Levin. To understand more, I recommend the two articles about the early days of complexity by Juris Hartmanis and by Boris Trakhtenbrot.

Russia's invasion and relentless bombing in Ukraine have quickly separated the east and the west again. 

Our first concern needs to be with Ukraine and its citizens. We hope for a quick end to this aggression and Ukraine remaining a free and democratic country. Ukrainian cities have undergone massive damage, and even in the best possible outcome it will take years if not decades to fully rebuild the country. 

Terry Tao has been collecting resources for displaced mathematicians due to the crisis.

We've cut off ties with Russia institutions. In our world, major events to be held in Russia, including the International Congress of Mathematics and the Computer Science in Russia conference are being moved online. I was invited to workshops in St Petersburg in 2020 and 2021, both cancelled due to Covid, and was looking forward to one in 2022, which if it happens, will now happen without me. 

The music world has has cancelled some stars, most notably Valery Gergiev and Anna Netrebko, due to their close ties to Putin. It's rare that we do the same to mathematicians for political reasons though not unheard of. I suspect most of our colleagues in Russia oppose the war in Ukraine, or would if they had accurate information of what was going on. I have several Russian friends and colleagues including two I travelled to Moscow in 2019 to honor and would hate to be disconnected from them.

It's way too early to know how this will all play out. Will we see a quick Russian retreat? Not likely. Will we see a situation that sees a mass migration of Ukranian and Russian mathematicians and computer scientists to Europe and North America, like in the 1990's? Possibly. We will see a repeat of the cold war, disconnected internets and science on both sides happening in isolation? I hope not but we can't rule it out.

Tuesday, March 15, 2022

Problem X won't be solved in MY lifetime- but what about...

1) In 1989 on the episde The Royale of Star Trek: The Next Generation (which takes place in the far future)  Captain Picard is working on Fermat's last theorem which he says quite explicitly is still open.

When I saw the episode I asked Larry Washington, a Number Theorist at Univ of MD, when he thought FLT would be solved. He said

                                      It will be solved within the next 10 years.

And indeed- Wiles solved it in 1993-sort of. There was a flaw in the proof which he fixed in 1994 with the help of his former student Richard Taylor. Wiles published the correction to the flaw in 1995, so we will date it as having been solved in 1995. Larry Washington was correct.  And in an episode of Star Trek: Deep Space Nine in 1995 (episode name:Facets) Dax says that a previous host, Tobin Dax, had done the most creative work on FLT since Wiles. Maybe Tobin wrote this limerick:

A challenge for many long ages

Had baffled the savants and sages

Yet at last came the light

Seems that Fermat was right

To the margin add 200 pages.


I asked Larry W when he thought Riemann would be solved. He said  

                    In your lifetime but not in mine.

He is about 10 years older than I am and I think we are both in good health. This seems like a rather precise prediction so I am skeptical. But he did get FLT right...

2) In class I sometimes say things like 

I do not think Quantum Computers will factor faster than classical in my lifetime. 

I do not think P vs NP will be solved in my lifetime.

I can imagine P=BPP will be proven in my lifetime. (I said that 10 years ago. I am less imaginative now.) 

I hope the muffin problem is solved in my lifetime (it was, see here).

I didn't quite think about the difference in my age and the students until recently when I was working with Ilya Hajiaghayi (Mohammd H's 9 year old son) on cryptography and he said 

In your recorded lecture you said you don't think quantum computers will be a threat to cryptography  in your lifetime. What about in my lifetime?

Indeed- his lifetime and mine are rather far apart. 

I am reminded that one of the answers to my P vs NP poll made the point that while we have some sense of what will happen in the next 10 years, maybe even 20, math and life can change so much that conjectures beyond that are guesswork. Any  prediction for x years from now you should have confidence < 1/ln(x) of it being true.





Sunday, March 06, 2022

Random thoughts on the Russian Invasion of Ukraine

 1) My first thought was: Doesn't Putin know that his army (and his society) is corrupt and people are promoted on loyalty rather than talent, hence the invasion is not going to work? But then note

a) He invaded Georgia (the country not the state)

b) He annexed Crimea

c) NATO agreeing on sanctions? They can't even agree on what to have for lunch.  

d) The above question ASSUMES that he will lose. This is not clear yet.

2) The US and other countries are imposing sanctions. Visa, MC, and Netflix have withdrawn from Russia. Will these cause Putin to stop, or will they just impose hardships on the citizens without having an affect? I ask non-rhetorically. Foreign Policy is hard, though I suspect Biden has hired experts and is listening to them. Doesn't mean they are right. 

3) This seems like a case where its obvious that Putin is in the wrong so I was surprised to see some Pro-Putin arguments. To be fair, some were more that we should not get involved, which is not quite Pro Putin. Here are some and my thoughts on them.

a) Putin never called me a racist and never made my kids learn Critical Race Theory. This is meant as a GOTCHA comment. To take it seriously one would have to (1) examine what American's are learning in grade school, (2) examine what Russians are learning in grade school, (3) see which country is giving their students a more honest view of things (particularly history), and (4) decide that whichever school is teaching more honest material deserves are support. 

b) Putin is a strong leader and I admire strong leaders. Really? If  Biden was a strong leader who could push through the Build-Back-Better plan, would you admire that? You can't just admire strong leaders in the abstract, you have to see where they lead. (Same with admiring people who have principles.)

c) Putin stands for good Christian values. OH- so Putin likes to help the poor and does not approve of divorce or pre-marital sex. Oh, that NOT what you mean? Oh, you just mean that he does not like gay people or abortion. OH, thats not correct- Russia has the second most number of abortions of any country (see here) So the only issue where Russia shares your values is in not liking gay people. Is that enough  commonality is enough to justify invading a country? This does raise the serious question: who do you support in a war? The country that shrares your values? The country that didn't start it (sometimes hard to tell, though not in this case)? The country you have a treaty with? These are good and serious questions. 

d) How come the world does not like Putin's war based on lies and had no problem with W's war on Iraq that was based on lies? This is actually a good question. Being an academic by first impulse is to write a paper on it. There are differences between the invasion of Ukraine and Gulf War II, but still, lets assume that they really are somewhat equivalent. The person asking the question was probably AGAINST Gulf War II. Hence they should be against the invasion of Ukraine as well. So this is a good question about the America and NATO's Double standard and hypocrisy but is not a reason to be pro-Putin. (I was emailed that there are many conflicts that American and NATO do not care about that are as bad as Putin's invasion.) 

e) Russia had real concerns about security. The last time Russia was invaded was WW II (if I am wrong then please correct me in the comments). Even so, I've heard analogies made to America freaking out when Cuba had Nuclear missiles. There were no nukes in Ukraine. Ukraine was not going to join NATO anytime soon. I wonder if this was a pretense on Putin's part and not a real reason. 

f) See here. I give an excerpt (I am not making this up). 

But as its Covid mission has become less clear, the group’s channels have turned to Russia’s invasion of Ukraine, where conspiracy-minded thinking has flourished. While some group members have admonished Russian President Vladimir Putin for the invasion, QAnon and anti-vaccine contingents within the groups have seized on a false conspiracy theory that the war is a cover for a military operation backed by former President Donald Trump in Ukraine.

The conspiracy theory, which is baseless and has roots in QAnon mythology, alleges that Trump and Putin are secretly working together to stop bioweapons from being made by Dr. Anthony Fauci in Ukraine and that shelling in Ukraine has targeted the secret laboratories. Fauci, director of the National Institute of Allergy and Infectious Diseases, has emerged in the past year as a main target for far-right conspiracy theories.

3) I was somewhat surprised when Hungary came out against Putin. But Putin's arrangments with his allies are transactional- there is no real love there. I was much more surprised when Switzerland came out against Putin. Switzerland has been neutral since 1515 (I think I read that some place). 



Wednesday, March 02, 2022

REU programs in general, and two at Univ of MD this summer.

REU stands for Research Experience for Undergraduates. 

REU programs are funded by the NSF. The NSF website of REU programs is here. 

Univ if MD at College Park dept of Comp Sci is running two REU programs this summer:

I (William Gasarch) am running  REU-CAAR (Combinatorics and AI Applied to Real problems) whose theme is applying theory to practice. The website for it is here.

 Jacquelyn Michaelis and Mihai Pop are running REU-BRIDGe (Bioinformatics Research In Data science for Genomics) which, as you can probably tell from the name, is in bio-comp. The website for it is here.

Most REU programs have the following: 

1) There is an admissions period where many people apply (I had around 200 applicants last year) of which only about 10 get in. Some have money for a few extra students. This year both REU-CAAR and REU-BRIDGe have applications due March 22; however, in the past I have admitted students before then, so students who apply March 21 may be at a severe disadvantage. 

2) Students apply from across the United states and these programs are competitive, so good to apply to several that you would definitely goto. Students ask me how many- I'll say 10 though temper that with only applying to those you REALLY would goto, and if there are MORE THAN 10 that look awesome, you could apply to more. 

3) Students stay in the dorms (the last two years some programs cancelled, and some were virtual- mine was virtual) and get stipend of $6000, and a meal card. The program is 10 weeks.

4) Students work on projects in teams of 2-5. Some programs have the students pick what projects they would be happy to work on when they apply (mine does that) while others assign projects once students arrive (REU-BRIDGe will do that). The later makes sense if the program is very focused so the projects do not differ that much. 

5) These programs are excellent for giving ugrads a chance to do research (NSF wants at least half of the students to come from non-research schools) and a sense of what grad school is like. So I recommend students thinking of grad school, or just want to do research, to apply to these programs. 

6) Some students get papers out of the research. In these cases the research usually continues after the program is over. 

7) It is healthy for a student to go to an REU program that is at a DIFFERENT school then where they are an ugrad for broadening. There may be mitigating circumstances where this is not possible. 


Saturday, February 26, 2022

I did an Instagram Live with Mohammad Hajiaghayi

 Today I did an Instagram Live with Mohammad H. He was the host, asking me questions. We discussed 

Our lives

Blogging (which I do but he does not)

Parenting (which he does but I do not)

P vs NP (which we both care about) 

Zero Knowledge and Zcash

and

How to inspire young minds (since I mentor many students, including Mohammad's 9 year old son)

The conversation is on you-tube here

Enjoy!


Thursday, February 24, 2022

I will be on instagram/If you have two reals in a box- Answer (Guest Post by David Marcus)

I will be on instragram:

We,  Prof. Mohammad Hajiaghayi and Prof. William Gasarch plan to have an Instagram Live at @mhajiaghayi this SAT FEB 26, 1:30PM EDT (in English).

 We talk about our lives as well as blogging, research, and how to inspire young minds. Please join if you can.

#PvsNP #blogging #youngminds #instagram


-------------------------------------

This is the answer to the problem posted in the last post which was a guest post by David Marcus. This post is also a guest post by him. 

We restate the problem:


-------------------------------------------------

PICK THE LARGEST NUMBER:

There are two distinct reals in a box (how do they fit! aren't reals infinite!). They are called the first and second number. 

You want to pick the larger one. You can pick one of the numbers at random and look at it

before deciding which one you want. 

Is there a strategy that will win with probability > 1/2.

CLARIFICATIONS:

1) We do not want a strategy that does well on average or in the long run. Even if the games is played just once, we want the probability of winning to be > 1/2.

2) It must have prob of winning > 1/2 for EVERY pair of reals.

3) Here is an example of a strategy that does NOT work: Pick the first number with prob 1/2. If its positive then keep it, else dump it. If the numbers are{1,2} this only works half the time.

-------------------------------------------------

There is a strategy. In fact, we give two.


STRATEGY ONE

Before looking at any number, pick a number x on your own from the reals according to a distribution with full support (every open interval has prob greater than 0). Then pick a number from the box (prob 1/2-1/2), which we call y. If x<y then keep y. If y\le x then take the other number.

If x is between the two numbers, then the strategy works. If not then the strategy does not hurt, so the prob in that case is 1/2. Hence you do better than 1/2. 

STRATEGY TWO

Let f: R--> (0,1) be strictly increasing. Pick a number from the box, call it y. Keep it with prob f(y).




Monday, February 21, 2022

I will be on Instagram/If you have two reals in a box.... (Guest Post by David Marcus)

I will be on instragram:

We,  Prof. Mohammad Hajiaghayi and Prof. William Gasarch plan to have an Instagram Live at @mhajiaghayi this SAT FEB 26, 1:30PM EDT (in English).

 We talk about our lives as well as blogging, research, and how to inspire young minds. Please join if you can.

#PvsNP #blogging #youngminds #instagram

-------------------------------------

 (David Marcus emailed me this for a guest post, inspired by my posts on a similar problem where I gave the question here and the answer here.)

This is a well known problem, but I have learned over time that not everyone knows things that are well known.

PICK THE LARGEST NUMBER:

There are two distinct reals in a box (how do they fit! aren't reals infinite!). They are called the first and second number. 

You want to pick the larger one. You can pick one of the numbers at random and look at it

before deciding which one you want. 

Is there a strategy that will win with probability > 1/2.

CLARIFICATIONS:

1) We do not want a strategy that does well on average or in the long run. Even if the games is played just once, we want the probability of winning to be > 1/2.

2) It must have prob of winning > 1/2 for EVERY pair of reals.

3) Here is an example of a strategy that does NOT work: Pick the first number with prob 1/2. If its positive then keep it, else dump it. If the numbers are{1,2} this only works half the time.

(Warning: I will NOT block comments that give away the answer, so if you want to work on it without knowing the answer, do not look at comments.) 



Monday, February 14, 2022

Belated happy 80th, Allan Borodin!

Guest Post by Aravind Srinivasan 

Allan Borodin turned 80 in 2021. This post is to belatedly wish him a very happy 80th, and to give a short personal perspective. 

Three things come to mind when I think of Allan:

  1. His range of research topics: I was first exposed to his work (Borodin's Gap Theorem) in a complexity-theory class by Hartmanis in Spring 1990, and have since enjoyed reading---at varying levels of depth---his works on algebraic complexity, space complexity and tradeoffs, circuit complexity, lower bounds in general, routing, adversarial queuing, online algorithms, priority algorithms, and E-commerce (I am surely leaving out some areas). This is an amazingly broad sweep!
  2. His enthusiasm in learning about and developing new models, as our field has evolved greatly over time.
  3. The enthusiastic embrace he has given to researchers spanning generations. Indeed, I am one of many who have been inspired by various facets of his research and personality.

Photos from Allan’s 60th can be seen at Amos Fiat’s page.

Thank you for everything Allan, and wishing you continued robust health and enjoyment of your academic work! 

Tuesday, February 08, 2022

A Book Break

I got the writing bug back while working on my recent CACM article and I'd like to try my hand at another book. Not sure the exact topic but something related to the changing nature of computing and its implications. 

I'll cut down my blogging for a while. I'll still post or tweet when I have something I want to say. Bill will continue to post regularly and keep this blog active.

Bill asked me if I have time to write this book as dean but he already knew the answer. Writing keeps me sane in a world that seems less and less so.

Sunday, February 06, 2022

PSPACE is contained in Zero Knowledge!! How come nobody seems to care?

(This post was inspired by Lance's post on Zero Knowledge, here, which was inspired by a video he has in the post which was inspired by... (I think this ordering is well founded.))

 ZK= Zero Knowledge.

When it was shown that NP \subseteq ZK this was a big deal. This was by Goldreich-Micali-Wigderson  (see here (FOCS-1986, JACM-1991). In the JACM paper they have the following passage:

Our result that all languages in NP have zero-knowledge proof systems, has been extended to IP, assuming the same assumptions. (The result was first proved by Impagliazzo and Yung, but since their paper [53] contains only a claim of the result, the interested reader is directed to [11] where a (different proof) appears.) In other words, whatever can be efficiently proven can be efficiently proven in a zero-knowledge manner. This may be viewed as the best result possible, since only languages having interactive proof systems can have zero-knowledge interactive proof systems.

11. BEN-OR, M., GOLDREICH, O., GOLDWASSER, S., HASTAD, J., KILLIAN, J., MICALI, S,,  AND ROGAWAY, P. Everything provable is provable in zero-knowledge. In Proceedings of Advances in Cryptology— Crypto88. Lecture Notes in Computer Science, vol. 403. Springer-Verlag, New York, 1990, pp. 37-56.

53.IMPAGLIAZZO. R., AND YUNG, M. Direct minimum-knowledge computations. In C. Pomerance, ed., Proceedings of Advances in Cryptology— Crypto87. Lecture Notes in Computer Science, vol. 293. Springer-Verlag, New York, 1987, pp. 40-51.
Later the papers of Lund-Fortnow-Karloff-Nisan and Shamir showed IP=PSPACE. Hence

PSPACE \subseteq ZK

When I realized this I thought OH, that's interesting! I then looked around the web and could not find any mention of it. I asked Lance and some people in crypto and yeah, they all knew it was true, but nobody seemed to care.

Why the apathy? Speculation:

1) ZK is a notion people actually want to use in real crypto (and there has been some progress on that lately). The prover for ZK in PSPACE has to be way to powerful to be practical. I don't really like this explanation since we are talking about theorists. Even in crypto, which has more of a connection to the real works then, say, Ramsey Theory, there are still plenty of non-useful results. 

2) IP=PSPACE was the big news and  had interesting proof with nice ideas. Nothing crypto-ish about it. So the corollary that PSPACE \subseteq ZK is an afterthought. 

3) SAT in ZK was big news. IP in ZK is nice, but uses mostly the same ideas.

4) I am WRONG- it is a celebrated result and I somehow missed the celebration.

5) The proof that ZK is in PSPACE USES two interesting results, but adds NOTHING to the mix. In short, the proof is to easy.

Any other ideas?

Wednesday, February 02, 2022

The Beginnings of Zero-Knowledge

Wired runs this video series where topic expert explain concepts to five levels of difficulty, typically a child, teen, undergrad, grad student and expert. UCLA professor Amit Sahai took this on for zero-knowledge. 

I'd recommend the whole thing but I'd like to focus on the last segment with USC Professor Shanghua Teng (starts at 17:05). Amit nicely summed up the importance of the paper.

What was such a beautiful insight is that the idea of zero-knowledge being something that you can already predict. If you can already predict the answer, then you must not be gaining any knowledge by that interaction. This insight of being able to predict the future accurately, and that being an evidence of a lack of new knowledge.

Like Shanghua I was also assigned the seminal zero-knowledge paper by Goldwasser-Micali-Rackoff from my advisor. In many ways the original STOC paper was rough. The definitions were buggy, the examples uninspiring. Supposedly the paper didn't even get accepted into a conference in its first try. And yet as you read the paper you realize the potential, the beauty of not one but two new models that would go on to change both cryptography and complexity forever.

In the fall of 1985 when I started graduate school I took a cryptography class from Manuel Blum. Much of that class was spent on protocols that would convince you that, for example, a number was the product of three primes. By the spring of 1986, Goldreich, Micali and Wigderson distributed their paper showing, among other things, all NP problems has zero-knowledge proofs, making many of the protocols discussed in Blum's course a few months earlier trivial corollaries.

But it wasn't just zero-knowledge. Goldwasser, Micali and Rackoff (and independently Babai and Moran) developed the notion of interactive proof, a proof system with statistical confidence, a model that would lead to probabilistically checkable proofs and helping us understand the limits of approximation.

I owe most of my early research to the models developed in the GMR paper and glad that Amit has found a way to share these ideas so well.

Sunday, January 30, 2022

Regan Lipton celebrates my 1000th blog post and random thoughts this inspires

Ken Regan emailed me recently asking if our software could tell how many blogs I had done (not how many Lance+Bill had done). We didn't know how to do that but he managed it anyway. Apparently he was more interested in this question than either Lance or I was. 

But the answer was interesting: My1000th post of Complexityblog was about Betty White dying at just the wrong time to be in those those we say goodbye to articles that appear CLOSE to the end of the year. (I don't know why, but I think the fact that my 1000th post was on Betty White is just awesome!) The post is here. He was asking this because he thought (correctly) that I was around 1000 and wanted to do a tribute blog to me (actually it was done by Lipton and Regan- more on that later). And indeed they did do the post, its here.

RANDOM THOUGHT ONE

While preparing it Ken asked me about my papers.  This brings up the more general question: When looking at your old work what do you think? Common reactions are

1) Gee, I was smarter then. That was very clever. OH, now I remember, my co-author did it. 

2) Gee, I was dumber then. I could do that argument so much better now. 

3) Why did I care about Muffins so much to write a book about it? (Replace Muffins with whatever you worked on and book with the venue it appeared in.) 

Item 3 is probably the most common: As a graduate student one works on things without really have a vision of the field (though the advisor can mitigate this) so what you work on may seem odd later on. And ones tastes can change as well. 

RANDOM THOUGHT TWO

Ken and Dick write actual posts together. I find that amazing! By contrast, the extent of Lance and my interactions about the blog are: 

a) Someone died. Which of us should do the blog obit? or get a guest blogger.?(Whenever Lance phones me on the telephone I answer who died and usually someone did.) 

b) Which of us does the April Fools Day post this year (we usually alternate, or do we)?

c) I plan on doing 2 posts close together- a question and an answer, so when do you NOT plan on blogging so I can do that.

d) Someone proved X. Which of us should blog? Or should we get a guest blogger?

e) Establish a general rule for the year like Bill will post Sunday's, Lance Thursdays.

f) I ask Lance for technical help on the blog. How do you get rid of the white background when I cut and paste?

g) Sometimes one of us wants commentary on a blog we are working no- but that is rare. Though I asked Lance for this post and he added a few things to this list.

h) Sometimes I look at one of his posts before it goes out and offer commentary, or vice versa. Also rare.

i) Lance writes the end of year posts, but always with my input. We jointly choose the theorem of the year.

j) The very rare joint posts.

k) If we happen to be in the same place at the same time, like Dagsthul, we'll do a typecast capturing our conversations. In the past we've also had podcasts and vidcasts together.



Wednesday, January 26, 2022

A Failure to Communicate

The screenwriter Aaron Sorkin wrote an article on prioritizing "Truth over Accuracy". He tells stories from his movies The Social Network and Being the Ricardos, of where he moves away from accuracy to get to the truth of a situation.

My friend and teacher, the late William Goldman, said of his Academy Award-winning screenplay for All the President's Men, "If I'm telling the true story of the fall of the President of the United States, the last thing I'm going to do is make anything up." I understand what he meant in context, but the fact is, as soon as he wrote "FADE IN," he'd committed to making things up. People don't speak in dialogue, and their lives don't play out in a series of scenes that form a narrative. Dramatists do that. They prioritize truth over accuracy. Paintings over photographs.

As scientists we focus on accuracy, as we should in our scientific publications. However being fully accurate can distract from the "truth", the underlying message you want to say, particularly in the title, abstract and introduction of our papers 

Even more so when we promote our research to the public. A science writer once lamented to me that scientists would focus too much on the full accuracy of the science and the names behind it, even though neither serves the reader well.

Reminds me of the recent Netflix movie Don't Look Up satirizes scientists trying to communicate an end-of-the-world event to an untrusting society. I wish it was a better movie but still worth watching just to see Leo DiCaprio and Jennifer Lawrence play scientists frustrated with their ability to communicate a true existential crisis to the government and the general public. 

So how should we as scientists try to frame our messaging to get people onboard, particularly when we say things they don't want to hear? Most importantly, how do scientists regain trust in a world where trust is in short supply. Perhaps we should paint more and photograph less.

Sunday, January 23, 2022

Personal Reflections on Dick Lipton in honor of his 1000th blog/75th bday.

 Is it an irony that Lipton's 1000th post and 75th bday are close together? No. Its a coincidence. People use irony/paradox/coincidence interchangeably. Hearing people make that mistake makes me literally want to strangle them. 

The community celebrated this milestone by having  talks on zoom in Lipton's honor. The  blog post by Ken Regan that announced the event and has a list of speakers is here. The talks were recorded so they should be available soon. YEAH KEN for organizing the event! We may one day be celebrating his 2000th blog post/Xth bday. 

I will celebrate this milestone by writing on how Lipton and his work have inspired and enlightened me. 


1) My talk at the Lipton zoom-day-of-talks was on the Chandra-Furst-Lipton (1983)  paper (see here) that sparked my interest in Ramsey Theory, lead to a paper I wrote that improved their upper and lower bounds, and lead to an educational open problem that I posted on this blog, that was answered. There is still more to do.  An expanded version of the slide talk I gave on the zoom-day is here. (Their paper also got me interested in Communication complexity.) 

2) I read the De Millo-Lipton-Perlis (1979) paper (see here) my first year in graduate school and found it very enlightening. NOT about program verification, which I did not know much about, but about how mathematics really works.  As an ugrad I was very much into THEOREM-PROOF-THEOREM-PROOF as the basis for truth. This is wrongheaded for two reasons (1) I did not see the value of intuition, and (2) I did not realize that the PROOF is not the END of the story, but the BEGINNING of a process of checking it- many people over time have to check a result. DLP woke me up to point (2) and (to a lesser extend) point (1). A scary thought: most results in math, once published, are never looked at again. So their could be errors in the math literature. However, the important results DO get looked at quite carefully. Even so, I worry that an important result will depend on one that has not been looked at much...Anyway, a link to a  blog post about a symposium about DLP is here.

3) The Karp-Lipton theorem is:  if SAT has poly sized circuits than PH collapses (see here), It connects uniform and non-uniform complexity.  This impressed me but also made me thing about IF-THEN statements. In this case something we don't think is true implies something else we don't think is true. So--- do we know something? Yes! The result has been used to get results like 

                                                   If GI is NPC then PH collapses.

This is evidence that GI is not NPC. 

4) Lipton originally blogged by himself and a blog book came out of that. I reviewed it in this column. Later it became the  Lipton-Regan blog, which also gave rise to a book, which I reviewed   here.  Both of these books inspired my blog book. This is a shout-out to BOTH Lipton AND Regan.

5) Lipton either thinks P=NP or pretends to since he wants people to NOT all think the same thing. Perhaps someone will prove P NE NP while trying to prove P=NP. Like in The Hitchhiker's Guide to the Galaxy where they say that to fly, you throw yourself on the ground and miss. I took Lipton's advice in another context: While trying to prove that there IS a protocol for 11 muffins, 5 students where everyone gets 11/5 and the smallest piece is 11/25, I wrote down what such a protocol  would have to satisfy (I was sincerely trying to find such a protocol) and ended up proving that you could not do better than 13/30 (for which I already had a protocol). Reminds me of a quote attributed to Erdos: when trying to prove X, spend half your time trying to prove X and half trying to prove NOT(X).

6) Lipton had a blog post (probably also a paper someplace) about using Ramsey Theory as the basis for a proof system (see here).  That inspired me to propose a potential randomized n^{log n) algorithm for the CLIQUE-GAP problem (see here). The comments showed why the idea could not work-- no surprise as my idea would have lead to NP contained in RTIME(n^{log n}). Still, it was fun to think about and I learned things in the effort. 





Wednesday, January 12, 2022

On the California Math Framework

Guest post by Boaz Barak and Jelani Nelson

In a recent post, Lance Fortnow critiqued our open letter on the proposed revisions for the California Mathematics Framework (CMF). We disagree with Lance’s critique, and he has kindly allowed us to post our rebuttal here (thank you Lance!).

First, let us point out the aspects where we agree with both Lance and the authors of the CMF. Inequality in mathematical education, and in particular the obstacles faced by low-income students and students of color, is a huge problem in the US at large and California in particular. As a Black mathematician, this portion of the CMF’s introduction particularly resonated with me (Jelani):

Girls and Black and Brown children, notably, represent groups that more often receive messages that they are not capable of high-level mathematics, compared to their White and male counterparts (Shah & Leonardo, 2017). As early as preschool and kindergarten, research and policy documents use deficit-oriented labels to describe Black and Latinx and low-income children’s mathematical learning and position them as already behind their white and middle-class peers (NCSM & TODOS, 2016).

We agree with the observation that bias in the public education system can have a negative impact on students from underrepresented groups. Where we strongly oppose the CMF though is regarding their conclusions on how to address this concern. 

The CMF may state that they are motivated by increasing equity in mathematics. However, if we read past the introduction to the actual details of the CMF revisions, then we see they suffer from fundamental flaws, which we believe if implemented, would exacerbate educational gaps, and in particular make it harder for low-income students and students of color to reach and be successful in college STEM.

You can read our detailed critique of the CMF, but the revisions we take issue with are:

  1. Recommendation to drop the option of Algebra I in the 8th grade
  2. Recommendation to offer (and in fact push and elevate above others) a “data science” pathway for high school education as an alternative to the traditional Algebra and Geometry curriculum. While data science can be a deep and important field, teaching it for students without a math background will be necessarily shallow. Indeed, the proposed data science courses focus on tools such as using spreadsheets etc., and do not provide mathematical foundations.

1 and 2 make it all but impossible for students that follow the recommended path to reach calculus (perhaps even pre-calculus)  in the 12th grade.  This means that such students will be at a disadvantage if they want to pursue STEM majors in college. And who will be these students? Since the CMF is only recommended, wealthier school districts are free to reject it, and some already signalled that they will do so. Within districts that do adopt the recommendations, students with means are likely to take private Algebra I courses outside the curriculum (as already happened in San Francisco), and reject the calculus-free “data science” pathway. Hence this pathway will amount to a lower-tier track by another name, and worse than now, students will be tracked based on whether their family has the financial means to supplement the child’s public education with private coursework.

Notably, though the CMF aims to elevate data science, we’ve had several data science faculty at the university level express disapproval of the proposal by signing our opposition letter, including a founding faculty member of the Data Science Institute at UCSD, and several others who are directors of various undergraduate programs at their respective universities, including four who direct their universities' undergraduate data science programs (at Indiana University, Loyola University in Chicago, MIT, and the University of Wisconsin)! 

One could say that while the framework may hurt low-income or students of color who want to pursue STEM in college, it might help other students who are not interested in STEM. However, interest in STEM majors is rapidly rising, and with good reasons: employment in math occupations is projected to grow much faster than other occupations. With the increasing centrality of technology and STEM to our society, we urgently need reforms that will diversify these professions rather than the other way around.

As a final note, Lance claimed that by rejecting the CMF, we are “defending the status quo”. This is not true. The CMF revisions are far from the “only game in town” for improving the status quo in mathematics education. In fact, unlike these largely untested proposals, there is a history of approaches that do work for teaching mathematics for under-served populations. We do not need to change the math itself, just invest in more support (including extracurricular support) for students from under-resourced communities. For example, Bob Moses’ Algebra Project has time and again taken the least successful students according to standardized exams, and turned them into a cohort that outperformed state averages in math. One of our letter’s contact people is Adrian Mims, an educator with 27 years of experience, whose dissertation was on  "Improving African American Achievement in Geometry Honors" and who went on to found The Calculus Project, a non-profit organization creating a pathway for low-income students and students of color to succeed in advanced mathematics. 

To close, a critique of the proposed CMF revision is not a defense of the status quo. Even if change is needed, not all change is good change, and our letter does make some recommendations on the front, one of which is a matter of process: if a goal is to best prepare Californian youth for majors in data science and STEM more broadly, and ultimately careers in these spaces, then involve college-level STEM educators and STEM professionals in the Curriculum Framework and Evaluation Criteria Committee.

Sunday, January 09, 2022

Math problems involving Food

 A few people emailed me an Math article on arxiv about cutting a pizza, and since I wrote the book (literally) on cutting muffins, they thought it might interest me. It did, though perhaps not in the way they intended. I got curious about math problems that involve food. Here are some

The Muffin Problem. See my book (here), or my website (here)

The Candy Sharing Game. See this paper  (here).

Sharing a pizza. See this paper (here)

Cake Cutting. See  this book (here) or google  Fair Division  on amazon

Chicken McNugget Problem. See this paper (here)

The Ham Sandwich  Theorem. See this paper (here)

Spaghetti Breaking Theorem. See this paper (here)

Perfect Head on a Beer. See this paper (here)

A smorgasbord of math-food connections, see this pinterest posting (here)

And of course the question that has plagued mankind since the time of Stonehenge: 

                     Why do Hot Dogs come in packs of 10 and Hot Dog buns in Packs of 8 (here)


All of these problems could have been stated without food (The Chicken McNugget Problem is also Frobenius's Problem) but they are easier to understand with food.

I am sure I missed some. If you now of any other food-based math problems, leave a comment.




Sunday, January 02, 2022

Did Betty White die in 2021?/Why do people have their `end-of-the-year' lists before the end of the year?

 I am looking at Parade Magazine's issue whose cover story is

                                          We say goodbye to the stars we lost in 2021.

The date on the magazine is Dec 19-26. Betty White is not in it. Neither is Bishop Tutu. Why not? Maybe they did not die in 2021. No, that's not it.  They died after the magazine appeared. They also won't be in the issue a year from now which has cover story 

                                          We say goodbye to the stars we lost in 2022.

Why do magazines and TV shows have their end-of-the-year stuff before the end of the year? Because they want to beat the competition? Because they all do it, so its a race-to-the-bottom? Tradition? 

This blog does the same--- we already posted our end-of-the-year post. Every year I worry that someone will prove P=NP or P NE NP between Dec 24 and Jan 1.  We don't have the Betty-White-Problem since the end-of-the-year post is based on when we blogged about it, not when it happened. So if  theorist X died on Dec 27 then we would do the blog obit in Jan, and would mention it in the end-of-the-year post for the next year. (This happened with Martin Kruskal who died on Dec 26, 2006.) 

Why do we have our end-of-the-year post before the end of the year? Tradition! That might not be a good reason.  

ADDED LATER: Ken Regan in the comments points out that Betty White DID die in 2022 if you use AWE: Anywhere on Earth!

This leads to the following question:

a) If a celebrity dies on Dec 31 but its Jan 1 in some time zones then do they get to be in the

WE SAY GOODBYE TO THE STARS

articles for the Jan 1 year? 

b) Is there a general rule on this? I doubt it and I doubt it comes up a lot. I noticed that celebrities dying between Dec 24 and Dec 31 don't make those lists about 20 years ago, and I have never seen a Dec 31 case before, though I am sure there have been some.

c) Note that this `bad to die in that zone' really only applies to minor celebrities. Betty White and Desmond Tutu did get proper attention when they died.  



Thursday, December 23, 2021

Complexity Year in Review 2021

The pandemic hampered many activities but research flourished with a number of great results in complexity. Result of the year goes to

Locally Testable Codes with constant rate, distance, and locality by Irit Dinur, Shai Evra, Ron Livne, Alexander Lubotzky and Shahar Mozes
and independently in
Asymptotically Good Quantum and Locally Testable Classical LDPC Codes by Pavel Panteleev and Gleb Kalachev

They achieved the seemingly impossible, a code that can be checked with constant queries, constant rate, constant distance and constant error. Here's Irit's presentation, a Quanta article and an overview by Oded Goldreich. Ryan O'Donnell presents the Panteleev-Kalachev paper, which also resolved a major open question in quantum coding theory.

Other great results include Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits by Nutan Limaye, Srikanth Srinivasan and SĂ©bastien Tavenas, The Complexity of Gradient Descent by John Fearnley, Paul W. Goldberg, Alexandros Hollender and Rahul Savani, Slicing the Hypercube is not easy by Gal Yehuda and Amir Yehudayoff, and The Acrobatics of BQP by Scott Aaronson, DeVon Ingram, and William Kretschmer. The latter paper answers a 16-year old open question of mine that suggests you cannot pull out quantumness like you can pull out randomness from a computation.

In computing overall, the story continues to be the growth in machine learning and the power of data. We're entering a phase where data-driven programming often replaces logic-based approaches to solving complex problems. This is also the year that the metaverse started to gain attention. Too early to know where that will take use, but the virtual space may become as disruptive as the Internet over the next decade, and its potential effect in research and education should not be ignored. In the next pandemic, we may wonder how we survived earlier pandemics without it.

The NSF might be going through some major changes and significant increases, or not, especially with the Build Back Better bill on hold. The Computing Research Policy Blog can help you through the morass. 

We remember Matthew Brennan, Benny Chor, Alan Hoffman, Arianna Rosenbluth, Walter Savitch, Alan Selman, Bob Strichartz and Stephen Wiesner. 

We thank our guest posters Paul Beame, Varsha Dani, Evangelos Georgiadis, Bogdan Grechuk, David Marcus and Hunter Monroe.

In May I posted on emerging from the pandemic. Then came Delta. Now comes Omicron pushing us back online next month. I hope Pi-day doesn't bring us the Pi-variant.

Wishing for a more normal 2022.