## Thursday, April 20, 2017

### Will talk about Harry Lewis 70th bday conference later but for now- that was then/this is now

On Wed April 19 I was at the Harry Lewis 70th birthday celebration!
I will blog on that later.

Harry Lewis was my thesis adviser. Odd to use the past tense- I DID finish my thesis with him
and so he IS my adviser? Anyway, I will do a blog about the celebration next week.

This week I ponder- what was different then and now (I got my PhD in 1985).

False predictions that I made in 1985:

1) CS depts all have different views of what a CS major should know. By the year 2017 they will have figured out EVERY CS MAJOR SHOULD KNOW XXX and I will still write questions for the CS GRE. DID NOT HAPPEN. And a MINOR source of income for me has been cut off.

2) CS will be about 45% or more female. After all, the old guard is dying, its a new field without a tradition of sexism (this may have been false even then). Actually Women in CS has DECLINED since 1985. I'm still surprised since people in computing tend to be progressive. One could do several blog posts on this, but lacking the expertise I won't. (Gee bill- since when has lacking expertise stopped you before :-)

3) There will be some progress on P vs NP. Maybe an n^2 lower bound on SAT. Saying we've made NO progress is perhaps pessimistic, but we haven't made much.

4) in 2017 when Jet Blue emails me CLICK HERE TO PRINT YOUR BOARDING PASS' the previous night then it will always work, and if it doesn't then I can call them and after 9 minutes on hold (not too bad) be able to fix the problem. They were not able to, though at the airport they fixed it and got me onto the plane fast as compensation.

OTHER CHANGES

1) Theory was more centralized. STOC and FOCS were the only prestige conferences, and everyone went to them.

2) A grad student could get a PhD and only have 2 papers published and get a Tenure Track Job.

3) One could learn all that was known in complexity theory in about two years.

4) You didn't have to do ugrad research to get into grad school (I don't think you HAVE TO now either, but many more do it so I PREDICT in the future you'll have to. Though my other predictions were not correct so .... there's that)

5) Complexity was more based in Logic then Combinatorics.

6) Complexity theory was easier! Gee, when did it get so hard and use so much hard math!

7) It seemed feasible that P vs NP would be solved within twenty years. I've heard it said that the Graph Minor Theorem was when P lost its innocence- there were now problems in P that used VERY HARD math--- techniques that were hard to pin down and hence hard to show would not work.

8) The number of complexity classes was reasonable. (I don't count Sigma_i as an infinite number of classes)

9) Grad students were just beginning to NOT learn the Blum Speed Up Theorem. It would take a while before they began to NOT learn finite injury priority arguments in recursion theory. OH- speaking of which...

10) Computability theory was called recursion theory.

11) Some schools had this odd idea that in FRESHMAN programming one should teach proofs of program correctness.

12) Some schools (SUNY Stonybrook and Harvard were among them) did not have a discrete math course. Hence the course in automata theory spend some of its time teaching how to prove things. (Both schools now have such a course. For Maryland I don't recall- either it didn't have one and I invented it OR it did have one and I revamped it.)

13) No Web. You had to go to a library to copy papers on a copier (Ask your grandparents what a copier is)

14) Copying cost far less than printing.

15) Someone who looked good on paper for MATH but had no real CS background could get into Harvard Applied science department for grad school and get a degree in ... speaking of which

16) In 1980 Harvard did not have a CS dept. So my Masters degree is formally in Applied Math, though I don't recall solving partial diff equations or other things that one associates with applied math. Sometime when I was there CS became officially something so I got my PhD in CS. (My students are surprised to hear this-- they think I got my PhD in Math.)

17) Harry Lewis had a moustache and smoked a pipe.  He has shaved off one and gave up the other.

SO, what to make of this list? ONE THING- I DO NOT yearn for the good old days' That was then, this is now. I am GLAD about everything on the list EXCEPT two area where NOT ENOUGH change has happened- (a) I wish there was more diversity in CS, and (b) I wish Jet Blue had better software for boarding passes.

## Monday, April 17, 2017

### Understanding Machine Learning

