Since we will soon be back in the classroom, how was Zoom? Anything you want to maintain?

UMCP will have all classes on campus this Fall. There is a Mask Mandate. All students and faculty have to get vaccinated unless they have a health or religious exception. 92% are vaccinated, which I interpret as people are NOT abusing the exceptions (though I still wish it was higher, and it may go higher). (ADED LATER- right after I posted this I got an email saying that UMCP is now up to 97%).  Those NOT vaccinated have to get tested - I think twice a week. 

Now that we are back in the live-classroom, here are some thoughts about teaching on zoom. 

I taught on zoom:

Spring 2020: The last half of both Ramsey Theory and Automata Theory(Reg, CFG,P,NP,Dec,Undec)

Fall 2021:  Cryptography 

Spring 2021: Honors Discrete Math and Automata theory

a) I taught in the usual time slot but I recorded the lecture so those who could not make it (more common during the pandemic) could still see it. Attendance was low, verbal interaction was low, but chat-interaction was very good. Looking into if we can do a chat in an in-person class. I was recording lectures before the pandemic and will keep doing so.

b) My exams were open-notes, open-book, open-web. That cuts down on ways they can cheat, though they can still phone-a-friend. Or ask their cat.  Unusual-but-correct answers can happen, as I discussed in this blog.

c) I gave my muffin talk a few times on zoom. In person it goes very well as my enthusiasm is contagious.  On Zoom that affect is dampened so the audience was more sedate.  I gave it as a special lecture to High School students and to my REU students. Note that it was NOT part of a class so the usual motivation to learn it to do the HW is gone. Hence its more important they be excited about it. 

d) In person I carefully make sure that I wear a funny T-shirt every day, and its a diff one, and usually a math one to (if possible) match the topic. On Zoom I did not bother, though I sometimes used wallpaper to match the topic. 

e) I had to make up slides for Aut theory and for some of Discrete Math. For Crypto I already had slides. I like the slides I made up and will use them in the future. But see next point. 

f) In Discrete Math I went  faster than usual- perhaps because its on slides, perhaps because there were less questions since it was on zoom, perhaps because Emily my  TA was so awesome that they had less questions. (She is very interested in education and did a guest post about the pandemic and education here.) As a result I actually learned and presented the proofs that (1) the e is irrational (my slides are here) and that Liouville numbers are transcendental (my slides are here). While I enjoyed learning those theorems and I think the students understood them on some level, I will slow down next time.

g) Ramsey Theory: It is impossible to teach the Poly VDW theorem on slides, so I had to omit that part of the course. 

h) Bottom Line: Did the students learn more? less? the same? My impression is that the students learned about the same, but really really didn't like it. And thats legit- that is NOT just students complaining. 

The Long Road

Guest blogger Varsha Dani tells us why it's never too late.

This week, I am starting as an Assistant Professor at RIT and I am super excited about it. What's the big deal, you are probably thinking. Don't lots of people get hired in tenure track positions every year? Sure. But the difference in my case is that I got my Ph.D. in 2008. 

Why didn't I look for a position right away? There were a number of reasons. I was burned out. I was going to have a baby. The job market was not particularly good that year. I would have had a two-body problem. And most importantly, I thought it was just going to be a short break. I thought that there was no rush...

What did I do in those intervening years? A lot of things. I spent a lot of time with my kids, including part home-schooling them for some time. I found some new interests, both in Math and CS and outside. I found new collaborators and did some research in new areas, just for fun. Sometimes I was funded for it through grants, but mostly I wasn't. I wrote a lot of Computer Science and some math materials for Brilliant.org. I organized math clubs at my kids' elementary and middle schools. I hiked. I wrote poetry. I never intended nearly 13 years to go by, but somehow they did.  At some point I remembered that I had meant to take a short break, not to give up on being an academic altogether. But by then it seemed too late. At the beginning of my meant-to-be-short hiatus, I used to jokingly refer to myself as a "scholar at large" but by the time a decade had gone by I had started to feel extremely isolated and being a scholar for its own sake was not something to joke about anymore.  Each year I rolled the job-search dice, but with each passing year it seemed more and more futile to do so, and more and more of an imposition to ask people to write recommendations for me. And then, out of the blue, last year, I found a whole community of independent researchers who, like me, were pursuing their scholarly interests despite not being employed to do so, and who felt unapologetically unembarrassed, even proud of it.  And, even more out of the blue, this year I got an offer. And now, this Fall, I am actually doing it. I am actually an academic! To be honest, I feel more than a little trepidation about it, mixed in with the excitement. 

