Skip to content
tags: ,

More computer scientists are elected to the academy

Dan Mote, the President of the National Academy of Engineering (NAE), just announced this year’s class of members elected to the NAE.

I am thrilled to see that several computer scientists were among the class.

Actually in putting together the list below of computer members I had some difficulty. If I made an error I apologize in advance. One of the interesting results of looking at the whole list of 80 members is that computing played a major role in many member’s citations. Yet for many of these I would not classify them as computer scientists. This is just another example of the importance of computing in all of engineering. So if I left out someone from what I considered another area, well I am sorry.

Congratulations to all on your election.

## The New Members

Here are the new members, along with their citations. The NAE likes pithy citations that start with the word “For.”

• Anderson, Thomas, University of Washington, Seattle. For contributions to the design of resilient and efficient distributed computer systems.

• Boneh, Dan, Stanford University, Stanford, Calif. For contributions to the theory and practice of cryptography and computer security.
• Chang, Frederick, Southern Methodist University, Dallas. For leadership in cybersecurity research in the intelligence community and advancing the importance of cybersecurity science in academia.
• Cornuéjols, Gérard, Carnegie Mellon University, Pittsburgh. For contributions to the theory, practice, and application of integer programming.
• Greenberg, Albert, Microsoft Corp., Redmond, Wash. For contributions to the theory and practice of operating large carrier and data center networks.
• Hinton, Geoffrey, Google Inc., Toronto (foreign member). For contributions to the theory and practice of artificial neural networks and their application to speech recognition and computer vision.
• Jain, Anil, Michigan State University, East Lansing. For contributions to the engineering and practice of biometrics.
• Johnson, David, Columbia University, New York City. For contributions to the theory and practice of optimization and approximation algorithms.
• Leiserson, Charles, Massachusetts Institute of Technology, Cambridge. For theoretically grounded approaches to digital design and parallel computer systems.
• Lindsay, Bruce, IBM Almaden Research Center, San Jose, Calif. For the design and implementation of high-performance distributed and extensible database systems.

## Some Comments

I cannot resist to say that I have a personal connection to both Boneh and Leiserson. I was honored to be the graduate advisor of Dan and the undergraduate advisor to Charles: the former at Princeton and the latter at Yale. Both were a delight to work with, and I am very excited that they are now in the academy.

I also noticed that areas that were selected for recognition were concentrated into three. Security was covered several times; large scale systems of several kinds was also; and theory was key for two new members.

Ken points out that all ten precede me in the alphabet—indeed they run snugly up to “Lip—.” As a member I voted but had no effect there.

## Open Problems

The main issue that confronts computer science is to get more members into the NAE. Many deserving researchers are not yet members and I hope that will be solved in the future. But for today let’s congratulate all those who did get into the NAE this year.

Ken: We are leaving yesterday’s post “unrolled” on the front page since this comes so soon after. To keep it short we elided material on deep learning and big data including this interview that would have brought “engineering” into the “science” versus “magic” issue.

Can we avoid accepting what we cannot verify?

 Cropped from biography source

Arthur Clarke was a British writer of great breadth and huge impact. He was a science writer, of both fiction and non-fiction. His works are too many to list, but 2001: A Space Odyssey—the novel accompanying the movie—is perhaps his most famous. He received both a British knighthood and the rarer Pride of Sri Lanka award, so that both “Sri” and “Sir” were legally prefixed to his name.

Today Dick and I want to raise questions about modern cryptography, complexity, and distinguishing science from “magic.”

Clarke added the following widely quoted statement to the 1973 revised edition of his book Profiles of the Future: An Inquiry into the Limits of the Possible as the third of three “laws” of prediction:

Any sufficiently advanced technology is indistinguishable from magic.

When I, Ken, first read the quote, I was surprised: it didn’t seem like something a proponent of science would say. Tracing versions of his book’s first chapter in which the first two “laws” appear, it seems Clarke first had nuclear fission in mind, then transistors, semiconductors, clocks incorporating relativity, and a list that strikingly includes “detecting invisible planets.” I agree with critiques expressed here and here: these phenomena are explainable. Perhaps Richard Feynman was right that “nobody really understands quantum mechanics,” but besides rebuttals like this, the point is that a natural explanation can satisfy by reduction to simpler principles without their needing to be fully understood. In all these cases too, experiment gives the power to verify.

