The Tenure system is broken but not in the way that you think (Anon Guest Post)

This is an ANON guest post. Even I don't know who it is! They emailed me asking if they
could post on this topic, I said I would need to see the post. I did and it was fine.

-----------------------------------------------------------------------------------------------------------------
I have written many tenure/promotion letters before. But this summer, I was especially inundated with requests. Thinking about my past experiences with such letters, I started to question their value.

For those unfamiliar with the process, let me explain. When someone is applying for a research job, they typically need to have recommendation letters sent on their behalf. Once someone is hired in
a tenure-track position, they then need to get additional letters each time they are promoted (in the US, this will typically occur when someone is granted tenure and again when they are promoted to full
professor).

Now, I know from experience that recommendation letters are scrutinized very carefully, and often contain useful nuggets of information. I am not questioning the value of such letters (though
they may have other problems). I am focusing here only on tenure/promotion letters.

Let me fill in a bit more detail about the tenure/promotion process,since it was a mystery to me before I started an academic position. (I should note that everything I say here is based only on how things are
done at my institution; I expect it does not differ much at other US universities, but it may be different in other countries.) First, the department makes a decision as to whether to put forward someone's
case for promotion. If they do, then a package is prepared that includes, among other things, the external recommendation letters I am talking about. After reviewing the candidate's package, the department holds an official vote; if positive, then the package is reviewed and
voted on by higher levels of administration until it is approved by the president of the university.

The external letters appear very important, and they are certainly discussed when the department votes on the candidate's case. However, I am not aware of any cases (in computer science) where someone who was put forward for tenure was denied tenure. (In contrast, I am aware of a very small number cases where a department declined to put someone forward for tenure. In such cases, no letters are ever
requested.) Perhaps more frustrating, this seems to be the case even when there are negative letters. In fact, I have written what I consider to be "negative" letters in the past only to see the candidate still get tenure.(To be clear, by academic standards a negative letter does not mean saying anything bad, it just means not effusively praising the candidate.) This makes be believe that these letters are simply being used as "checkboxes" rather than real sources of information to take into account during the decision-making process. Essentially, once a department has decided to put someone forward for promotion, they have effectively also decided to vote in favor of their promotion.

Letters take a long time to write, especially tenure/promotion letters, and especially when you are not intimately familiar with someone's work (even if they are in the same field). But if they are
basically ignored, maybe we can all save ourselves some time and just write boilerplate letters (in favor of tenure) instead?




Are Conferences Discriminatory?

Glencora Borradaile wrote a blog post in June about how conferences discriminate.

Let me spell it out. In order to really succeed in most areas of computer science, you need to publish conference papers and this, for the most part, means attendance at those conferences. But because of the institutional discrimination of border control laws and the individual discrimination that individuals face and the structural discrimination that others face, computer science discriminates based on nationality, gender identity, disability, and family status, just to name a few aspects of identity.

Suresh Venkatasubramanian follows up with a tweet storm (his words) echoing Glencora's points.

Is there structural (i.e not intentional or institutional) bias in how conferences operate? I.e is there a systematic and persistent disadvantage to certain groups from how conferences are structured? If we consider location, and groups = non-US people, then yes.

— Suresh Venkatasubramanian (@geomblog) July 6, 2018

Ryan Williams had a twitter thread defending conferences.

Because of where I live and work, I can collaborate with and see talks by many more people than the average person in my field. To me, conferences serve as a way of *leveling* that field, giving a venue where people from all over can benefit similarly.

— R. Ryan Williams (@rrwilliams) July 7, 2018

Not much difference these day between blog posts, tweet storms and twitter threads and I recommend you read through them all.

Much as I think conferences should not serve as publication venues, they do and should play a major role in connecting people within the community. We should do our best to mitigate the real concerns of Glencora and Suresh, create an environment that everyone feels comfortable, have travel support and child care to make it easier and have meetings in different countries so those with visa issues can still attend at times. But we cannot eliminate the conference without eliminating the community. Personal interactions matter.

The Rule of Threes/Astrology

On Aug 16, 2018 Aretha Franklin died. A famous singer.

On Aug 18 2018 Kofi Anan died. A famous politician.

