Wednesday, October 28, 2020

2020 Fall Jobs Post

My annual fall jobs posts, giving advice to PhDs looking for faculty positions, were getting repetitive. See last year's post for the usual stuff and feel free to post opportunities in the comments on this post. This year let's talk about what's changed.

First something you might have missed--the latest Taulbee Survey shows a small drop in the number of new undergraduate CS majors in 2019 after years of massive growth. Is it a simple blip or have we hit the saturation point? We may never know because of the change you definitely didn't miss seeing.

So let's talk about the effect of COVID. We're seeing a large drop in new international students who are having a hard time getting visas or just avoiding the US like the plague (literally). Not sure those numbers will fully come back given other alternatives and a changing international relationship particularly with China. Many undergrads have delayed college and some may never attend. 

On the other hand, COVID has accelerated digitizing the economy, from videoconferencing to in-home entertainment and games to remote access to work environments. The post-COVID economy could create even a larger demand for computer scientists. 

Many universities curtailed hiring last year worried and may do so in the spring given the uncertain budget situation due to the virus. Others continue to hire in computing, some to make up for last year. I just can't make a prediction for the upcoming year but I wouldn't rush to the job market if you have the option to wait. Last year the CRA reinstated the CIFellows, postdocs to help those in a tight job market, and may do so again next year. The CRA will also repeat its CV database.

Late spring interviews in 2020 went virtual and will likely go virtual again in 2021. Nevertheless take the zoom meetings seriously. Make sure your interview talk is still a discussion--answer questions people give in the chat. Still do your research to have strong conversations with everyone you talk to, especially the non-theorists. And still dress nicely, at least from the waist up. Putting on a sports coat is not a bad idea. 

Though most places continue to focus on data science/ML, cybersecurity and to some degree quantum, Rutgers is specifically looking for a hire in computational complexity. Don't see that everyday. 

Sunday, October 25, 2020

Do not become obsessed with the Polls unless...

I know someone who checks the polls 3 times a day to see who looks like they will be elected prez. She cares A LOT about the election. It is irrelevant to this post who she supports. 

I've asked her `if you find out that, say, Biden is up  8 points instead of 9 in Penn. or that Georgia is looking pretty safe for Trump, or that Texas is in play (really?) how will that change your life? What will YOU do differently?'

She had no answer. Unfortunately she is still a poll-watcher (I know that means something else usually, but you know what I mean.)

So who should be poll-watching or poll-obsessing?

1) To be fair to my friend, she might decide to GIVE MORE to her candidate if the polls are saying that he will lose (whoops- by saying `he' I gave away that her candidate is NOT Jo Jorgenson- Libertarian).  I doubt my friend could say to the campaign `I want to you to spend it in state X since I read that its close there' (I read that some big donors in 2016 demanded more say in where the money was spend. I doubt that's a good idea since I suspect the party knows more about how to best spend the money then the donor does.) 

2) The Biden and the Trump Campaigns SHOULD be poll-watching to decide where to put their efforts. And I suspect they are doing just that.

3) A really big donor (my friend is not one of those) MIGHT want to poll watch to decide if the candidate they want needs money. (I wonder if EITHER candidate needs money since they get so much free media.)

4) Nate Silver-being a poll-watcher is kind-of his job. And of course writing columns about them and making predictions based on what he sees. My friend is not Nate Silver. 

5) Other people who have Nate Silver's job. I can't name any- is Nate Silver the most famous... Gee, not sure what job title he has... SO this is now two questions: What is his job title, call it X, and is he the most famous person who does X?

SO- my point- DO NOT be a poll-obsessive unless the information you get will lead to an action you can take. And I suspect that mostly it does not. 

The primaries are different: If a poll says A can beat X but B cannot beat X, that might guide who you vote for. 

