A Few Interesting Computer Science Papers

Probabilistic Rank and Matrix Rigidity by Josh Alman and Ryan Williams

Leslie Valiant outlined an approach to proving circuit lower bounds from matrix rigidity. A matrix is rigid if you need to change many entries to significantly reduce the rank. Valiant showed that one could create a function with high algebraic circuit complexity from a rigid matrix. Of course one needs a rigid matrix and the Hadamard matrices (rows are Hadamard codes) seemed the perfect candidate. Alman and Williams say not so fast, in fact the Hadamard matrices are not that rigid and won't work for Valiant's program.

Ryoan: A Distributed Sandbox for Untrusted Computation on Secret Data by Tyler Hunt, Zhiting Zhu, Yuanzhong Xu, Simon Peter, and Emmett Witchel

You want to use Intuit's TurboTax to prepare your taxes but you don't want to actually let Intuit or their cloud provider to see your income sources. Sounds like a job for homomorphic encryption, a good solution in theory but not yet practical. Ryoan, an OSDI best paper awardee, takes a systems approach to the same problem, creating a computing sandbox where one can do secure computation without allowing the cloud or software provider access.

Google's Multilingual Neural Machine Translation System: Enabling Zero-Shot Translation (and related blog post) by Melvin Johnson, Mike Schuster, Quoc V. Le, Maxim Krikun, Yonghui Wu, Zhifeng Chen, Nikhil Thorat, Fernanda Viégas, Martin Wattenberg, Greg Corrado, Macduff Hughes and Jeffrey Dean

Google now using a single system to translate between different pairs of languages, even pairs of languages for which it has no examples. Their analysis shows a potential internal representation of the language and the beginning of a universal translator.

Music Theory for Theorists

I fully completed and passed my first MOOC, Fundamentals of Music Theory, a Coursera course out of the University of Edinburgh. I played the tuba in college and grad school but really just practiced scales and (usually) hit the notes. I didn't really understand keys, intervals, chords and the such and I wanted to learn.

Music theory has the same problem as C++, too much overloaded notation before you really understand what's going on. So here's a quick view of music theory without the mess.

Think (theoretically) of an bi-infinite sequence of notes. Every note is equivalent to notes a factor of twelve away from them (though in different octaves). Pick a note, label it 1, then the notes labelled 1, 3, 5, 6, 8, 10, 12, 1 (an octave higher) form a major scale in the key of note 1. There are twelve major scales, depending on which note you label 1. If you start at 10, i.e., 10, 12, 1, 3, 5, 6, 8, 10 you get the relative minor scale in the key of note 10. Also twelve minor scales.

Start a new major scale starting from 8 you'll get 8, 10, 12, 1, 3, 5, 7, 8, just one number off from the previous scale. Repeating this process will run through all the major scales. This is called the circle of fifths (since 8 is the fifth note of the scale). You can go through the circle backwards by starting at 6.

A chord is typically three or four alternating notes of a scale, for example 1, 5, 8 (the tonic) and 8, 12, 3, 6 (the dominant 7th). They can be inverted using different octaves and all sorts of other good stuff.

So notation wise, there is a mapping of {A,B,C,D,E,F,G} X {Flat, Natural, Sharp} to the twelve notes with several notes getting two different names in such a way that each note of any scale can get one of the letters in cyclic order. For example the D-Major scale would be the notes D-Natural, E-Natural, F-Sharp, G-Natural, A-Natural, B-Natural, C-Sharp and back to D-Natural. You put it all together in a diagram called a musical score.

Many undergrad computing courses now use Python instead of C++ to get around the notational challenges. Alas music notation goes back a millennium or so, I don't expect any changes soon.

Should I tell HS students that if they do well I'll write them a letter OR do I want them to ...

I teach a 3-week intense course for HS students on cryptography during the summer. Some of the students are very good, interested, and working hard. I also give out some extra credit assignments that some of them do.  For such students I am glad to write letters of rec for college. I want to reward them for working hard and being interested not knowing that they will get a letter for it.