On Aug 25, 2018 John McCain died. A famous politician.

On Aug 26, 2018 Neil Simon died, a famous playwright.

For 12 famous people who died between Aug 5 and Aug 26 see here (be careful- there are a few more on the list who died in August but a different year).

One could group those 12 into four sets of three and claim the rule of threes that celebrities die in threes. There was an episode of  30 Rock   where two celebrities had died and Tracy Jordan (a celeb) tried to kill a third one so he would not be a victim of the rule of threes. (see the short video clip: here.)

How would one actually test the rule of threes? We would need to define the rule carefully. I have below a well defined rule, with parameters you can set, and from that you could do data collection (this could be a project for a student though you would surely prove there is no such rule).

1. Decide on a definite time frame: T days. The deaths only count if they are within T days.
2. Define celebrity. This may be the hardest part. I'll start with they must have a Wikipedia page of length W and they must have over H  hits on Google. This may be hard to discern for people with common names or alternative spellings. You might also look into Friends on Facebook and  Followers on Twitter. A big problem with all of this is that if you want to do a study of old data, before there was Google, Wikipedia, Facebook, and Twitter, you will need other criteria (ask your grandparents what it was like in those days).
3. Decide whether or not to have a cutoff on age. You may decide that when Katherine Hepburn, Bob Hope, and Strom Thurmond died less than a month apart, at the ages of 96, 100, 100 this doesn't qualify. Hence you may say that the celebrities who die must be younger than Y  years.

I doubt anybody  will ever do the experiment--- those that believe its true (are there really such people?) have no interest in defining it carefully or testing it. And people who don't believe would not bother, partially because so few people believe it that its not worth debunking. But I wonder if a well thought out experiment might reveal something interesting. Also contrast the data to all deaths and see if there is a difference. For example, you might find that more celebs die in August then would be expected based on when all people die. Or that celebs live longer. Or shorter. Actually with enough p-hacking I am sure you could find something. But would you find something meaningful?

Astrology is in the same category- people who believe (there ARE such people!)  could do well defined experiments but have no interest in doing so. I doubt they would find anything of interest if they did. Here there are enough people who believe it in to be worth debunking, but would a well designed science experiment convince them that astrology does not have predictive powers? Has such been done?


I once DID do such an experiment to disprove a wild theory. In 2003 a cab driver once told me (1) there is no Gold in Fort Know, and Ian Fleming was trying to tell us this in the book Goldfinger,  (2)  Reagan was shot since he was going to tell,  (3) a small cohort of billionaires  runs the world. I challenged him-- if that is the case then how come in 1992 Bill Clinton beat George Bush, who was surely the billionaires  pick. He responded that Bill Clinton was a Rhodes Scholar and hence he is in-the-club. I challenged him- OKAY, predict who will get the Democratic Nomination in 2004. This was a well defined experiment (though only one data point) He would give me a prediction and I could test it. He smiled and said Wesley Clark was a Rhode Scholar. Oh well.

What is Data Science?

The Simons Institute at Berkeley has two semester long programs this fall, Lower Bounds on Computational Complexity and Foundations of Data Science. The beginning of each program features a "boot camp" to get people up to speed in the field, complexity last week and data science this week. Check out the links for great videos on the current state of the art.

Data Science is one of those terms you see everywhere but not well understood. Is the the same as machine learning? Data analytics? Those pieces only play a part of the field.

Emmanuel Candès, a Stanford statistician, gave a great description during his keynote talk at the recent STOC theoryfest. I'll try to paraphrase.

The basic scientific method works as follows: You make an hypothesis consistent with the world as you know it. Design an experiment that would distinguish your hypothesis from the current models that we have. Run the experiment and accept, reject or refine your hypothesis as appropriate. Repeat.

The Higgs Boson followed this model as a recent example.

Technological Advances have given us a different paradigm.

1. Our ability to generate data has greatly increased whether it be from sensors, DNA, telescopes, computer simulations, social media and oh so many other sources.
2. Our ability to store, communicate and compress this data saves us from having to throw most of it away.
3. Our ability to analyze data through machine learning, streaming and other analysis tools has greatly increased with new algorithms, faster computers and specialized hardware.

