When students are wrong but have a valid point, encourage them

I often have the class VOTE on a statement (the choices are usually TRUE/FALSE/UNKNOWN TO SCIENCE/Stewart-Colbert-2020)

I ask the students who voted incorrectly (some say anything except Stewart-Colbert-2020 is an incorrect vote, though I'm partial to Bee-Oliver, though John Oliver was not born in this country so he's not eligible, though our current president might say that neither was Obama so thats not a bar to the presidency) why they vote the way they do to get a good discussion going. I give some examples. I use real first names but decided to not give last names for reasons of security. The people involved all agreed. If you have examples of students being WRONG but HAVING A POINT, leave an intelligent comment about it!

1) In Discrete Math they  vote on: is Q, the rationals, countable?One of the NO votes was named Alice (really!).

Alice: The rationals, like there are SO many of them. They are just so crammed in their. I mean really!

Bill: I think you want to say that between any two rationals is a rational.

Alice: Thats what I said!!

Bill: Great! And realize that  a set is countable if there is a bijection from the  set to N. So what you are really saying is-----

Alice: There is a bijection between N and Q but not an order preserving Bijection!

2) In Formal Lang theory they vote if alpha is a reg expression and L(alpha) is the lang generated by alpha then is there a reg exp beta such that L(beta) is the complement of L(alpha). One of the NO votes was named Andrea (nickname Andy).

Andy: Given alpha I just don't see an easy way, or for that matter any way, to create beta.

Bill: I will soon prove that regular expressions are equivalent  to DFA's. So what one would do is take the L(alpha), form the DFA, complement the DFA, then convert back to a regular expression.

Andy: Oh, yes that works, but it seems complicated.

Bill: It is! You though it would be complicated so it was false. Even though its true, your intuition that its complicated is correct! In fact, there are reg expressions of length n such that the complement lang has a rather large reg expression.

3) Formal Lang theory again. Not a vote this time. I had on the board the regular expression

(a UNION b)(a UNION  b )^*

A student Dolapo thought it could be simplified:

Dolapo: Can't you write that as the regular expression (a union b)^+ ?

Bill: Yes and no. Yes the lang is (a UNION b)^+, but + is not allowed in regular expressions.

Dolapo: Why not?

Bill: First off, they really could have been defined that way and perhaps should have. So why weren't they? I go with historical accident, but some people disagree- see my blog post here

NP is Hard

You don't get much press by stating conventional beliefs--there is no "round earth society". Nevertheless there are serious researchers out there trying to say that it is reasonably possible if not likely that P = NP. Don't believe it.

Emanuele Viola just outright states I Believe P = NP. He starts with a similar argument that we've seen from Richard Lipton: We've had surprising results in the past so why should the convention wisdom that P ≠ NP be true? I have two major problems with this line of reasoning:

• These arguments cherry pick certain results and ignore the vast majority of theorems that went the way we expected. It's akin to saying that because there have been lottery winners in the past, the ticket I hold in my hand is likely to be a winner.
• All the major surprises in complexity have occurred early in first two decades of the P v NP era. We've seen no surprises at that level since the early 90's. We have seen surprise proofs of results like Primes in P, Undirected Connectivity in Log Space and NEXP not in ACC⁰ but the theorems themselves surprised no one. 

Viola also makes the argument that we've seen fewer significant lower bound results than upper bounds. This doesn't surprise me--an upper bound requires a single algorithm, a lower bound requires showing an infinite number of algorithms can't work. I fully agree that we're unlikely to see a proof that P ≠ NP in the near future. But this isn't a reason to think they are the same. And we've seen no non-trivial algorithms for general NP problems like circuit-SAT.

Which takes me to Ryan Williams Some Estimated Likelihoods For Computational Complexity where he gives 20% probability (which I consider nearly 20% too high) that P = NP based on similar logic. Ryan surprises me even more by giving a whopping 80% chance that NEXP = coNEXP. That would imply every easily describable tautology has a short proof of being a tautology (for the appropriate definitions of describable and short) which I find hard to fathom.

If I would guess collapses that might happen, I would suggest L = NL (directed connectivity in log space) or one that Ryan gives even odds, TC⁰ = NC¹. TC⁰ captures constant-depth neural networks and as we've seen from the ML community, those neural nets look awfully powerful. 

The web bad/People using it bad.

I was going to write a post about how hard it was to find what grades mean at different schools (e.g., at UMCP W (for withdraw) means the student dropped the course, but at UT Austin its Q (for Quit?)) but then I found that my Googling

Name of school grade key