So why am I telling you this? Partly to celebrate. Partly to publicly thank my spouse, who has been extremely supportive of all my decisions (and all my actions that were born of indecision) over many years. Partly to give a shout-out to the wonderful folks at the Ronin Institute who helped me remember that we do science (and computer science) because we love it, not because it pays the bills. Ironically, I believe I needed to be reminded of that before I could get a job! But mostly, I'm writing this to reach out to anyone out there who thinks that their decisions have led to a one-way street they no longer want to be on. It may be hard, and there are, of course, no guarantees, but you won't know whether you can turn around, unless you try. 

When Words Get Stretched Beyond Their Original meaning

STORY ONE:

 On a Jeopardy rerun with Alex Trebek the question (actually the answer, given the shows format) was (I paraphrase)

Who resigned his commision in the US Army Air Force in April 1941 after President Roosevelt publicly rebuked him for his views?

The answer (actually the question--Why does Jeopardy do this answer-question thing, drives me nuts!) was

Charles Lindbergh.

Alex Trebek then said  Charles Lindberg's views on WW II were not politically correct.

This really struck me since Politically correct means, to quote Wikipedia:

a term used to describe language, policies, or measures that are intended to avoid offense of disadvantage to members of particular groups in society. 

Wikipedia also adds that the term is generally used pejoratively with an implication that these policies are excessive or unwarranted. 

 But Alex Trebek is using the term to mean  incorrect or perhaps incorrect given what we know now or if you think history is written by the winners, then perhaps incorrect since Germany lost the war.  But my point is that I really don't think the term  politically incorrect  makes sense here.

STORY TWO

More recently I heard an anti-masker say

We should not let some woke school board take the right to not wear a mask away from parents and children.

Independent of if you are anti-mask-mandates or pro-mask-mandates, this seems like a strange use of the word  woke  which means, to paraphrase Wikipedia:

Having an awareness of racial prejudice, gender prejudice, sexual orientation prejudice, and the past and current discrimination they have and do cause. 

I've seen it both positively and negatively.

The anti-masker's using of the term seems odd in that mask wearing is not a woke issue. Perhaps he should have said 

We should not let some Nazi school board take the right to not wear a mask away from parents and children.

The term  Nazi while not actually correct, conveys that the school board is authoritarian. However, he really could not use the term that since he was was a neo-Nazi and proud of it. That raises a question: what pejorative  term can a Neo-Nazi use when they want to say someone is  Authoritarian? I ask non-rhetoically. 

But I am getting off topic here- my real point is that the word woke is being used to mean Authoritarian which is not even close to its original meaning. 

MY POINT

The above are examples of how a word in English may change its definition over time, which is not really news, but I found the examples interesting since I saw the origin of these words.

BILL, THIS IS A COMPLEXITY BLOG! SO TALK ABOUT COMPLEXITY. OR MATH!

In math do words change their meaning over time? Yes. Here are a few

Function: at one time `function' implicitly means a function that occurs in nature. So only continous and perhaps diff functions qualified. 

Sets: probably similar.

Efficient: At one time this was an informal notion (Joe Kruskal's paper on MST (see here) is an example of that), then it seemed to be P or perhaps BPP. For some its linear or O(n log n) with a small constant. Rather than say the notion changed, its more like it was never that well defined in the first place, and still isn't. 

Constructive: The many diff definitions of this word could be a blog post of its own. In fact, I thought it was, but I could not find it. I did find lots of blog posts that use the word constructive in diff ways. 

Elementary: Also has many definitions, though they are closer together than for Constructive. This one I did do a post on here

Trusting Scientists

 A tweet that made me think.

If you think you don't trust scientists, you're mistaken. You trust scientists in a million different ways every time you step on a plane, or for that matter turn on your tap or open a can of beans. The fact that you're unaware of this doesn't mean it's not so.

— Paul Graham (@paulg) July 26, 2021

The point here is subtle. We don't get on a plane because we "trust scientists", rather we do so because of the strong safety record of commercial aviation. I knew some physicists who won't get on a commuter plane because they worry about the science. Never stopped me.

It is science that we trust to tell us why planes fly, or the water is our tap is (mostly) safe and healthy. I'm not a big fan of beans but not because of the science. Of course I trust science that created the vaccines.

It's not just science, but solid engineering and lots and lots of testing. 

Science isn't always right or consistent. When I was a kid not that long ago, we had nine planets in this solar system, dinosaurs were killed off by climate change and homosexuality was a mental illness. Science is fluid, updating as we learn with new data, models and experimentation. Science is at its best when it doesn't trust itself.

Sometimes people say trust in science to reinforce their beliefs. I've seen smart people say "Trust in the science" about whether vaccinated people should wear masks with completely different conclusions.

I'm a scientist, should you trust me? Let me quote another Paul G. 

“There’s a slightly humorous stereotype about computational complexity that says what we often end up doing is taking a problem that is solved a lot of the time in practice and proving that it’s actually very difficult,” said Goldberg.

The quote comes from a recent Quanta Magazine article about Paul's recent work with John Fearnley, Alexandros Hollender and Rahul Savani on the hardness of gradient descent. Even many NP-complete problems these days can often be solved in practice.

Let's end with the quote attributed to statistician George Box, "All models are wrong, but some are useful". Science gives us ways to understand the world and we need to both trust in the science but know the limitations of what it has to say.

What are the most important 46 papers in Computer Science? Harry Lewis has a book about them!

 (Disclosure:  Harry Lewis was my PhD advisor. For a blog post on  disclosures and bias see my post on that topic here.)

Harry Lewis has a book out: Ideas that Created the Future: Classic Papers in Computer Science

He picked out the 46 (why 46? Why not 46?) classic papers in computer science and, for each one, has a short article saying why its important, and then has the paper itself, though perhaps shortened (leave out the boring parts) or in some cases he has an excerpt of a book (e.g., The Mythical Man Month which is why I blogged about that book recently here).

Harry Lewis has blogged about his book here where he points to my review which is in SIGACT News. 

OR you an use my link to my review here. 

The list of 46 papers had some constraints, so if you wonder why isn't X there it might have hit one of those constraints.

1) No paper past 1980 (he had to stop somewhere).

2) He preferred short readable papers to long or unreadable ones (don't we all!). Before thinking `Gee why isn't paper X in the book' go read paper X. 