All this data does not lend itself well to manually creating hypotheses to test. So we use the automated analysis tools, like ML, to create models of the data and use other data for testing those hypotheses. Data science is this process writ large.

We are in the very early stages of data science and face many challenges. Candès talked about one challenge: how to prevent false claims that arise from the data not unrelated to the current reproducibility crisis in science.

We have other scientific issues. How can we vouch for the data itself and what about errors in the data? Many of the tools remain adhoc, how can we get theoretical guarantees? Not to mention the various ethical, legal, security, privacy and fairness issues that vary in different disciplines and nations.

We sit at a time of exciting change in the very nature of research itself, but how can we get it right when we still don't know all the ways we get it wrong. 

Is Trivium (the Stream Cipher) used?

This Fall I am teaching the senior course in Crypto at UMCP. Its a nice change of pace for me since REAL people REALLY use this stuff! Contrast to last Spring when I taught

                   Ramsey Theory and its `Applications'

There is one topic in the Crypto course that LOOKS really useful but I can't tell if it IS being used, so I inquire of my readers. (I will probably come across others topics like that in the future.)

A Secure Stream Cipher is (informally) a way to, given a seed and optionally an Init Vector (IV), generate bits that look random. Alice and Bob communicate the seed either in person or over a private channel or perhaps by using RSA (or some other public key system) and they then both effectively have a very long string of random bits. They send the IV in the clear. They can then do one-time-pad (really a psuedo-one-time-pad). There are other uses for random-looking bits as well.

So what is needed is a Secure Stream Cipher.  Trivium seems to be one such. According to the Trivium wiki

It was submitted to the Profile II (hardware) of the eSTREAM compeition by its authors Christophe De Canniere and Bart Preneel, and has been selected as part of the portfolio for low area hardware ciphers (Profile 2) by the eSTREAM project. It is not patented.

According to these papers: here and here, and the Wikipedia entry, here the following are true:

1) Trivium takes an 80 bits seed and an 80 bit IV

2) The implementation is simple and is already in hardware. Around 3000 logic gates.

3) There are reasons to think its random-looking but no rigorous proof.

4) So far it has not been broken, though its not clear how many people have tried. Thats goes to my question-- how widely used it is it?

5) Trivium need 1152 steps in the init phase. If it only does 799 then The Cube Attack can break it in 2^68   which is better than the naive algorithm of trying every key and IV (2^160) but still not feasible.

6) Trivium is also An American Metal Band and a Medieval theory of education. Its a good name for a band. See my post What Rock Band Name Would you Choose? for fictional good names for bands with a math or theoretical cs connection.

OKAY, back to the main topic:

SO my questions:

Is Trivium used?

If so then by whom and for what (for the psuedo 1-time pad?) ?

If not then why not (e.g., some of of my points above are incorrect)? and should it be instead
of what is being used?

Katherine Johnson (1918-)

Katherine Johnson is celebrating her 100th birthday today. This is the first centenary post we've done for a living person.

The movie Hidden Figures made her story famous: In 1952, she joined NACA, the predecessor of NASA, in the all-black West Area Computing section of the Langley lab in Virginia. During the "space race" of the 50's and 60's she worked on trajectory analysis for the early human spaceflights. In 1960, she was the first woman to co-author a technical report for NASA on placing satellites over a specific latitude and longitude.

The West Area Computing section had human computers working on the critical calculations for air and space travel. Soon NASA started moving that work to IBM machines but much as we don't fully trust machine learning today, humans didn't initially trust these computers. John Glenn's first orbital mission required complex calculations to track his flight. He insisted on Katherine Johnson working out the computations herself, which she did. "If she says they're good then I'm ready to go".

In 2015, then President Obama awarded Katherine Johnson the highest US civilian honor, the Presidential Medal of Freedom.

The Zero-One Law for Random Oracles

A couple of years ago, Rossman, Servedio and Tan showed that the polynomial-time hierarchy is infinite relative to a random oracle. That is if you choose each string independently to be in or out of an oracle R with probability one, the polynomial-time hierarchy will be infinite relative to R with probability one. This is one in the measure theory sense, there are oracles where it is false, it is just that those oracles will occur with zero probability.

There are still a few open questions for random oracles, such as whether P = BQP, quantum and classical computing can solve the same problems efficiently.. We suspect that P is different than BQP relative to a random oracle because otherwise BQP would be the same as BPP unrelativized (and thus factoring is easy), but we have no proof. Could it be possible that this problem has no simple resolution, that P = BQP holds with probability 1/2 relative to a random oracle, or some other probability strictly between 0 and 1? As it turns out no.

Some statements do hold with intermediate probabilities. The sentence "0101 in R" holds with probability 1/2. Even for a fixed machine M, questions like "M^R accepts an infinite language" could hold with probability say 3/8.

But statements like P = BQP relative to R can't happen with intermediate probability. That's due to the Kolmogorov zero-one law. If you have a subset of oracles that are closed under finite differences, that set must occur with probability zero or one. Every statement about complexity classes has that property because we can hard wire finite differences of the oracle into the machine description without increasing the running time. It will change the machine but not the complexity class. So P = BQP holds with probability zero or one even though we can't tell which one yet.

The Kolmogorov zero-one law gives us a consistent look at complexity classes. Since the countable union of zero probability events still has probability zero, every finitely-described statement about complexity classes that hold with probability one, all simultaneously hold with probability one. While this random world does not match the unrelativized one, it does give us a relativized world where we can explore the different possible relationships between complexity classes.

Fractional Problems: 2.1-colorable, 2.8-SAT

Some graphs are 2-colorable, some graphs are 3-colorable, some graphs are...Does it make sense to say that a graph is 2.1-colorable? It does!(Source_ Factional Graph Theory by Schneinerman and Ullman-- I saw a talk on this by Jim Propp a long time ago.)

Def 1: A graph is (a,b)-colorable (with a \ge b) if you can assign to every vertex a set of b numbers from {1,...,a} such that if u and v are adjacent then the set of numbers are disjoint. Note that k-colorable is (k,1)-colorable. Let chi_b(G) be the least a such that G is (a,b)-col.
 The fractional chrom num of G is lim_{b-->infinity} chi_b(G)/b.

Def 3:  We restate the ordinary Chrom Number problem as an integer program (and NOT by using that
Chrom Num \le SAT \le IP).  In fact, our Int Prog will be LARGE. For every ind set I of G we have a 0-1 valued var x_I which will be 1 iff x_I is all one color. We want to minimize \Sum_I x_I with the constraint that, for every vertex v in the graph. sum_{v in I} x_I \ge 1, so every vertex is colored.
: Fractional Chrom number is what you get if you relax the above IP to an LP with x_I in [0,1] instead of {0,1}.

Defs 1 and 2  turn out to be equiv. The wikipedia entry on Fractional Chromatic Number (see here) is pretty good and has some applications to real world things.

QUESTION: 2-col is in P, 3-col is NPC. What about, say, 2.1-col. It turns out that, for every c>2, c-col is NPC.

Open question (which Jim Propp used to begin his lecture): Every planar graph is 5-col has an EASY proof. Every planar graph is 4-col has a HARD (or at least tedious) proof. Is there a nice proof that every planar graph is (say) 4.5-colorable? The answer is Yes, Every planar graph is 4.5 colorable.  I blogged on it here.

Are there other fractional problems related to NPC problems. YES- at a Dagstuhl there was a paper on (2+epsilon)-SAT. (by Austrin, Guruswami, Hastad) (see here).

What is fractional SAT? Lets recall ordinary k-SAT: every clause has k literals and you need to make at least one of them true. What if you wanted to make at least 2 of them true? (a/b)-SAT is if every clause has exactly b literals and you want an assignment that makes at least a in each clause true.

GOOD NEWS: for all epsilon, (2+epsilon) is NP-complete. Its not so much good that its true, but its good that its known.

BAD NEWS: The proof is hard, uses lots of tools.

ODD NEWS: The speaker said that they PROVED there was no easy proof.

I think its worth having your students try to DEFINE these terms on their own. The NPC proofs may be over their heads (they may be over my head), but the definitions are nice and the students might be able to derive them.

QUESTION: Do other NPC problems have Fractional versions? I would think yes. This could lead to a host of open problems OR perhaps they have already been asked. If you know of any, please comment.

How valuable is a Fields Medal?

(Johan Hastad won the Knuth Prize! The below post was written before I knew that but has a mild connection to it. See here for more info on the Hastad winning it, or see Lance's tweet, or see Boaz's blog post here. There will prob be other blogs about it as well. ADDED LATER: Lipton and Regan have a post on this here.)




The Fields Medal was recently awarded to

Caucher Birkar

Alessio Figalli

Peter Scholze

Akshay Venkatesh

I was going to try to give one sentence about what they did, but Wikipedia does a better job than I ever could so I point there: here. Terry Tao also has some comments on the Fields Medal here. So does Doron Zeilberger here.

How much is a Fields medal worth?

1) The winners get $15,000 each.

2) Winning a Fields medal gets one a higher salary and the ability to change schools, so the $15,000 might not be the main monetary part.  All Field Medalists are under 40 so the salary increases and such last for a much longer time then (say) a Nobel prize given for life achievements to someone much older. So you may rather win a Fields' medal when you are 39 than a Nobel when you are 70. The Abel prize is around 740,000 dollars and (I think) given for lifetime achievement so again, a Fields Prize may be better. (See here for more on the Abel Prize).  Which would I prefer to win? I would be delighted if that was my dilemma.

3) I am sure that none of the four winners went into math because of the allure of the $15,000 Fields Medal.

4) The title of this post is ambiguous. It can also be read as

how valuable is the actual medal?

The answer is $4000, much more than I would have thought. I only know this since it was recently stolen, see here.

This raises a linguistic question. The four people above can say

                                                          I WON a Fields Medal

The thief can say

                                                          I HAVE a Fields Medal

and hope that people don't quite realize that he didn't earn it.

(The article about the theft says the Fields medal is $11,500 dollars. Do they deduct the cost of the Medal itself? Or is the article wrong?)

While I Was Away

After the Oxford Workshop I enjoyed a two-week family vacation in Spain, where there was no rain in the plain, just very hot up to 106℉. The old Spanish cities knew how to optimize for shade and breeze, more than I can say for Oxford.

Meanwhile in a more moderate Brazilian climate, the International Congress of Mathematicians awarded their medals, including the Rolf Nevanlinna Prize to Constantinos Daskalakis in a year with several very strong candidates. The Nevanlinna prize gets awarded every four years to a researcher under 40 for contributions to mathematical aspects of information sciences. Costis was the then-student author of the 2004 Nash Equilbrium is PPAD-complete result and has gone on to be a leader in the algorithmic game theory community.

The ICM also distributes the Fields Medal, the highest honor in mathematics. Much ado is given to Peter Scholze who received the award this year at the age of thirty though remember that Alexander Razborov received his Nevanlinna prize at the age of 27 in 1990. Caucher Birkar also received the Fields Medal at the more standard age of 40 but had it for only a few minutes before it was literally stolen away.

I didn't realize how much I appreciate the convenience of Uber and Lyft until I had to get around cities where they don't exist. Meanwhile New York started to limit ride-sharing vehicles and I arrived in Madrid to a taxi strike protesting Uber in that city. The Yin and Yang of technology.

The Future of TCS Workshop, celebrating V Vazirani 60th, now online

On June 29, 2018, a workshop was held, in conjunction with STOC 2018, to celebrate the accomplishments of Vijay Vazirani on the  occasion of his 60th birthday, organized by his PhD students, Aranyak Mehta, Naveen Garg and Samir Khuller. The workshop was called "TCS: Looking into the Future" and true to the title, it was precisely that!  In front of a large, enthusiastic audience, left over from STOC, the star-studded lineup of speakers outlined some of the most avant-garde, far out ideas  on the future of computing.  Fortunately, this exciting and highly thought-provoking set of talks was recorded for posterity  and is available for all to view here
THE LAST WORD `here' IS THE LINK to the website which has links to the four talks.