I could find it.  Okay, so grade keys are not that hard to find.

WEB BAD:

However, course descriptions are. Both questions (what grades mean and course desc) came up when I do admissions for my REU program.  If a student has a course in Discrete Mathematics that could mean a course where you learn how to prove simple things OR it could mean a course where you proof  the graph minor theorem (actually I doubt that) or something in between. Similar for Principles of Programming languages and Software Engineering in that they could mean a variety of things. I think math and physics are more standardized, but even there you have the problem that Advanced calc could be either multivar or a course with proofs or something else. There is a great related XKCD here.

PEOPLE USING THE WEB BADLY:

Fellow blogger Scott Aaronson recently posted about Vivek Wadhwa's Washington post column on quantum computing (the post is here) The article by Vivek told the tired and utterly false story that QC can be used to solve TSP by looking at all possibilities. Should Vivik have known better by looking at the web? At first I thought YES he should know better. But then I thought -- I should try to see what he might have done. Maybe the web has this one wrong. In fact, some of my students Iwho, I should add, are not writing articles on QC for the Washington Post)  tell me that they don't need to learn the proof of the Cook-Levin theorem since Quantum Computers can solve SAT anyway.  So I decided to pretend I didn't know anything about QC and went to the web to see what I could find.  First stop: Wikipedia. I found the following quote in the QC article:

BQP is suspected  to be disjoint from NP-complete and  a strict superset of P though this is not known.

So, the first place I look I find that BQP is suspected to NOT solve SAT or TSP or... Realize that Wikipedia is not some obscure source of  hidden knowledge. It is literally the first place one would look.  Hence, no excuse, even if other experts told him otherwise (which seems to be the case, though `experts'  should be in quotes) the Wikipedia quote should at least give pause.

So even when Wikipedia gives the right information, not everyone looks there.

Corporate Education

First of all read the #metoo testimonial going around the TCS blogosphere. Our field is not immune.

Last Sunday Frank Bruni wrote an op-ed column Corporations will Inherit the Earth, an article on how corporations have taken on what governments used to do. Quite a bit is focused on education.

The nimbleness of corporations gives them an edge over hoary, complacent institutions, including those in higher education...In an effort to make sure that employees have up-to-the-minute technical skills--or are simply adept at critical thinking and creative problem solving -- more companies have developed academies of their own. That's likely to accelerate. "I think enterprises like Amazon and Google are going to build universities that teach coding and things the nation needs" said Margaret Spellings, former education secretary and current president of the University of North Carolina system.

Already in the universities we've seen a move towards more majors and minors in STEM and computer science in particular. The changing corporate workplace has already changed academia, putting more an emphasis on technical areas and less on the liberal arts. Will companies though take the next step, running their own schools that focus on the needs of industry? If we see continued decreased government funding for universities and academic research, we may end up with a handful of rich universities and the rest of the population getting education on the job, a future that would be a loss for us all.

A ``new'' ``application'' of Ramsey Theory/A Truly ``bad'' math song

Ian Parberry once told me (though I doubt he originated it- The first link I found says it was Mark Twain)


to a man with a hammer, everything looks like a nail

Indeed. Since I am teaching a grad course Ramsey theory and its ``Applications'' (I got 24 students, which is more than I thought I would- including around 10 ugrads who are taking it because `all the cool kids are taking it' ) I have been taking the hammer of Ramsey Theory and looking for nails to apply it to. (I'm also using a webiste I found of applications of Ramsey Theory here and an survey article on applications of Ramsey here.)

Thinking about the infinite Ramsey Theorem I came up with this ``application'' :

If p1, p2, p3, ... is an infinite sequence of points in Rⁿ then there exists a subsequence q1, q2,q3,... such that for each coordinate 1 ≤ i ≤ n the projection onto that coordinate is either (a) strictly incresing, (b) strictly decreasing, or (c) constant.

Proof:  For i< j color (i,j) with one of 3^n colors - indicating for each coordinate i if the ith projection is increaing, decreasing, or constant. The infinite homog set gives you the sequence.

End of Proof

One can also proof this from the Bolzano-Weierstrass  theorem (an infinite bounded sequence of points in Rⁿ has a convergent subsequence). We leave that proof to the reader; however, the proof of BW looks like the proof of the infinite Ramsey Theorem, so I'm not sure if my proof is new or not.

I wanted to look into the BW theorem so I googled "Bolzano-Weierstrass"  I think Google knows me better than I know myself since the second hit was https://www.youtube.com/watch?v=dfO18klwKHg which is a Rap Song about the BW theorem (I am a fan of novelty songs, and of math, so does it follow I am a fan of Math Novelty songs. Not sure if its follows, but I AM!)