These students don't quite know about colleges and letters and that stuff. I have two choices:

1) The first day tell them that if they do well I could write a letter for them.

PRO- this will encourage some of them to work harder

CON- I want them to work hard and BE interested (not just SHOW interest, though I doubt they are that good as actors) NOT because of some reward but because they really are interested. Contrast:

Bob showed an intense interest in computer science

to

Bob showed an intense interest in computer science but it may have been just for show to get this letter. Gee, I can't tell.

2) Don't tell them. This way when they work hard and show interest its more likely genuine.

PRO- as noted, their behavior is genuine

CON- They may not work as hard.

I tend to do (1) now- tell them. One thing, don't tell them too much and make it simple. I used to say that I would write a letter even for a B student if there were extenuating circumstances or if I could tell they really were good and just happened to blow an exam, or something like that. But this just invites more questions about what they need to get a letter, and I've never  had one of those cases where a B-student is better than he looks. (This could be because my exams are of the type where there is no time pressure as evidenced by half the students leaving about half way through. They are not easy, but they depend on knowledge not cleverness, so more time does not help. Or it could be something else about my teaching and grading.)

So- better to tell them about a letter option or not?

Computer Science Academic Hiring

My faculty recruiting season in 2016 never stopped. The spring recruiting season bled through summer right into various fall recruiting activities. How I envy my friends in other fields whose faculty recruiting season runs in less than three months.

Economist Noah Smith writes about the process he went through in the econ job market in 2012.

After applications go out, employers contact grad students for interviews. These interviews take place at the AEA's Annual Meeting in early January, which is a gigantic confab where most of the economists in the country go to eat free food and hobnob. As an interviewee, you generally don't have time to go to any of the presentations or speeches; you're running back and forth from hotel to hotel, going to interview after interview. This year's AEA Meeting was in Chicago. 

You then wait a week or two, and the employers who are interested in you call you back and schedule a flyout. Flyouts, which happen in February and March, involve going to the place, meeting the people, getting taken to dinner, and presenting your research. After that, offers go out.

Ahh to be done with recruiting before April Fools Day. Why can't we do this in Computer Science? In one word: Decentralization.

Academic fields act administratively like their field. So econ creates a structured market with the goal of an efficient (in their sense of the right people get the right jobs) outcome.

Computer science abhors centralized control. We lack a strong central authority and have very little coordination between different departments. So we have a process that takes a long time to work its way through and quite often fails to get that efficient outcome. Even the CRA's modest 2010 proposal for some common earlier deadlines went nowhere.

What can we do? I welcome suggestions and will give some of my own in a future post.

Did you do research when you were an undergrad? Well.. it was a different time.

Dan is a high school student who has worked with me and is now an ugrad at College Park

DAN: Bill, did you do research when you were in high school?

BILL: No, things were different then, there wasn't really a mechanism for it. Or, as you young people would say, it wasn't a thing.

DAN: When as an undergrad did you begin to do research?

BILL: Well, I never did research as an ugrad either.

DAN: Then how did you get into Harvard? Did they accidentally put your folder in the wrong pile?

BILL: Good question. I'll ask my adviser if he recalls what went wrong back in 1980.

DAN: Really? You'll ask him?

BILL: NO!

Okay, the real question here is:

At some point (before 1980) doing research at an ugrad in college was not really a thing many people did.

And now its quite common.

What changed? Is the change for the good? I'll phrase my thoughts and questions in the form of a question (the opposite of Jeopardy).

1) Are there more magnet schools and more ways to funnel students into research early?

2) Do computers allow students to to more research than they could have back before (say) 1980?