My newfound appreciation for Clarke’s quip, and Dick’s all along, comes from realizing the potential limits of verification and explanation in our own field, computational complexity. This applies especially to crypto. Let’s see what the issues are.

## Checking Results

As often in computing, issues have “ground” and “meta” levels. Let’s start on the ground.

The big center of gravity in complexity theory has always been the idea of ${\mathsf{NP}}$. The idea is that although it may take a lot of effort to find a solution to a problem in ${\mathsf{NP}}$ but if and when you find one, it is easy to check. Separate from whether ${\mathsf{P = NP}}$, there was much success on programs whose outputs are checkable with markedly greater efficiency than the original computation. This gives not only instant assurance but usually also an explanation of why the solution works.

An even lower example in complexity terms is verifying a product ${C = AB}$ of ${n \times n}$ matrices. Although we may never be able to multiply ${AB}$ in ${O(n^2)}$ time, once we have ${C}$ we can verify in ${O(n^2)}$ time by randomly choosing ${n}$-vectors ${x,y}$ and checking that ${xCy}$ equals ${xA}$ times ${By}$. Here the randomized check may give less explanation, but the ability to repeat it quickly confers assurance. We should mention that this idea originated with Rūsiņš Freivalds, who passed away last month—see this tribute by his student Andris Ambainis.

As the field has matured, however, we’ve run into more cases where no one has found a verifying predicate. For example, every finite field ${F = F_{p^n}}$ has elements ${g}$ whose powers ${g^i}$ generate all the non-zero elements of ${F}$. However, no way is known to recognize them in time polynomial in ${n\log p,}$ let alone find one. The best recent news we know is a 2013 paper by Ming-Deh Huang and Anand Narayanan that finds one in time polynomial in ${pn}$ which is fine when ${p}$ is small. In other things too, we seem to be moving away from ${\mathsf{NP}}$ to non-checkable complexity classes.

## Learning and Explaining

To see a still broader form of not knowing, we note this remark by Lance Fortnow on the Computational Complexity blog about a ramification of the deep-learning technique used to craft the new powerful Go-playing program by Google:

“If a computer chess program makes a surprising move, good or bad, one can work through the code and figure out why the program made that particular move. If AlphaGo makes a surprising move, we’ll have no clue why.”

To say a little more here: Today’s best chess programs train the coefficients of their position-evaluation functions by playing games against themselves. For example, the Weights array for last year’s official Stockfish 6 release had five pairs:

$\displaystyle \{289, 344\},\;\;\{233, 201\},\;\;\{221, 273\},\;\;\{46, 0\},\;\;\{321, 0\}.$

Line 115 of the current Stockfish source file evaluate.cpp has four pairs:

$\displaystyle \{214, 203\},\;\;\{193, 262\},\;\;\{47, 0\},\;\;\{330, 0\}.$

(Update 2/11/16: the array was removed entirely—see this change note.)

The myriad Score numbers following it are likewise all different. They are mysterious but they are concretely present, and one can find the position-features they index in the code to compute why the program preferred certain target positions in its search. A case of why Deep Blue played a critical good move against Garry Kasparov in 1997 caused controversy when IBM refused Kasparov’s request for verifying data, and may still not be fully resolved. But I’ve posted here a similar example of tracing the Komodo program’s refusal to win a pawn, when analyzing the first-ever recorded chess game played in the year 1475.

Deep learning, however, produces a convolutional neural network that may not so easily reveal its weights and thresholds, nor how it has learned to “chunk” the gridded input. At least with the classic case of distinguishing pictures of cats from dogs, one can more easily point after-the-fact to which visual features were isolated and made important by the classifier. For Go, however, it seems there has not emerged a way to explain the new program’s decisions beyond the top-level mixing of criteria shown by Figure 5 of the AlphaGo paper. Absent a human-intelligible explanation, the winning moves appear as if by magic.

## Crypto and Illusion

James Massey, known among many things for the shift-register deducing algorithm with Elwyn Berlekamp, once recorded a much-viewed lecture titled,

“Cryptography: Science or Magic?”