One of the problems on the HW was BW-rap- good, bad, or really bad?

Answers were:

1) Made my ears bleed

2) Lyrics good, singing really bad

3) So bad its good

4) No, just bad.

I'm in the Lyrics good/singing is `so bad its good' camp. The class was okay with the lyrics, but mostly thought it was so bad its... bad. One person thought it was awesome!

I would like to see  real rapper perform  it on you tube. I doubt I will. Oh well.

For the Love of Algorithms

Wired magazine labelled 2017 as The Year We Fell Out of Love with Algorithms. The article goes on to talk about how algorithms give us filter bubbles, affect elections, propagate biases and eliminate privacy. The article at the end argues that we shouldn't blame the algorithm but the people and companies behind them.

Every day algorithms decide what music we listen to, what posts we see on Facebook and Twitter, how we should drive from point A to point B, what products we should buy. Algorithms feed my nostalgia in Facebook and Google Photos showing me what once was. Algorithms recognize my voice and my face. We've even created new currencies from algorithms. Algorithms form the backbone of the top six world's largest public companies (Apple, Alphabet, Microsoft, Amazon, Facebook and Tencent). It's been a long time since I only trusted algorithms to format my papers.

Algorithms have taken over nearly every aspect of our lives and our economy. With new machine learning techniques, no longer can the creator of an algorithm fully understand how algorithms work. But we aren't in a Skynet world, algorithms are not sentient and not even inherently bad, any more than we label a group of people inherently bad because of a few examples.

This societal transition from human-oriented decision to algorithmic decision making will continue and will have great benefits such as much safer cars and medical care. We must be vigilant, of course, to how algorithms will change society, but (in a serious sense) I welcome our new machine overlords.

"How can you use your research for ugrad projects?'- the wrong question

I was helping a math PhD who worked in computable ramsey theory prepare his teaching and research statements for his job application. One of the questions various schools wanted to know was

How can you use your research as the basis for undergraduate projects?

His answer was kind of a cheat- Ramsey Theory was combinatorics which ugrads can work on without too much prior knowledge (true), computability theory could be picked up (not true), and the chance to combine the two should thrill ugrads (it doesn't even thrill most Ramsey Theorists!).

I don't fault the PhD student, I fault the school. What they really want to know is:

Can you come up with ugrad projects?

They should realize that some math requires too much bacground and is not appropriate for ugrads AND that a math PhD will have picked up OTHER knowledge for projects. They may relate some to the research (e.g., in the case above just Ramsey Theory) or they may not even be close.

In Comp Sci it is more common for an ugrad to work on research related to a profs research since Comp Sci is a younger field and needs less background knowledge. And students can often code something up of interest related to the profs research.

SO- do you have ugrads work on your research program OR on something else?

Flying Blind

Many computer science conferences have made a number of innovations such as a rebuttal phase, multi-tiered program committees, a hybrid journal/conference model with submission deadlines spread through the year. Not theoretical computer science which hasn't significantly changed their review process in the major conferences since allowing electronic submissions in the early 90's and an ever growing program committee now at 30 for FOCS.

Suresh Venkatasubramanian learned this lesson when he ran a double blind experiment for ALENEX (Algorithmic Engineering and Experiments) and laid out an argument for double blind at broader theory conferences to limit the biases that go along with knowing the authors of a paper. The theory blogosphere responded with posts by Michael Mitzenmacher, Boaz Barak and Omer Reingold and a response by Suresh. I can't stay out of a good conference discussion so here goes.

Today major orchestra auditions happen behind a screen with artists even told to remove footwear so sounds won't give away the gender of the musician. On the other extreme, the value of a piece of art can increase dramatically in price if it is discovered to be the work of a famous artist, even though it is the same piece of art. Where do research papers lie? It's more a work of art than a violinist in a symphony.

Knowing the authors gives useful information, even beyond trusting them to have properly checked their proofs. Academics establish themselves as a brand in their research and you learn to trust that when certain people submit to a conference you know what you get, much the way you would more likely buy a new book from an author you love.

Suresh rightly points out that having authors names can and do produce biases, often against women and researchers at lesser known universities. But we should educate the program committee members and trust that they can mitigate their biases. We can completely eliminate biases by choosing papers at random but nobody would expect that to produce a good program.

Having said all that, we should experiment with double blind submissions. Because everything I said above could be wrong and we won't know unless we try.