We had an incredible year for theorems in 2015, the strongest year in computational complexity in the last decade. Topping the list as the theorem of the year is László Babai's quasipolynomial-time algorithm for graph isomorphism. A little risky because nobody, including Babai himself, has fully verified the proof but given Babai's reputation and the warm reception of his lectures, I have little doubt it will all work out. Again I strongly recommend watching the video of Babai's first lecture. Not only is Babai a great researcher but he's an excellent speaker as well. For the those up to the challenge, the paper is now available as well.
Beyond Babai's result we had a great year including random oracles separating the polynomial-time hierarchy, the (3+1/86)n size lower bound for general circuits, Terry Tao's solution to the Erdős discrepancy problem, explicit constructions of Ramsey Graphs and new bounds on threshold circuits.
We celebrated 50 years of computational complexity and Moore's law, the centenary of Hamming and the bicentenaries of Ada Lovelace and George Boole, the latter giving us the Boolean algebra. In 2016 we will celebrate the centenary of the person who used those bits to describe information.
We thank our guest posters Dylan McKay and Thomas Zeume. Dylan's metric group problem is still open if anyone wants to try and crack it.
In 2015 we continue to see CS departments struggle to meet the demand of students and industry. US universities faced many difficult challenges including dealing with race relations, freedom of speech and safety issues. Too much tragedy in the US and abroad, and a far too divisive political campaign. Here's hoping for reason to prevail in 2016.
We remember Gene Amdahl, Alberto Apostolico, Barry Cooper, George Cox, Jiří Matoušek, John Nash, Leonard Nimoy, Hartley Rogers Jr., Donald Rose, Karsten Schwan and Joe Traub.
Wishing everyone a Happy New Year and a successful 2016.
Monday, December 28, 2015
Tuesday, December 22, 2015
Guns and Crypto
“We believe it would be wrong to weaken security for hundreds of millions of law-abiding customers so that it will also be weaker for the very few who pose a threat,” said a spokesperson from Smith & Wesson on the recent calls for increased gun control.
The quote was actually from Apple on a proposed British law that would require the company to devise methods to break into iPhone communications.
In the wake of Paris and San Bernardino we've heard calls for controls on both guns and cryptography with eerily similar arguments coming from defenders. If we ban guns/crypto then only bad people will have guns/crypto. Any attempts to limit guns/crypto is a slippery slope that takes away our constitutional rights and our freedoms.
I don't have a gun but I do use encryption, built into the iPhone and the various apps and browsers I use to communicate. Fat lot of good it does me as hackers stole my personal information because I shopped at Home Depot and Target. Because my health insurance runs through Anthem. Because I voted in the State of Georgia.
I am a strong believer in individual rights, a person should be able to use cryptography to protect their communications and a gun, if they wish, to protect their family. But I do see the value in gaining access in communications to stop a terrorist as well as making it harder for them to get the weapons to carry out their acts. Why can't the fingerprint technology that unlocks my iPhone also unlock a gun? The gun/crypto advocates don't trust to government to implement any restrictions reasonably and thus fight any changes.
No laws can completely eliminate or even restrict guns or crypto but they can make it harder to use. The challenges aren't technological, we can create guns or crypto protocols that perform as we want them to perform. The challenges are social, finding the right balance between rights and security and governments we can trust to enforce that balance.
The quote was actually from Apple on a proposed British law that would require the company to devise methods to break into iPhone communications.
In the wake of Paris and San Bernardino we've heard calls for controls on both guns and cryptography with eerily similar arguments coming from defenders. If we ban guns/crypto then only bad people will have guns/crypto. Any attempts to limit guns/crypto is a slippery slope that takes away our constitutional rights and our freedoms.
I don't have a gun but I do use encryption, built into the iPhone and the various apps and browsers I use to communicate. Fat lot of good it does me as hackers stole my personal information because I shopped at Home Depot and Target. Because my health insurance runs through Anthem. Because I voted in the State of Georgia.
I am a strong believer in individual rights, a person should be able to use cryptography to protect their communications and a gun, if they wish, to protect their family. But I do see the value in gaining access in communications to stop a terrorist as well as making it harder for them to get the weapons to carry out their acts. Why can't the fingerprint technology that unlocks my iPhone also unlock a gun? The gun/crypto advocates don't trust to government to implement any restrictions reasonably and thus fight any changes.
No laws can completely eliminate or even restrict guns or crypto but they can make it harder to use. The challenges aren't technological, we can create guns or crypto protocols that perform as we want them to perform. The challenges are social, finding the right balance between rights and security and governments we can trust to enforce that balance.
Monday, December 21, 2015
Blog Followers
If you follow this or any other Blogger-based blog via a non-Google account, you'll need to follow with a Google account instead. Details.
Wednesday, December 16, 2015
Simons and Berkeley
The Simons Institute for the Theory of Computing in Berkeley held two programs this fall, Fine-Grained Complexity and Algorithm Design and Economics and Computation both ending this week. It would have been a great fall for me to spend there as I have strong connections in both groups, but as a department chair and father to a high-school senior it would have been impossible to be away from Atlanta for an extended period of time.
But I did manage some short trips, my first to Simons. In September I went to attend the workshop on Connections Between Algorithm Design and Complexity Theory but had to leave early and to make up for it I visited for a few days last week as well. The Simons Institute has taken over Calvin Lab, a circular building on the UC Berkeley campus. Lecture rooms on the first floor, wide-open working spaces on the second floor where most people congregate and visitor offices on the third floor. It's not just the space but an incredible group of complexity theorists and EC types there this fall.
The year marks thirty years since I spent that not-so-happy year of grad school in Berkeley. The city of Berkeley has mellowed a bit. When I lived there before, many recent graduates didn't leave and instead remained in their cheap rent-controlled apartments. Now you see almost a bimodal distribution centered around college-aged students and late middle-aged residents. Berkeley housing is getting hard to find again, this time because of overflow from limited affordable housing in San Francisco. Still Berkeley seems like a city that has never grown up. I guess people like it that way.
But I did manage some short trips, my first to Simons. In September I went to attend the workshop on Connections Between Algorithm Design and Complexity Theory but had to leave early and to make up for it I visited for a few days last week as well. The Simons Institute has taken over Calvin Lab, a circular building on the UC Berkeley campus. Lecture rooms on the first floor, wide-open working spaces on the second floor where most people congregate and visitor offices on the third floor. It's not just the space but an incredible group of complexity theorists and EC types there this fall.
The year marks thirty years since I spent that not-so-happy year of grad school in Berkeley. The city of Berkeley has mellowed a bit. When I lived there before, many recent graduates didn't leave and instead remained in their cheap rent-controlled apartments. Now you see almost a bimodal distribution centered around college-aged students and late middle-aged residents. Berkeley housing is getting hard to find again, this time because of overflow from limited affordable housing in San Francisco. Still Berkeley seems like a city that has never grown up. I guess people like it that way.
Thursday, December 10, 2015
Ada Lovelace (1815-1852)
Ada, daughter of the poet Lord Byron, showed an early talent in mathematics. At age 17 she became a friend of Charles Babbage, inventor of the difference engine and proposed a more complex analytic engine. Babbage gave a talk at the University of Turin and Ada had the task of translating an article written by Italian engineer Luigi Menabrea based on the talk. Ada did more than just translate, she added her own thoughts which included a program that could be run on the analytic engine computing a specific sequence of numbers. The analytic engine never got built and Ada never saw her program run but nevertheless she gets credit as the first computer programmer and most notably in 1980 the US Department of Defense named their preferred computer language "Ada" in her honor.
Here's to Lady Ada Lovelace, born way too far ahead of her time.
Monday, December 07, 2015
crank math and crank people
In the same week I got email claming:
1) Babai had shown that GI is in quasipoly time.
2) Opeyemi Enoch, a Nigerian Mathematician, solved the Riemann hypothesis.
I believe Babai's claim since (a) he's worked on the problem a lot and is a known expert, (b) the result is believable, and (c) the math we know now seem up to the task.
I do not believe Enoch's claim. It would be unfair for me to not believe it because I never heard of him. However, my sources in math say that RH is not in a position to be solved. Also, articles I've read on the web including this article seem to say things that cast doubts on it such as this quote:
motivation to solve the problem came from his students, who brought it to him with the hope of making 1 million ``off the internet''
Bobby Jindall (who?) dropped out of the Prez race (why am I bringing this up? Is he working on RH?) Bobby Jindall was a Rhodes Scholar. (why am I bringing this up? Wait and see.)
In 2003 I was in a Taxi (ask your grandparents what Taxi's were before we had Uber) and the driver began telling me lots of conspiracies--- there is no Gold in Fort Knx, the novel Goldfinger was Ian Flemmings attempt to tell us this, Reagan was shot because he knew this, and the American Presidency is controlled by a secret cabal. I pointed out that if that's the case how did George Bush Sr (clearly a member of the Cabal) lose to Bill Clinton. His answer: Bill Clinton was a Rhodes Scholar and the Cabal is controlled by Rhode Scholars.
Its hard to argue with a conspiracy theorist about the past. But you can challenge him to predict the future. So I told him ``if you can predict who will be the Democratic Nominee for Prez in 2004 then I will look at your website and take it seriously. If not, then not'' He smiled and just said ``Wesley Clark was a Rhodes scholar'' If I had asked him who would be the republican nominee in 2016 then he might have said ``Bobby Jindal is a Rhodes Scholar''
The way to expose conspiracy theorists, astrologers, and The National Inquirer is to take their predictions seriously and test them. I wonder why anyone believes these things given their track record.
Judging math things is different- A math paper can be read and should stand on its own.
Thursday, December 03, 2015
Moonshots
In 1961 Kennedy said "this nation should commit itself to achieving the goal, before this decade is out, of landing a man on the Moon and returning him safely to the Earth". In 1969 Neil Armstrong and Buzz Aldrin walked on the moon and returned to earth safely. In the 46 years hence man has gone no further.
Bill Gates founded Microsoft to place "a computer on every desk and in every home". Once he succeeded, Microsoft lost its way. Their current mission takes a different tact "Empower every person and every organization on the planet to achieve more."
In my life I've seen many a moonshot succeed, from a computer chess program that can beat the best humans, the classification of finite simple groups and the proof of Fermat's last theorem. They all seem to end up with a "Now what?". If you have a finite mission, you can only achieve finite things. We often think of moonshots as an amazing challenge but they serve as limits as well.
In computing we have a law that has become a mission, that the power of computing doubles roughly every two years. These improvements have enabled the incredible advances in learning, automation and connectivity that we see today. We keep making better computers because we don't have a limit just a goal of getting better than where we are today.
When I first started writing grant proposals, a senior faculty member chided me for saying "the ultimate goal of computational complexity is prove P ≠ NP". He said that would kill any grant proposals after we did settle the question. While we are in no danger of solving this problem in the near future, eventually we will and I'd hate to see the field whither afterwards.
My favorite mission comes from Star Trek, particularly the TNG version with "Its continuing mission: to explore strange new worlds, to seek out new life and new civilizations, to boldly go where no one has gone before."
Bill Gates founded Microsoft to place "a computer on every desk and in every home". Once he succeeded, Microsoft lost its way. Their current mission takes a different tact "Empower every person and every organization on the planet to achieve more."
In my life I've seen many a moonshot succeed, from a computer chess program that can beat the best humans, the classification of finite simple groups and the proof of Fermat's last theorem. They all seem to end up with a "Now what?". If you have a finite mission, you can only achieve finite things. We often think of moonshots as an amazing challenge but they serve as limits as well.
In computing we have a law that has become a mission, that the power of computing doubles roughly every two years. These improvements have enabled the incredible advances in learning, automation and connectivity that we see today. We keep making better computers because we don't have a limit just a goal of getting better than where we are today.
When I first started writing grant proposals, a senior faculty member chided me for saying "the ultimate goal of computational complexity is prove P ≠ NP". He said that would kill any grant proposals after we did settle the question. While we are in no danger of solving this problem in the near future, eventually we will and I'd hate to see the field whither afterwards.
My favorite mission comes from Star Trek, particularly the TNG version with "Its continuing mission: to explore strange new worlds, to seek out new life and new civilizations, to boldly go where no one has gone before."