So Was I

While Bill marched at the main March for Science in DC, I marched at the satellite march in Atlanta, my daughter Molly in Chicago, Scott Aaronson in Austin, Hal Gabow in New York, and Donald Knuth (pictured) presumably in San Francisco. I thank the many of you who participated in your local march. Science appreciates the support.

Most of the marchers I saw did not come from the ranks of academia or professional scientists. Rather people from all walks of life who believe in the important role science and scientists have in shaping our future. Parents dragged their kids. Kids dragged their parents.

There have been some worry about politicizing science and whether the march would be a bad idea. The march won't have much effect on policy positively or negatively. But we mustn't forget that scientists need to deal with politics, as long as the government continues its missions of funding science and using proper science to help guide policies that require understanding of the world.

If there's one positive sign of a Trump presidency, as Molly explained to me, it's inspiring a generation. We would not have had a March for Science if Trump wasn't president, but what an wonderful movement and we should march every year around Earth Day no matter who sits in the oval office.

I was at the March for Science on Saturday

(Will blog on Harry Lewis's 70th Bday next week-- Today's post is more time sensitive.)

I was on the March for Science on April 22. Here are some Kolmogorov random comments

1) Why should I go to it? One less person there would not have matters. AH- but if they all think that then nobody goes. The Classic Voting Paradox- why vote if the chance that your vote matters is so small (even less so in my state- Maryland is one of the Bluest States).  In the case of the March For Science there is another factor- since I live in Maryland I really CAN go at minimal effort. Most of the readers of this blog cannot (Though there were some other marches in other cities. Scott was at a March in Austin Texas.)

2) One of the speakers said something like `and the fact that you are all here in the rain shows how much you believe in our cause!'  While the rain might have made our being there more impressive, I wish it had been better weather.

3) Here are some of the Signs I saw:

What do we Want!
Empirical  Based Science!
When do we Want it!
After Peer Review!

Trump- where's your PhD? Trump University?
(This one is not fair- most presidents have not been scientists and have funded science. Trump himself not have a PhD  is not relevant here.)

A sign had in a circle:  pi, sqrt(2) and Trump and said: These are all irrational.

A 6-year old had a sign: Light travels faster than sound which is why Trump looks bright until he talks (I think her mother, who was there, made it for her).

Science is the Solution (with a picture of a chemical Flask)

If you are not part of the solution you are part of the precipitate

Truth is sometimes inconvenient.

So severe even the nerds are here

I can't believe I'm marching for facts!

There is no planet B (this refers to if Global Warming kills the planet we can't go elsewhere- a play off of `Plan B')

I'm with her (pointing to the earth) (The person with this sign told me she used the same sign for the Women's  March- so recycling!)

Science has no borders

Science doesn't care what you think.

Its not Rocket Science- well, some of it is.

4) The March For Science was the same day as Earth Day and many of the talks mentioned global warming and pollution. Many of the talks mentioned the contributions of women and minorities. One of the speakers was transgender .Hence the March had a liberal slant. BUT- if believing in Global Warming and wanting to open science up to all people (e.g., women and minorities) are Liberal positions, this speaks very badly of conservatives. First ACCEPT that Global Warming is TRUE- then one can debate what to do about it--and that debate could be a constructive political debate.  One talk was about Indigenous Science-- I can't tell if its a healthy alternative  view or ... not.

A more telling point about the march having a liberal slant is the OMISSION of the following topics:

Technology has

(a) helped Oil people extract more oil, and fracking to be cost effective

(b) GMO's  have helped feed the world and have had no ill effects (I think anti-GMO in America is a fringe view-- I don't know of any elected democrat who is anti-GMO, though I could be wrong. I think its a more mainstream view in Europe.)

(c)  make the weapons that keep us safe (that's a positive spin on it)

(d) DNA used to prove people GUILTY (they did mention DNA used to prove people INNOCENT).

So the March LOOKED like it was a bunch of Liberal Scientists. Does this make it less effective and easy for Trump and others to dismiss? Or are we so far past any hope of intelligent conversation that it doesn't matter?


5) Many of the machers, including Darling and me,  had lunch at the Ronald Reagan Center. Is this an IRONY?

NO: Reagan funded the NSF as well as other presidents, see this blog post of Lance's from 2004. That post is interesting for other reasons: at the time Dems and Reps seemed to both RESPECT science. Trump may be the first one not to- though its early in his term so we'll see how it all pans out. Second, Lance has been blogging for a LONG time! (since 2003, and me since 2007).

YES: See these quotes by the Gipper (ask your grandparents why Reagan is called that):here

6) Will it have any effect? Short term I doubt it, Long term probably yes. An article about the impact of the the Women's March: here

7) There have been Women's Marches, The Million Man March, Civil Rights Marchs, pro-life, pro-choice, anti-war, pro-gay, anti-gay marches before. Has there ever been a March for Science before? Has there ever been a need before? I don't think so but I am asking non-rhetorically.

Cutting EPA because you don't believe in Global warming is appalling, (see here) but I understand politically where that comes from.

Not allowing funding of gun violence because you are pro-gun is appalling, (see here) but I understand politically where that comes from.

IF they cut funding on the study of evolution (Have republican presidents done that?) then that would be appalling but I would understand politically where it came from.

But cutting the NIH (see here) or the NSF (has he done that yet or is he just thinking of doing that?) I really DON"T understand- It does not even fit into the Republican Philosophy.

There should NOT be a NEED for a MARCH FOR SCIENCE, Or, to quote one of the signs

I can't believe I"m marching for facts!

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.

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.

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.

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?

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?

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. 

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

Well, Lin-Manuel heard about this and noticed that

William Rowan Hamilton

has the exact same number of syllabus as

Alexander Hamilton.

Hence some of the songs would be able to have the same cadence.  He has gone ahead with the project! He has asked that I beta test the first song by posting it, so I will:

William Rowan Hamilton

Lin-Manuel will be reading the comments to this blog- so please leave constructive comments about the song and the idea.