Misc thought: 

 I've heard the phrase `democratic pollster' and `republican pollster' These terms do not make sense. Would I call myself a `democratic Muffin Mathematician' ? My political leanings do not affect my search for truth about mathematical Muffins. Similarly, one would think that a pollster wants to find the TRUTH, even if its bad news for their employer, ESPECIALLY if its bad news for their employer, so they can help their employer fix it. The phrase `pollster employed by the X party' would make more sense-- however, whenever they are on TV they seem to always say that their candidate is doing well, even when they are not. 

ADDED LATER: Lance had a great tweet about this post: do not obsess about polls, but DO obsess bout prediction markets. I think in the past prediction markets have been better predictors but some group-think has set in so its no longer clear. (I could be wrong- but thats why I have heard.) 

Monday, October 19, 2020

Nature vs Nurture close to my birthday

 Since I was born on Oct 1, 1960 (that's not true---if I posted  my real birthday I might get my  identity stolen), I will do a nature vs nurture post based on my life, which seems less likely to offend then doing it on someone else's life. I'll just rattle off some random points on Nature vs Nurture.

1) Is it plausible that I was born with some math talent? Is plausible that I was born with some talent to understand the polynomial van der Warden theorem? What is the granularity of nature-given or nurture-given abilities?

2) My dad was a HS English teacher and later Vice-Principal. My mom taught English at a Community college. Readers of the blog might think, given my spelling and grammar, that I was switched at birth. My mom says (jokingly?) that I was switched at birth since she thinks I am good at math.

a) I am not THAT good at math. Also see next point.

b) While there are some math families, there are not many. See my post here.

c) I think being raised in an intellectual atmosphere by two EDUCATORS who had the money to send me to college and allowed me the freedom to study what I wanted to  is far more important than the rather incidental matter of what field I studied.

d) Since my parents never went into math or the sciences it is very hard to tell  if they were `good at math' or even what that means.

3) There were early signs I was INTERESTED in math, though not that I was good at it.

a) In fourth grade I wanted to know how many SECONDS were in a century so I spend some time figuring it out on paper. Did I get the right answer?  I forgot about leap years.

b) I was either a beneficiary of, or a victim of, THE NEW MATH. So I learned about comm. and assoc. operations in 8th grade. We were asked to come up with our own operations. I wanted to come up with an operation that was comm. but not assoc. I did! Today I would write it as f(x,y) = |x-y|. This is the earliest I can think of where I made up a nice math problem. Might have been the last time I made up a nice math problem AND solved it without help. 

c) In 10th grade I took some Martin Gardner books out of the library. The first theorem I learned not-in-school was that a graph is Eulerian iff every vertex has even degree. I read the chapter on Soma cubes and bought a set. (Soma cubes are explained here.) 

d) I had a talent (nature?) at Soma Cubes.  I did every puzzle in the book in a week, diagrammed them, and even understood (on some level) the proofs that some could not be done. Oddly I am NOT good at 3-dim geom. Or even 2-dim geom.  For 1-dim I hold my own!

e) Throughout my childhood I noticed odd logic and odd math things that were said: 

``Here at WCOZ (a radio station) we have an AXIOM, that's like a saying man, that weekends should be SEVEN DAYS LONG'' (Unless that axiom resolves CH, I don't think it should be assumed.) 

``To PROVE we have the lowest prices in town we will give you a free camera!'' (how does that prove anything?) 

``This margarine tastes JUST LIKE BUTTER'' (Okay-- so why not just buy butter?)

e) In 9th grade when I learned the quadratic formula I re-derived it once-a-month since I though it was important that one can prove such things.  I heard (not sure from where) that there was no 5th degree equation. At that very moment I told my parents:

I am going to major in math so I can find out why there is no 5th degree equation.

There are worse things for parents to hear from their children. See here for dad's reaction. 

f) When I learned that the earth's orbit around the sun is an ellipse and that the earth was one of the foci, I wondered where the other foci is and if its important. I still wonder about this one. Google has not helped me here, though perhaps I have not phrased the question properly. If you know the answer please leave a comment. 

g) I also thought about The Ketchup problem and other problems, that I won't go into since I already blogged about them  here

4) I was on the math team in high school, but wasn't very good at it. I WAS good at making up math team problems. I am now on the committee that makes up the Univ of MD HS math competition. I am still not good at solving the problems but good at making them up. 

5) From 9th grade on before I would study for an exam by making up what I thought would be a good exam and doing that. Often my exam was a better test of knowledge than the exam given. In college I helped people in Math and Physics by making up exams for them to work on as practice. 

6) I was good at reading, understanding, and explaining papers. 

7) I was never shy about asking for help. My curiosity exeeded by ego... by a lot!

8) Note that items 5,6, and 7 above do not mention SOLVING problems. The papers I have written are of three (overlapping) types:

a) I come up with the problem, make some inroads on it based on knowledge, and then have people cleverer (this is often) or with more knowledge (this is rarer) help me solve the problems.

b) I come up with the problem, and combine two things I know from other papers to solve it. 

c) Someone else asks for my help on something and I have the knowledge needed. I can only recall one time where this lead to a paper. 

NOTE- I do not think I have ever had a clever or new technique. CAVEAT: the diff between combining  known knowledge in new ways and having a clever or new technique is murky. 

8) Over time these strengths and weaknesses have gotten more extreme. It has become a self-fulfilling prophecy where I spend A LOT of time making up problems without asking for help, but when I am trying to solve a problem I early on ask for help. Earlier than I should? Hard to know. 

9) One aspect is `how good am I at math' But a diff angle is that I like to work on things that I KNOW are going to work out, so reading an article is better than trying to create new work. This could be a psychological thing. But is that nature or nurture?  