What Massey meant by “magic” is different from Clarke. In virtually all cases, modern cryptographic primitives rely on the intractability of problems that belong to the realm of ${\mathsf{NP}}$ or at worst ${\mathsf{\#P}}$. The widespread implementation of public-key cryptography and digital signatures via RSA relies on factoring which belongs to ${\mathsf{NP \cap co}\text{-}\mathsf{NP}}$. Even if we knew ${\mathsf{NP \neq P}}$, we still wouldn’t have a proof of the security needed to establish that the world really confers the capabilities promised by these primitives.

As above the issue is lack of ability to verify a property, but this time of an algorithmic protocol rather than a single solution or chess or Go move. This “meta” level goes to the heart of our field’s aspiration to be a science. Of course we can prove theorems conditioned on hardness assumptions, but apart from the issue we have covered quite a few times before of loopholes between security proofs and application needs, we perceive a more fundamental lack:

The theorems don’t (yet) explain from first principles what it is about the world that yields these properties.

Modern cryptography is filled with papers that really say the following: If certain simple to state complexity hardness assumptions are correct, then we can do the following “magical” operations. This is viewed by those who work in cryptography, and by those of us outside the area, as an example of a wonderful success story. That factoring is hard implies the ability to encrypt messages is not so hard to believe, but that we can make the encryption asymmetric—a public key system—was at first a real surprise. But that this assumption further allows us to do some very powerful and wonderful operations is even more surprising.

Massey gives as example the technique developed by Amos Fiat and Adi Shamir to convert any interactive proof of knowledge into one that carries the signature of the person conveying proof of knowledge without needing that person’s active participation. It preserves the feature that only the person’s fact of knowing is transmitted, not the known data itself. This is truly wondrous: you can interact offline.

We can trace the composition of hardness assumptions, plus the assumption of implementing a suitable random oracle, in a conditional theorem. Since we cannot prove any of the conditions, Massey asks, is this all an illusion? How can we tell it’s not? For us this raises something further:

If a capability seems too wondrous to believe, can that be grounds for doubting one or more of the assumptions that underlie it?

In short, the magical success of crypto could be misleading. Could the assumptions it rests on go beyond magic into fantasy? In short could factoring be easy, and therefore modern crypto be wrong? Could the whole edifice collapse? Who knows?

## Open Problems

The three issues we have highlighted can be summarized as:

• Not knowing how to test what we are getting;

• Getting something that works in the field but not knowing how we got it; and

• Not knowing whether things deployed in the field are really true.

Can we distinguish the parts of theory that underlie these problems from “magic”? Must we bewail this state of our field, or is it an inevitable harbinger that complexity, learning, and crypto are becoming “sufficiently advanced”?

A non-announcement announcement

 Crop from Farkas Prize src

Michel Goemans is the chair of this year’s ACM/IEEE Knuth Prize committee. He teaches at MIT and among many wonderful achievements co-won the 2000 MOS/AMS Fulkerson Prize with David Williamson for their great work on approximation for MAX CUT and MAX SAT and other optimization problems.

A few days ago he emailed me to ask if Ken and I would announce this year’s call for nominations.
Read more…

tags: , , ,

A simple example of the failure of the fundamental theorem of arithmetic

Ernst Kummer was a German mathematician active in the early 1800s. He is most famous for his beautiful work on an approach designed to solve Fermat’s Last Theorem (FLT).

Today we will talk about a barrier that stopped his approach from succeeding.
Read more…

Marvin Minsky’s contributions to complexity theory

 Cropped from BBC feature on AI

Marvin Minsky, sad to relate, passed away last Sunday. He was one of the great leaders of artificial intelligence (AI), and his early work helped shape the field for decades.

Today Ken and I remember him also as a theorist.

We halve our blunder rate when infinitesimally ahead, but why?

 Crop from Seneca chess quote source

Lucius Seneca was a Roman playwright, philosopher, and statesman of the first century. He is called “the Younger” because his father Marcus Seneca was also a famous writer. His elder brother Lucius Gallio appears as a judge in the Book of Acts. Beside many quotations from his work, Seneca is famous for one he is not known to have said:

“To err is human.”

Lest we cluck at human error in pinning down ancient quotations, the source for the following updated version is also unknown—even with our legions of computers by which to track it:

“To err is human, but to really screw things up requires a computer.”

Today I report a phenomenon about human error that is magnified by today’s computers’ deeper search, and that I believe arises from their interaction with complexity properties of chess.
Read more…

Euclid writes randomness into his Elements

 Cropped from source (Garrett Coakley)

Euclid is, of course, the Greek mathematician, who is often referred to as the “Father of Geometry.”

Today Ken and I want to talk about an “error” that appears in the famous volumes written by Euclid a few years ago—about 2300 years ago.

Read more…