Today Georgia Tech had the launch event for our new Machine Learning Center. A panel discussion talked about different challenges in machine learning across the whole university but one common theme emerged: Many machine learning algorithms seem to work very well but we don't know why. If you look at a neural net (basically a weighted circuit of threshold gates) trained for say voice recognition, it's very hard to understand why it makes the choices it makes. Obfuscation at its finest.

Why should we care? A few reasons:

• Trust: How do we know that the neural net is acting correctly? Beyond checking input/output pairs we can't do any other analysis. Different applications have a different level of trust. It's okay if Netflix makes a bad movie recommendation, but if a self-driving car makes a mistake...
• Fairness: Many examples abound of algorithms trained on data will learn intended or unintended biases in that data. If you don't understand the program how do figure out the biases?
• Security: If you use machine learning to monitor systems for security, you won't know what exploits still might exist, especially if your adversary is being adaptive. If you can understand the code you could spot and fix security leaks. Of course if the adversary had the code, they might find exploits.
• Cause and Effect: Right now at best you can check that a machine learning algorithm only correlates with the kind of output you desire. Understanding the code might help us understan the causality in the data, leading to better science and medicine.
What if P = NP? Would that help. Actually it would makes things worse. If you had a quick algorithm for NP-complete problems, you could use it to find the smallest possible circuit for say matching or traveling salesman but you would have no clue why that circuit works.

Sometimes I feel we put to much pressure on the machines. When we deal with humans, for example when we hire people, we have to trust them, assume they are fair, play by the rules without at all understanding their internal thinking mechanisms. And we're a long way from figuring out cause and effect in people.

## Thursday, April 13, 2017

### Alice and Bob and Pat and Vanna

"The only useful thing computer science has given us is Alice and Bob" - A physicist at a 1999 quantum computing workshop
Alice and Bob, great holders of secrets, seemed to pop into every cryptography talk and now you see them referenced anytime you have two parties who have something to share. Someone at Dagstuhl a few weeks back asked who first used Alice and Bob. What a great idea for a blog post, and I decided to do some binary searching through research papers to find that elusive first Alice and Bob paper. Turns out Wikipedia beat me to it, giving credit to Rivest, Shamir and Adleman in their paper A method for obtaining digital signatures and public-key cryptosystems, the paper that won them the Turing Award.

In grad school attending a square dance convention we ran into a married couple Alice and Bob and they couldn't figure out why we were laughing. Yes, I square danced in grad school, get over it.

The Wikipedia page lists a number of other common names used in protocols including perennial third wheel Charlie and nosy eavesdropper Eve. I can claim credit for two of those names, Pat and Vanna. In my first conference talk in 1987 I had to explain interactive proofs and for the prover and verifier I picked Pat and Vanna after the hosts, Pat Sajak and Vanna White, of the popular game show Wheel of Fortune. Vanna didn't trust Pat and spun the wheel to get random questions to challenge him. Half of the audience laughed hysterically, the other half had no clue what I was talking about. I heard the FOCS PC took a break by watching an episode of Wheel of Fortune to understand the joke.

Howard Karloff insisted we use Pat and Vanna in the LFKN paper. Pat and Vanna have since retired from interactive proving but thirty years later they still host Wheel of Fortune.

## Monday, April 10, 2017

### What is William Rowan Hamilton know for- for us? for everyone else?

I found the song William Rowan Hamilton that I used in my April fools day post because I was working on a song about Hamiltonian Circuits to the tune of Alexander Hamilton

Circuit Hamiltonian

I want a Circuit Hamiltonian

And I'm run-ing a pro-GRAM for it

So  I wait, so I wait