3) Is the phrase `HS research' a bit odd-  it is more learning then doing?

4) Is there a cycle going on- since more students are doing research, more have to do research to keep up in order to get into grad school? Is this even an issue for college admissions and/or scholarships?

5) Has the quality of research at HS science competitions increased ? Ugrad research? Grad student research? Prof research?

6) Does having HS or ugrads do research with you increase or decrease your productivity? (That depends on the students of course)

7) Do colleges give faculty kudos for guiding HS or ugrad research? (That depends on the school of course)

8) Are there more grants for ugrad research then before 1980? Are REU programs fairly new?

9) Does an ugrad now NEED to have done research to get into one of the top X grad schools? If so is this a good thing or not?  Does this hurt those without the oppurtunity  to do research? Do REU programs help alleviate this problem?

10) Are students entering grad school knowing far more than they used to?

11) Some magnet schools REQUIRE HS students to do research. Is this a good thing?

12) I've been using 1980 as a reference for no good reason- when did HS research and ugrad research increase? Was it gradual or was there some big increase over some X years where X is small?

Our Role and Responsibility

It's Trump but not just Trump. Brexit. Right-wing politicians gaining power in France, Netherlands, Austria and beyond. We worry about the future of our country and the whole world at large.

But what role have we played? By we I mean those of us who work in technology-related fields and have benefited the most from the new economy. 

There's a large population who's lives haven't gotten better. Not just the poor, we're talking the lower 80% of the economy. Our changing economy hasn't greatly improved the life of the middle class. 

Our technologies have put people out of jobs. We tell them our technology will create more and better jobs, our own version of trickle-down economics. They just need to learn what we have created, drive our Ubers, at least until the Ubers can drive themselves. 

We love working at universities where we can educate the very top students. But many don't get the opportunity to go to college at all. They are honest people willing to work hard and not seeing their lives improving. And we just call them "uneducated". 

We have learned how to mine data but often forget the people behind the data and get caught by surprise when things don't go the way we expected from the data.

We've created new communication channels. But we also control those channels. We often make the choices between usability, security, privacy, fairness, free speech and preventing hatred and discrimination. But who are we to make those choices. They have little say.

Who are they? They are us, fellow Americans. We need to make sure that all of us benefit from our changing world and everyone feels that they contribute to making it better and everyone has a say. Democracy, messy as it is, means that if people don't feel they the world looks out for them, they will find someone who promises change no matter the baggage they carry. And we need to listen or we end up with Donald Trump.

And the winner is... Harambe

Tomorow is the Election for Prez of the USA! This post is non-partisan but, in the interest of full disclosure, I state my politics: I will be voting for Hillary Clinton. I urge you to read the posts by Scott Aaronson: here and by Terry Tao here or John Oliver's segment here to see why. I would have thought that 99% of  their readers, and mine, are voting for Clinton, but looking at the comments on  Scott's an Terry's blog I realize that might not be true. (ADDED LATER- A nice article that summarizes the entire election, I put it here for you and for me: here)

However, I am not blogging about who you should vote for.

I had the teachers of Discrete Math and Algorithms (two diff courses)  give their students paper ballots with the four candidates on the Maryland ballot (Clinton, Trump, Johnson, Stein, write-in) and had them vote. But with a difference:

Discrete Math did the standard voting where you vote for ONE candidate

Algorithms did approval voting- where you mark all those you approve of.

DISCRETE MATH RESULTS: 428 students.
Clinton: 305
Trump: 44
Johnson:21
Stein:11:
Abstain (or some variant like `f**k all of them')-7
Sanders-6
Harambe. The Gorilla  who was shot (see here)-3
Hugh Mungus (word play - you figure it out. Also see here)-3
Ken Bone (he asked a good question at the Town Hall Debate. Then...)-2
Vermin Supreme (Policy: All Americans must brush their teeth. See here)-2
Joe Yecco (don't know who it is. Maybe a student in the class) -2

For the people who got 1 vote see here. There were 22 of these.

ALGORITHMS RESULTS. 251 students (won't add up since its approval voting)
Clinton-155
Johnson-63
Stein-59
Trump-40
Sanders-18
Abstain-14
Clyde Kruskal (who teaches the course)-13
Tom Reinhart (a CS lecturer at UMCP)-5
Larry Herman (a CS lecturer at UMCP)-3
John Kasich-3
Evan McMullen (Third Party Candidate who is doing well in Utah)-3 See here
Vernin Supreme (see above)-3
Harambe the Gorilla (really!) -2
Michelle Obama-2
Eric Sim (don't know who this is- Maybe a student in the class)-2

For people who got 1 vote see here

For more complete information see here

What to make of all of this?

College Students are largely Liberal so the pro-Clinton vote is not surprising. Also Maryland is a strongly democratic state, though I think being a college is more of a factor than being in Maryland. I suspect that students at UT Austin are also liberal even though the state isn't.

I've had large classes vote before, but not by approval voting. Both of the classes above had more  write-ins than usual- though that is less surprising for approval voting.

Approval voting shows that Trump is very few people's second choice. That is, those that don't like him REALLY don't like him. Again, this  is among the narrow demographic of college students taking Algorithms at UMCP CS.

Any odd candidate who gets ONE vote does not surprise me. If ONE person votes for Aliko Dangote, a real (see here) Nigerian Billionaire (he has NOT emailed you) that is not surprising.

If someone who is sort-of out there get TWO or more votes  (Vernin Supreme, Hugh Mungus) I am not surprised. Those two have websites and a following, though small.

The three votes for Harambe the Gorilla surprised me. I've looked on the web, and this is NOT a thing- there is no Harmabe for Prez websites, even as a joke (I assume if they existed they would be a joke). So I am surprised he got 3 votes in DM and 2 vote in Algorithms. One of those voted for Clinton, Johnson, Stein, and Harambe. I'm assuming that's a strong anti-trump vote.

Does this poll have any predictive value? The winner of the Discrete Math Poll ended up being the real winner in 1992, 1996 (though there were more Ross Perot Votes then I would have thought),
2008, and 2012. Note that in all these cases the democratic candidate won. Not a surprise.

Some  personal opinions:

1) If Trump loses what will the republicans learn from this. NOTHING since Trump was such an odd candidate. I wish it would have been Hillary (or someone like her) vs Cruz (or someone on the hard right) so that if they lose the reps can't say, as some have, we lost because we weren't conservative enough. And one can hope that Hillary vs Cruz would have more of a contest of ideas.

2) I'm not sure what would be better for the Rep Party- a Trump loss or a Trump win.

3) Predictwise says a Hillary win is around 85% likely. Nate (the only pollster known by his first name!) says 65%. If Hillary wins it won't be clear who was right? If Trump wins then Nate would have been more right, but not sure what that means. More generally:

If two people give different predictions, in the end you can see who was right

If two people give different probabilities of an event, then its harder to see who was right.

Do We Still Need Great Minds?

An anonymous comment on a recent post on alternate histories.

As far as science is concerned I don't believe that the great minds are needed anymore. They only speed things up that would later have been developed by an industry of a great mass of brilliant but more mediocre researchers. The best examples are Godel's and Turing's work which would have been done necessarily by the next generation of logicians or theoretical computer scientists. Regarding your own contributions it is fair to say that "the future doesn't need you." Anything important would also be created sooner or later by others, only some idiosyncratic work of minor importance could be left undone forever.

Depressing. So we do either mediocre work or work that others would later do anyway.

Of course we can never know. We can't tell if some great idea today may not have existed if a single genius didn't create it. We also don't know what technology we don't have because of someone who became a playwright instead of a scientist.

I don't doubt we'd have the P v NP question without Cook, Karp and Levin, though our understanding of the problem would have a very different flavor.

Take someone like Manuel Blum. Through him and his students we got formal models of cryptography that led to zero-knowledge proofs, interactive proofs, probabilistically checkable proofs, lower bounds on approximation and major advances in coding theory, among so much more. Would we have all this work if Manuel never existed? Maybe, eventually, but we'd live in a whole different theory world without him. And that world would always look different until we find a new Manuel to unify it.