The speakers were:

Len Adleman, Manuel Blum, Richard Karp, Leonard Schulman, Umesh Vazirani.

1) I URGE you to all WATCH those talks!

2) I really like it when talks are available on line after the fact so even if you didn't go (I didn't) you can still see the talks later.

3) So many talks to watch, so little time, alas!

4) Sorry for the white background for this post- that happens sometimes. NO comments on it please.

Three trick questions in Formal Lang Theory

There are three questions I ask in my Formal Lang Theory class that even the very best students get wrong. Two I knew were trick quesions, the other I was surprised by

1) If w is a string then SUBSEQ(w) is all strings you can form by replacing some symbols in w
with empty string. SUBSEQ(L) is defined in the obv way.

I ask the following in class (not on an exam). TRUE or FALSE and WHY and we'll discuss
If L is regular then SUBSEQ(L) is regular
If L is context free then SUBSEQ(L) is context free
If L is decidable then SUBSEQ(L) is decidable
If L is c.e. (used to be called r.e.) then SUBSEQ(L) is c.e.

The students pretty much get and prove that 1,2, and 4 are TRUE. They all think 3 is false.
But is true. For a strange reason

If L is ANY lang whatsoever then SUBSEQ(L) is regular. Comes from wqo theory. For more on this see a blog post I did when I was a guest blogger (it shows- the typeface is terrible) here