3) Some papers cost to much to get permission to reprint. My review points to one such paper that I found 5 links to on the web. 

4) We don't need X papers on topic Y.

Of more interest is some papers that you had not heard of but we can now see are important.

For more thought, read my review!

For even more information, buy the book!

Recognizing Faces

I sometimes have trouble recognizing faces, matching faces to people I've interacted with in the past. It's not a disease like prosopagnosia, I can certainly tell the difference between faces and have no trouble with people I work with directly. But if I haven't seen someone in a while, I may not recognize them or confuse them for someone else. It's especially bad out of context, say running into a professor in my campus on the streets of Frankfurt. It's gotten worse with age but I've had challenges my whole life.

I have my coping mechanisms. I start a conversation to get enough clues to figure out who I'm talking to. I'll google an image before I'm supposed to meet someone I haven't seen in a while. Sometimes I'll just say "Remind me how to pronounce your name again". Sometimes I'll just say something embarrassing thinking the person I'm talking to is someone else.

Name tags are useful, if it isn't obvious you are looking at them. Zoom has been great--everyone's name is just there. I worry that 18 months of zoom meetings means I've lost much of my coping ability, much the way I can no longer navigate by maps the way I used to.

We have technological solutions but mostly unable to make use of them. Through the magic of machine learning, computers have gotten extremely good at recognizing faces. Nevertheless Google Googles actively prevented their one killer app, telling you who you were looking at, for privacy reasons. Perhaps they could limit it to people in your contacts with pictures you uploaded. It would only recognize people you already know.

I know I'm not alone, and I'm writing this post so others won't feel alone. And next time you see me and I look confused, remind me of your name.

Combing two posts: Blankface (Scott Aa) and Is Science Slowing Down? (Scott Al)

(I also posted this to the Less Wrong Website. At least I tried to- I don't quite know if or when it will appear there as its my first post there.) 

Some papers result from taking two papers and combining them. Perhaps nobody else had read both of them so you can say something new! Or (looking over this post) it may guide people to two really good papers, or in this case two really good posts. 

This blog will draw from two excellent blog posts.

Scott Aaronson  blogged on  his website Aug 2, 2021 about blankfaces, people who let stupid or undefined rules dictate what you can do  without apology (see his post for a better explanation). One example that struck me I quote

No, I never applied for that grant. I spend two hours struggling to log in to a web portal designed by the world's top blankfaces until I finally gave up in despair. 

Scott Alexander blogged  on LessWrong on Nov 26, 2018 about Is science slowing down? which answers with an emphatic yes. His point is science-per-researcher is much less than it used to be, and he has graphs and stats to prove it (see his post for the evidence and some speculation as to why this is) One of the reasons he gave struck me which I quote

Certain features of the modern academic system like undepaid PhD's, interminably long postdocs, endless grant writing drudgery, and clueless funders have lowered productivity. The 1930's academic system was ineed 25x more effective at getting researchers to actually do good research.

(A commenter reminded me that Scott Alexander himself dismisses this reason. I do not.) 

(I note that he gives other reasons as well, most notably for our field that the low hanging fruit is gone. Our lack of progress on P vs NP is likely that its a hard problem, rather than the reason above. Of course, if its solved tomorrow by an outsider without funding, I will happily be proven wrong.) 

Scott Alexander hits upon two types of blankfaces (without using the term).

Grant writing drudgery: the rules for how to submit get more and more detailed an onerous. This is  what Scott Aaronson was alluding to. There are other ways its drudgery as well. 

Clueless Funders: the people deciding who gets funded might not know the area (actually in my experience the grant I've reviews have been quite good and the problem is more not enough money to award all that are deserving.) 

SO I pose the following non-rhetorically as always

1) How big a factor is the slowing down of science that blankfaces get in the way?

2) What can we do about it?

