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.  

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.

Fifty Years of P vs. NP and the Possibility of the Impossible

I have a new article Fifty Years of P vs. NP and the Possibility of the Impossible, to mark the anniversary of the 1971 publication of Steve Cook's seminal paper, a month too late in the January 2022 Communications of the ACM. 

Initially Moshe Vardi asked me to update my 2009 CACM survey The Status of the P versus NP Problem. The P vs NP problem hasn't changed much but computing has gone through dramatic changes in the last dozen years. I try to view P vs NP in the lens of modern optimization and learning, where we are heading to a seemingly impossible Optiland (a play on Impagliazzo's Pessiland), where we can solve many of the toughest NP-complete problems in practice and yet cryptography remains unscathed.

CACM produced a slick companion video to the article.

Fifty Years of P Versus NP and the Possibility of the Impossible from CACM on Vimeo.

Did Lane Hemaspaandra invent the Fib numbers?

 (I abbreviate Fibonacci by Fib throughout. Lane Hemaspaandra helped me with this post.) 

We all learned that Fib invented or discovered the Fib Numbers:

f_0=1,

f_1=1, and

for all n\ge 2, f_n = f_{n-1} + f_{n-2}.

We may have learned that they come up in nature (NOT true, see here) or that they were important in mathematics (questionable--see this blog post here which says no, but some comments give good counterarguments). You also learned that Fibonacci was the mathematician who first studied them. Also not true!  This one surprised me. 

1) I came across this blog post: here that says they were invented by Hemachandra first. Wow--I then recalled that Lane Hemaspaandra's birth surname  was Lane Hemachandra (he married Edith Spaan and they are now both Hemaspaandra). So naturally I emailed him to ask how a 20th-century person could invent something earlier than 1170. He told me a picture of him in the basement ages while he stays young. 

2) It would be nice to say OH, let's call them Hemachandra numbers (would that be  easier than convincing the world to use tau instead of pi,? See The Tau Manifesto) and let students know that there were people other than Europeans who did math back then. But even that story is not as simple as it seems. Lane emailed me this article: here that tells the whole muddled story. (In what follows I leave out the accents.)

Virahanka seems to be the formulator of the Fib recurrence, though not quite the numbers. His motivation was Sanskrit Poetry.  He did this between 600 and 800 AD.

Gopala, in work prior to 1135, was aware of Virhanka's work. In particular he know about the inductive rule. But he also set the initial values and generated numbers, so he was the first to have the sequence we now call the Fib numbers. His motivation was Sanskrit Poetry. 

Hemachandra in 1150 also formulated them, independently.  His motivation was Sanskrit poetry.

(I will learn some Sanskrit poetry the next time I teach Discrete Math so I can give the students an application of the material!)

So does Virhanka win? Hardly:

Acarya Pingala's writings from the 5th or 6th century BC (YES- BC!) indicate that he knew about the Fib numbers in the context of (you guessed it!) Sanskrit poetry. 

3) I would support changing the name of the Fib Numbers to the Pingala numbers. This is both good and bad news for Lane:

a) Bad news in that he does not get a sequence of number that shares his pre-marriage name.

b) Good news in that if I settled on Hemachandra numbers then Lane and Edith would have to decide if 0 or 1 or 2 of them want to change their name to Hemachandra. I would guess not--too complicated. Plus one name change in a life is enough. 

4) The story (especially  the articles I pointed to) shows just how complicated history can get. Even a straightforward question like:

Who first formulated the Fib Numbers?

might not have a well-defined answer. Perhaps this is  the wrong question since if people formulate the concept independent of each other, they should all get some credit.  Even if the authors are 1000 years apart. 

Side note: Independent Discovery may be harder to assert now since, with the web,  Alice could have seen Bob's paper so it may be hard to call Alice's discovery independent. As I have mentioned before on this blog, my students have a hard time with the notion of Cook and Levin coming up with NP-completeness independently  since  surely one would have posted it and the other would have seen it. An era before posting was possible! Unimaginable to them. Sometimes even to me. 

Defending the Status Quo

When the Wall Street Journal's editorial board and the New York Post endorse your efforts, that should ring warning bells.

Several members of the theory and mathematics community and have written and endorsed an Open Letter on K-12 Mathematics that attacks the proposed revisions to the California Mathematics Framework. I have mixed feelings about these efforts. 

Certainly the CMF has its issues, and the FAQs protest too much. But the letter goes too far in the other direction, arguing mainly for the status quo that worked well for those who signed the letter, very few of which have significant experience in K-12 education. The open letter allows for only incremental change unlikely to lead to any significant improvements.

Before you sign the letter, take a look at the CMF introduction

To develop learning that can lead to mathematical power for all California students, the framework has much to correct; the subject and community of mathematics has a history of exclusion and filtering, rather than inclusion and welcoming. There persists a mentality that some people are “bad in math” (or otherwise do not belong), and this mentality pervades many sources and at many levels. 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. 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. These signifiers exacerbate and are exacerbated by acceleration programs that stratify mathematics pathways for students as early as sixth grade.

Students internalize these messages to such a degree that undoing a self-identity that is “bad at math” to one that “loves math” is rare. Before students have opportunities to excel in mathematics, many often self-select out of mathematics because they see no relevance for their learning, and no longer recognize the inherent value or purpose in learning mathematics.

You may or may not agree with the CMF approach, but it's hard to deny the real challenges they are trying to address and students they are trying to help. If you don't agree with the CMF, work with them to come up with a good alternative that helps create a more inclusive mathematical citizenry. An outright rejection of the approach won't fix problems and probably won't be taken seriously, except from the conservative press.

Update (1/12/22): Boaz Barak and Jelani Nelson respond to this post.