10) Could I be a better problem solver? Probably. Could I be a MUCH better problem solver? NO. Could I have been a better problem solver  I did more work on that angle when I was younger? Who knows? 

11) Back to the Quintic: I had the following thought in ninth grade, though I could not possibly have expressed it: The question of, given a problem, how hard is it, upper and lower bounds, is a fundamental one that is worth a lifetime of study. As such my interest in complexity theory and recursion theory goes back to ninth grade or even further. My interest in Ramsey Theory for its own sake (and not in the service of complexity theory) is much more recent and does not quite fit into my narrative. But HEY- real life does not have as well defined narratives as fiction does. 

12) Timing and Luck: IF I had been in grad student at a slight diff time I can imagine doing work on  algorithmic  Galois theory. Here  is a talk on Algorithmic  Galois theory. Note that one of the earliest results is by Landau and Miller from 1985---I had a course from Miller on Alg. Group Theory in 1982. This is NOT a wistful `What might have been' thought. Maybe I would have sucked at it, so its just as well I ended up doing recursion theory, then Ramsey theory, then recursion-theoretic Ramsey Theory, then muffins. 

Thursday, October 15, 2020

50 Years of PBS

The Public Broadcasting Service (PBS) launched fifty years ago this month in the United States. The New York Times talks about its fifty reasons how the network mattered. I'll throw in my thoughts.

I was just slightly too old for shows like Sesame Street, Electric Company, Mr. Rogers and Zoom, not that that stopped me from watching them. My kids grew up on Barney and Friends. My daughter even had a toy Barney that interacted with the show, which went as well as you'd expect

PBS introduced me to those great British TV shows for young nerds like me including Monty Python and Doctor Who. I wasn't into Nova but did watch Carl Sagan's Cosmos religiously in high school.

My favorite PBS show was the American Experience, short documentaries about US culture. I remember learning about this history of Coney Island and the quiz show scandals before Robert Redford made a movie about it.

Siskel and Ebert got their start on PBS and became my go to source for movie reviews.

In 1987 PBS broadcasted Ivy League football games. One Saturday I sat down expecting to watch my alma mater and instead got supreme court hearings. Only on PBS could Cornell football get Borked.

Monday, October 12, 2020

Hugh Woodin, Kurt Godel, Dwayne `The Rock' Johnson, Robert De Niro, David Frum, Tom Selleck: Do I care what they think? Should I?