Pole Vault Live Blogging

As I write this I'm watching the women's pole vault final in the Olympics. Of the 15 women who made the finals, only four remain after two heights.

To expand on my tweet, I find the pole vault the purest of the Olympic Sports. No electronic monitors and timers, no biased judges, no video review. No points deducted for bad form or failing to stick the landing. No disqualification for a false start or stepping over a line. Either you clear the bar without knocking it down, or you don't.

The high jump has similar properties, but just not as cool looking.

All four made the third height. Now onto 4.85 meters. An American, a Greek, a Brit and a Russian (sorry I meant member of the Russian Olympic Committee).

Back in the day, the TV coverage was rather limited. We'd only see the Americans and the medal winners with too much time spend on human interest backgrounds. Now in the streaming world I can watch every competitor. The good and the bad. Live as it happens.

The Russian Anzhelika Sidorova just cleared 4.85 on her first attempt. So did the Brit Holly Bradshaw and the American Katie Nageotte. The Greek Katerina Stefanidi missed her first attempt but decided to pass on the rest. All now go to 4.90 but Stefanidi only gets two attempts while the rest get three.

Stefanidi missed her first attempt at 4.90. She gets one attempt left.

Sidorova and Bradshaw fail to even reach the bar. Nageotte can't clear the bar.

Now the moment that means everything for Stefanidi. Her last attempt. Make it or the rest get the medals. Stefaidi fails to get a good plant and doesn't get into the air at all. Her Olympics are over.

Second attempt for the others. Sidorva and Bardshaw knock down the bar. Nageotte clears the bar, putting her in prime position. Go USA!

Imagine if we judged research papers this way. Either they get into a conference or they don't. Wait, that is they way they happen, although not always without biased judging.

Sidorova is passing on her last attempt at 4.90. Bradshaw goes for it but hits the bar. She has to settle for Bronze.

Bar is now at 4.95 meters. 

Sidorova gets only one attempt at 4.95. If she makes it, she takes the lead, if she misses, she gets the silver. 

Sidorova doesn't clear and the gold goes to the American Katie Nageotte! 

Just for excitement Nageotte is going for 5.01 meters, which would be her first over five meters in competition. In the men's pole vault, the Swede Armand Duplantis (great pole vault name!) easily won the gold. He moved the bar to 6.19 meters to break his own world record. Came all so close in his first attempt but failed to clear. 

Nageotte is just too excited winning the gold to focus enough to make a serious attempt at 5.01. Can't blame her.

Thus ends the best sport in the Olympics.

Do Four Colors Suffice?

(Guest Post by David Marcus)

Comment by Bill: Haken and Appel proved that all planar maps are 4-colorable. Or did they? David Marcus emailed me that its not quite true and I asked him to post on it, so here it is. The meta point is that math can be very subtle.

And now David Marcus's post:

Is the Four Color Map Theorem true?

It is commonly believed that the Four Color Map Theorem says that four colors suffice to color a planar map. While this is true for any map a non-mathematician would dream up, it is not true for maps a mathematician might dream up without some restriction on the regions that are allowed. This is shown in Hud Hudson's Four Colors Do Not Suffice which appeared in the American Math Monthly, Volume 110,  No. 5, May 2003, pages 417--423. 

Hudson's article is written in a very entertaining style. I recommend that you read it. He constructs a map consisting of six regions R1,...,R6.  Each region is bounded and path connected. There is a line segment B that is  in the boundary of all six regions.  So, six colors are needed, since all six regions share a common boundary. The construction is similar to the topologist's sine curve. For each i , the union of Ri and B is not path connected. Hudson also shows that for any n, there is a map that requires at least n colors.

Hudson thus disproves the following statement:

1)  Four colors are sufficient to color any map drawn in the plane or on a sphere so that no two regions with a common boundary line are colored with the same color.

Appel and Haken actually proved the following:

2) Four colors are sufficient to color any planar graph so that no two vertices connected by an edge are colored with the same color.