2) How many states does and NFA  need for { a^n : n \ne 1000} (or similar large numbers). ALL of the students think it takes about 1000 states. They are wrong: here

The two above I know people get wrong. The third one surprised me, yet every year the good students get it wrong

3) BILL: We showed that
a) 2-colorablility is in P, hence of course planar 2-colorability is in P
b) 3-colorability is NP-complete
c) 4-colorabilty of Planar graphs is in P

SO what about 3-colorability of planar graphs?

My very best student said the following last spring:

Planar 2-col is in P

Planar 4-col is in P

so I would guess that Planar 3-col is in P.

In prior years others made the same mistake.  My opinion of these students is NOT lowered, but I am surprised they make that guess. Of course, once you KNOW something you have a hard time recovering the state of mind of NOT knowing it, so my being surprised says more about my having drunk the Kool aid then their thought patterns.

Complexity in Oxford

Oxford, England is in the middle of a heat wave and it handles high temperatures about as well as Atlanta handles snow. But that can't stop the complexity and a wonderful workshop this past week. It's my first trip to Oxford since I came five years ago to celebrate the opening of the Andrew Wiles building, a building that hosted this weeks' workshop as well.

We also got a chance to see old math and physics texts. Here's Euclid's algorithm from an old printing of Euclid's Elements.

