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.

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.

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. 

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.

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.

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.