(Darling said: Don't quit your day job.)

I noticed that William Rowan Hamilton had the same cadence as Alexander Hamilton so I assumed that someone must have used that for a parody, and I was right

But

Listen to the son. They mention the following::

Kinetics, Quaternions (This is mentioned the most), An optimization view of light,  Minimal action,
your energy function generates the flow of time' ,Operators that Lie Commute with the symbol that bears your name, His versors(?) formed hyperspheres - see if you can plot 'em- invented vectors and scalars for when you dot 'em (Did he really invent vectors? Wikipedia says that in a sense he invented cross and dot products.) And Schrodinger sings that he adapted Hamilton's work for Quantum (I didn't know Schrodinger could sing!).

What do they NOT mention: Hamiltonian paths or circuits. His Wikipedia page does mention Hamiltonian circuits, but not much and you would have no idea they were important.

When a computer science theorists hears Hamiltonian' she prob thinks path' or circuit' and not an optimization view of light' or anything else in physics'  She might think of Quaternions and if she does Quantum Computing she may very well think of some of the items above. But these are exception. She would likely think of the graph problems.

The rest of the world would think of the list above (or would think William Rowan Hamilton died in a dual over Quaternions and later had the best Hamilton Satire written about him- the second of course being the one about Batman,)

In his own time he was best know for Physics. Maybe also  quaternions. I think Hamilton himself would be surprised that this problem became important. So here is my question:

When did the problem become important? Before NP-Completness or after?

Is he still better known for his physics and quats- I think yes.

When I say Hamilton' what comes to YOUR mind?

## Thursday, April 06, 2017

### A Bridge Too Far

In Atlanta last week a fire destroyed a major highway bridge right on my, and so many other's, commutes. I've been playing with different strategies, like coming in later or even working at home when I can, not so easy when a department chair. I expect at Georgia Tech, just South of the damaged highway, we'll see less people around for the next ten weeks or so.

Even before the bridge collapse faculty don't all come in every day. In the Chronicle last month Deborah Fitzgerald laments the empty hallways she sees in her department. Hallways became a victim of technology, particularly the Internet. We mostly communicate electronically, can access our files and academic papers on our laptops and iPads just as easily in a coffeehouse as in our office. If you use your mobile phone as your primary number the person calling you won't even know if you are in the office. The only reason to come into the office is to teach or to meet other people.

Of course meeting other people is a very good reason. Not only scheduled meeting with students but the random meeting with another colleague that turns into a research project. The times I've walked into a student's office with a crazy idea, or needed a combinatorial theorem from one of the local experts. As we even move our meetings to video conferences, we really start to lose those spontaneous connections that come from random conversations. Soon the technology may get so good that our online meetings and courses will become a better experience than meeting in person. What will happen to the universities then?

## Tuesday, April 04, 2017

### Proving Langs not Regular using Comm Complexity

(My notes on this are at my course website: here They are notes for my ugrad students so they may be longer and more detailed than you want.)

While Teaching Regular langauges in the Formal Languages course I realized

Using that  { (x,y) : x=y, both of length n}  has Communication Complexity \ge n+1 one can easily prove:

a) The Language \{ xx : x\in \Sigma^*} is NOT regular

b) For all n the language \{ xx : x \in \Sigma^n }, which is regular, requires a DFA on 2^{n+1} states.

I also used Comm Complexity to show that

{ w : the number of a's in w is a square}  is not regular, from which one can get

{ a^{n^2} : n\in N} is not regular.

More generally, if A is any set such that there are arb large gaps in A, the set

{ w : the number of a's in w is in A} and {a^n : n \in A} are not regular.

This approach HAS TO BE KNOWN and in fact it IS- Ian Glaister and Jeffrey Shallit had a paper in 1996 that gave lower bounds on the size of NFA's using ideas from Comm Complexity (see here). They present  their technique as a way to get  lower bounds on the size of NFA's; however, their techniques  can easily be adapted to get all of the results I have, with similar proofs to what I have.
(Jeffrey Shallit, in the comments,  pointed me to an article that predates him that had similar ideas:here.)
(Added later- another early  referene on applying comm comp to proving langs not regular is Communication Complexity. Advances in Computers Vol 44 Pages 331-360 (1997),
section 3.1, by Eyal Kushlevitz. (See here)

Next time you teach Automata theory you may want to teach showing langs are NOT regular using Comm Complexity. Its a nice technique that also leads to lower bounds on the number of states for DFA's and NFA's.

## Saturday, April 01, 2017

### William Rowan Hamilton- The Musical!

With the success of Hamilton,the musical on broadway (for all of the songs and the lyrics to them see here- I wonder who would buy the CD since its here for free)  Lin-Manuel Miranda looked around for other famous figures he could make a musical about. Per chance I know Lin's college roommates father and I suggested to him, more as a joke, that Lin-Manuel could make a musical about

William Rowan Hamilton