Unlike a research conference, this workshop had several talks that gave a broader overview of several directions in complexity with a different theme each day.

A few highlights of the many great talks.

Sasha Razborov gave a nice discussion of proof systems that help us understand what makes circuit bounds hard to prove.

Tuesday was a day for pseudorandomness, finding simple distributions that certain structure can't distinguish from random. Ryan O'Donnell talked about fooling polytopes (ANDs of weighted threshold functions). Avishay Tal talked about his new oracle with Ran Raz, viewing it in this lens as a distribution that the low-depth circuit can't distinguish but quantum can. I talked about some simple extensions to Raz-Tal and the possibilities of using their techniques to show that you can't pull out quantumness in relativized worlds.

Toni Pitassi talked about lifting--creating a tight connection between decision tree and 

complexity bounds to export lower bounds from one model to the other. Yuval Ishai talked about the continued symbiosis between complexity and theoretical cryptography.

Ryan Williams talked about his approach of using circuit satisfiability algorithms to prove lower bounds that led to his famed NEXP not in ACC⁰ result. He has had considerable recent progress including his recent work with Cody Murray getting reducing NEXP to nondeterministic quasipolynomial time.

Great to get away and just think complexity for a week. Seeing my former students Rahul Santhanam and Josh Grochow all grown up. And realizing I've become that old professor who regales (or bores) telling complexity stories from long ago. 

Need EASY approaches to getting unif random from non-random sources

Teaching crypto for the first time next semester I am looking into lots of stuff I always meant to look into but now I have to. NOT a complaint- good to be forced to expand my horizons (within TCS).

I"m also finding out that the web is great for easy and hard stuff but not so good for medium stuff.