My last post on CH mentioned that Hugh Woodin used to think NOT(CH) but now thinks CH. In both cases his reasons have some math content to them. Also, note that Hugh Woodin seems to believe that CH somehow HAS an answer. Kurt Godel also thought CH HAS an answer. It has been said that he could have announced  his result that CH is consistent by saying  L is THE model, and the problem is now solved. 

Should we care what Hugh Woodin and Kurt Godel think about CH?

YES- they have both studied the issue A LOT. If you think CH should have an answer, then surely you would care what they think. 

NO-  CH has no answer so there opinions are no better than mine. If you think CH does not have an answer then you might think this; however, I think you should still be at least INTERESTED in what people who have thought about the problem A LOT have to say, even if you will disagree with them.

But with MATH there are people who clearly know more than you on topics you care about, so it is worth hearing what they have to say. 


Recently Dwayne THE ROCK Johnson (by Wikipedia: actor, producer, businessman, and former professional wrestler) ENDORSED Joe Biden. Should we care about his opinion? Maybe, if wrestling fans and former pro wrestler tend to be Republicans, so this may indicate a shift. I do not know if this is the case. 

Robert De Niro was in favor of impeaching Donald Trump. He also said that Trump was like a Gangster. He would know because he was in the movie GOODFELLOWS and later THE IRISHMAN (about Jimmy Hoffa). To be fair I do not think he said that is how he would know. Even so, I don't think I care what he thinks, unless he has some specialized knowledge I do not know about. 

David Frum is a republican who had a break with the party NOT over Donald Trump, but over Obamacare- which you may recall was originally a CONSERVATIVE response to Hillarycare by the Heritage Foundation.  He has a good article on this here. Because he is an intelligent  republican in favor of Obamacare (or some version of it) he is worth listening to.

In POLITICS its trickier- who is worth listening to and why. For all I know, THE ROCK has made a detailed study of the Republican and Democratic platforms (actually this cannot be true since the Republicans did not have a platform this time). 


Tom Selleck (Actor-Magnum PI a while back, Blue Bloods now)  does commercials for reverse mortgages. A while back I asked a group of people WHY he is doing them. Here were some answers and reactions

a) He needs the money. Not likely, he seems to have done well and does not seem to have the kind of bad habits (e.g., drugs) that need money. Maybe he has expensive tastes (my only expensive tastes is in fine European Kit Kat bars--- which actually are not that expensive). 

b) He likes doing commercials. Maybe.

c) He believes in the product. At this, everyone cracked up in laughter.

This raises a more general point: Why does ANYONE believe ANY commercial since we KNOW the actor is being PAID to say it. I ask non rhetorically as always. 

Thursday, October 08, 2020

Revisiting the Continuum Hypothesis

I have been thinking about CH lately for two reasons

1) I reread the article

Hilbert's First Problem: The Continuum Hypothesis by Donald Martin from Proceedings of Symposia  in Pure Mathematics: Mathematical developments arising from Hilbert Problems. 1976. (For a book review of the symposia and, The Honor Class, also about Hilbert's problems, see here.)

The article takes the point of view that CH CAN have an answer. He discusses large cardinals (why assuming they exist is plausible, but alas, that assumption does not seem to resolve CH) and Projective Det.  (why assuming it is true is plausible, but alas, that assumption does not seem to resolve CH).

(A set A \subseteq {0,1}^omega is DETERMINED if either Alice or Bob has a winning strategy in the following non-fun game: they alternate picking bits a_1, b_1, a_2, b_2, ... with Alice going first. If a_1 b_1 a_2 b_2... IS IN A then Alice wins, IF NOT then Bob wins. Martin showed that all Borel sets are determined. Proj Det is the statement that all projections of Borel sets are determined. AD is the axiom that ALL sets A are determined. It contradicts AC.)

But what really inspired this post is the last paragraph:

Throughout the latter part of my discussion, I have been assuming a naive and uncritical attitude towards CH. While this is in fact my attitude, I by no means wish to dismiss the opposite viewpoint.  Those that argue that the concept of set is not sufficiently clear to fix the truth-value of CH have a position that is at present difficult to assail. As long as no new axiom is found which decides CH, their case will continue to grow stronger, and our assertions that the meaning of CH is clear will sound more and more empty.

2) Scott Aaronson mentioned in a blog post (see here) that  he has read and understood the proof that CH is independent of set theory.

SO, this seemed like a good time to revisit thoughts on CH.

 I took a very short poll, just two people, about CH: Stephen Fenner (in a perfect world he would be a set theorists) and Scott Aaronson (having JUST read the proof that CH is ind.  he has thought about it recently).

Here are some thoughts of theirs and mine

1) All three of us are Platonists with regard to the Naturals (I was surprised to find recently that there are people who are not!) but not with regard to the reals.  So we would be OKAY with having CH have no answer.

2) All three of us  agree that it would be nice if SOME axiom was both

a) Intuitively appealing or aesthetically appealing ,  and

b) resolved CH.

I always thought that (a) would be the hard part-- or at least getting everyone (not sure who we are talking about) to AGREE on a new axiom. But even getting an axiom to resolve CH seems hard.  Large cardinals don't seem to do it, and various forms of Determinacy don't seem to do it.

Scott reminded me of Freiling's Axiom of Symmetry (see here) which IS intuitive and DOES resolve CH (its false) though there are problems with it--- a minor variant   of it contradicts AC (I am QUITE FINE with that since AC implies Banach-Tarski which Darling says shows `Math is broken'.)

Stephen recalled some of Hugh Woodin's opinions of CH, but Hugh seems to have changed his mind from NOT(CH): 2^{aleph_0} = aleph_2, to CH:  2^{aleph_0} = aleph_1.(See here.)

3) All three of would be okay with V=L, though note that this would put many set theorists out of work. All the math that applies to the real world would still be intact.  I wonder if in an alternative history the reaction to Russell's paradox would be a formulation of set theory where V=L. We would KNOW that CH is true, KNOW that AC is true. We would know a lot about L but less about forcing.

4) Which Geometry is true: Euclidian, Riemannian, others? This is now regarded as a silly question: Right Tool, Right Job! If you build a bridge use Euclid. If you are doing astronomy use Riemann. Might Set Theory go the same way? It would be AWESOME if Scott Aaronson found some quantum thing where assuming 2^{aleph_0} = aleph_2 was the right way to model it.

5) If I was more plugged into the set theory community I might do a poll of set theorists, about CH. Actually, someone sort-of already has. Penelope Maddy has two excellent and readable articles where she studies what set theorists believe and why.

Believing The Axioms Ihere

Believing The Axioms IIhere

Those articles were written in 1988. I wonder if they need an update.

Monday, October 05, 2020

MIP* = RE Redux

Everything pre-covid seems at least five years ago to me, so it's hard to believe that MIP* = RE is a 2020 result. To remind you, consider the model where we have two powerful provers put in separate rooms where they can't communicate (think suspects of a crime put in separate interrogation rooms). An computationally efficient verifier can ask them questions based on random coins. Thirty years ago, Laszlo Babai, Carsten Lund and myself showed that every language in nondeterministic exponential time has proofs in this model.

Now suppose the provers have entangled quantum bits. This question has a long history that culminates in the MIP* = RE paper earlier this year by Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen showing that every proof of any length can be proven in this model. Incredible!

But wait, why is there a new version 2 dated last week? Turns out the MIP* = RE paper relied on a 2016 paper by Vidick which was later discovered to have a bug. No worries, as the authors of the MIP* = RE paper got around this issue by a quantum analysis of a low-degree test from that old Babai-Fortnow-Lund paper.

Vidick's blog post explains it all, including the angst of a major result falling apart temporarily. He has good company. Glad it all worked out.