Here is what I want to know so I am reaching out to my readers.

KNOWN: you want to generate a unif rand seq of 0's and 1's. The bits you can generate are Independent (yeah) but biased (boo). So here is what you do: generate 2 at a time and

if see 00 then DO NOT USE

if see 11 then DO NOT USE

if see 01 then generate 0

if see 10 then generate 1

KNOWN: You can do similar things if you have 00, 01, 10, 11 independent. And also if you have 000, 001, blah blah , 111 independent.

I tried looking up if there is a better way and I came across some complicated papers. I need material for a senior course. So, are there INTERMEDIARY results Suitable for a classroom, on better ways to us an imperfect source to get unif rand?

CRA Snowbird 2018

Marios Papaefthymiou (UC Irvine), Michael Franklin (U. Chicago), Larry Birnbaum (Northwestern) and me.

This week I attended the 2018 Computing Research Association Snowbird conference, a biennial meeting of Computer Science chairs and leadership mostly from the US. This is my fifth Snowbird meeting, once as a panelist talking about publications and now four times as a chair.

One cannot deny the success of computer science over the past decade. Our enrollments have jumped dramatically, our students at all levels get great jobs, CS departments are expanding. CS research and ideas play fundamental roles in society usually but not always for the better. We have our challenges, how to we hire new faculty when most PhDs take industry jobs and how to cover the increasingly heavy course enrollments, but we do not have the existential discussions you might find in similar meetings in other disciplines.

While the best part of the meeting happens in informal discussions in the hallways and on the mountain, several sessions bring out some specific topics in the minds of participants. A few that caught my interest.

In the first Snowbird of the #metoo era, we had some good discussion and a few scary stories about what women face at conferences and academic departments. The ACM has a new conference harassment policy and many CS communities, including theoretical computer science, are tackling this issue head on. This is part of a longer and larger struggle the field has had in attracting and retaining women and underrepresented minorities into the community.

One session focused on pushing metric-based rankings of computer science programs with presentations of Microsoft Academic Search, CRA’s own CS metrics and Emery Berger’s CS Rankings. CS Rankings has grown in popularity, particularly among undergrads looking at grad schools and Emery discussed how he’s created an advisory board that carefully considers how to count papers.

Personally I prefer the reputation-based rankings like US News, but I was definitely the tiny minority in the room.

The Mystical Bond Between Man and Machine

You just can't watch a movie these days without being inundated with trailers. First came Axl, a movie about a boys love for a military robotic dog.

 

"It's only a robot," says his father. "It's an intelligent robot" replies the kid. Then comes the generic ET-like story of the government coming for the robot.

Next came a trailer for a movie that start off with Hailee Steinfeld discovering a VW bug with the background voice going "The driver don't pick the car. The car picks the driver". I'm thinking it's either a new Herbie movie or Transformers. Spoiler: Transformers.


"There's a mystical bond between man and machine" the voice intones. Followed by action that looks just like Axl.

Movie love for machines is hardly new. You can go back to Her or Short Circuit or even Metropolis in 1927. But in an age that parents worry about their kids being rude to Alexa perhaps this mystical bond is starting to get just a little too real.

The Six Degrees of VDW

 A long long time ago  a HS student, Justin Kruskal (Clyde's  son)  was working with me on upper bounds on some Poly VDW numbers (see here for a statement of PVDW). His school required that he have an application.  Here is what he ended up doing: rather than argue that PVDW had an application he argued that Ramsey Theory itself had applications, and since this was part of Ramsey Theory it had an application.

How many degrees of separation were there from his work and the so called application.

1. The best (at the time) Matrix Multiplication algorithm used 3-free sets.
2. 3-free sets are used to get lower bounds on VDW numbers.
3. Lower bounds on VDW numbers are related to upper bounds on VDW numbers
4. Upper bounds on VDW are related to upper bounds on PVDW numbers.

Only 4 degrees!  The people in charge of the HS projects recognized that it was good work and hence gave him a pass on the lack of real applications. Or they didn't quite notice the lack of applications. He DID end up being one of five students who got to give a talk on his project to the entire school.

When you say that your work has applications is it direct? one degree off? two? Are all theorems no more than six degrees away from  an application? Depends on how you define degree and application.

Soliciting answers for THIRD survey about P vs NP

I have done two surveys for SIGACT NEWS Complextiy Column (edited by Lane Hemaspaandra)
on P vs NP and related topics.  Lane has asked me to do a third. I annouced it in my open problems column here For those who don't read SIGACT news

1) You should!

2) Here is where to go to fill out the survey: here

bill g.

P.S. (do people use P.S. anymore? Do young people know that it means Post Script, and that it
does not refer to ps-files?)

A commenter requested I add what the DEADLINE for responding was. I originally thought people would read the post and immediately respond (and I HAVE had a BIG uptick in responses in the last day). I still believe this. BUT there are people who read the blog days, weeks, months, even years after I post it (though the comments we get on very old posts tend to contain clicks for good deals on Tuxedo's (I am serious. Tuxedo's? Not well targeted unless they count my Tuxedo T-shirt).

Okay, enough babbling -- the point is that I should have a deadline for those who read the blog later than now.

DEADLINE: Oct 1, 2018. STRICT!

P.P.S - does anyone use P.P.S anymore?

Happy 90th Juris!

Juris Hartmanis turns 90 today. Hartmanis with Richard Stearns received the 1993 Turing Award for their seminar work On the Computational Complexity of Algorithms. I've talked about that paper before, after all it started our field and gave the name that we use for the blog. So instead I'll use this blog post to talk about how Hartmanis led me into this wondrous field.

At Cornell in 1983 I was an undergraduate double major in math and CS destined at the time for grad school in math. I took the undergraduate Introduction to Theory course from Hartmanis and immediately got excited about the field. Hartmanis said the top student in the course was typically an undergrad followed by a bunch of graduate students. I was a counterexample coming in second in the course list (back then your grades were posted by ID number). I never found out who came in first.

In that same semester I took Introduction to Linguistics. Chomsky and context-free languages in both classes. Seemed cool at the time.

Based almost solely on that course with Hartmanis I decided to do graduate work in theoretical computer science. In the spring of 1985, while most of my fellow second-semester seniors took Introduction to Wine, I took graduate Complexity Complexity again with Hartmanis. That cemented my career as a complexity theorist. The course started with some basic computability theory (then called recursion theory) and used that as a jumping point to complexity. A large emphasis on the Berman-Hartmanis Isomorphism Conjecture. The conjecture implies P ≠ NP and Hartmanis said anyone who could prove the conjecture, even assuming P ≠ NP, would get an automatic A. The problem remains open but I did years later have a couple of proofs giving an oracle making BH true. That should be good enough for a B.

My favorite quote from Juris: "We all know that P is different from NP, we just don't know how to prove it." Still true today.

The BREAKTHROUGH on Chromatic Number of the Plane (guest post)

(The new SIGACT News chair wnated me to post a letter he send to all SIGACT members on my blog in case you are not in SIGACT. He thinks you should be. I think so to so next year he won't ask me to do this. Here is his letter: here)

As many of you know there was a BREAKTHROUGH on the problem of the The Chromatic Number of The Plane. There have been fine blog posts on this by Gil Kalai here amd Scott Aaronson here. Rather than blog on it ourselves we have recruited and expert in the field, Alexander Soifer. He has written a book on the history and mathematics of coloring problems (see here for the amazon link to the book and here for my review of the book). The Chromatic Number of the Plane is his favorite problem. Much of the work on it is either by him or inspired by him. Much of the book is on it.

Alexander also is the editor of a journal on problems like this called GEOCOMBINATORICS (oddly enough. Geometric Combinatorics is a different field). See here for that journal- which I recommend!

He wrote an 8-page essay, which is a concise version of an essay that will appear in a Special Issue XXVIII (1) of Geocombinatorica (July 2018, 5-17),  dedicated to 5-chromatic unit distance graphs. The essay includes contributions from Aubrey D.N.J de Grey, Marijn J.H. Heule, and Geoffrey Exoo
and Dan Ismailescu.

What I find remarkable is that even though the result is new, the essay contains NEWER results. The modern world moves fast!

Without further ado, here is that essay: here.