Research Abstracts - 2007

Introduction

Consider the following fantastic scenario: Earth has just started receiving some signals from outer space. These signals don't seem like usual cosmic noise. Potentially an intelligent alien civilization is trying to make contact. How should Earth respond? How can we (earthlings) tell if the aliens are receiving our response and reacting to it? Are they really intelligent, or are we talking to sunspots? If they are intelligent, will we ever be able to achieve meaningful interaction in this setting?

The classical theory of communication, typically ignores the issue of semantics of communication, and has focused principally on quantitative measures in syntactic settings. Increasingly, however, it is becoming clear that practical challenges to communication arise due to semantic gaps between senders and receivers. The fictional problem above, merely, carries this gap to the extreme.

Despite the fantastic nature of this fictional problem, it has been seriously considered in the past, though mostly from an empirical perspective. Most notably, Freudenthal [Fr60] claims that it is possible to code messages describing mathematics, physics, or even simple stories in a radio transmission in such a way that it can be understood by any sufficiently humanlike recipient. The difficulty with schemes like Freudenthal's is in the assumption that the recipient is "sufficiently humanlike." It is possible to state the assumptions Freudenthal requires more precisely, but these assumptions are quite strong, too strong to be considered truly universal.

Rather than take such strong assumptions on the recipient's behavior for granted, we begin by requiring that a well-defined, verifiable goal be specified. We then are able to exhibit protocols with the guarantee that if some efficient protocol could achieve the specified goal while conversing with the alien (e.g., by conversing in the alien's language), then our protocol efficiently achieves this goal.

Preliminary results and techniques

We begin by considering the familiar goal of attempting to determine the answer to a given yes-or-no question. In particular, we suppose that we are given a question that is beyond our computational abilities, and we wish to use the assitance of our alien friend to determine its answer. In this setting, we assume that:

• communication is well-synchronized: we take turns passing finite-length strings back and forth
• some probabilistic polynomial time protocol is capable of determining the answers to these questions by conversing with the alien, independent of their prior conversation: regardless of what messages were previously passed between us, if we run this protocol, it converses with the alien for an amount of time bounded by a polynomial function of the length of the question, and outputs an answer that is correct with high probability.

Note that we do not know what this protocol is---this is how we model our lack of understanding. We then seek a probabilistic protocol that is universal in the sense that:

• For any such alien, there is a polynomial time bound such that for all questions, our protocol converses with the alien and outputs an answer that is correct with high probability within the time bound.

This setting is inspired and informed by the theory of interactive proofs [BM88, GMR89] and program checking [BK89]. Notably, we are able to show the following [JS07]:

• There is a universal protocol for deciding any PSPACE-complete question
• Any question that has a universal protocol is in PSPACE.

These results are closely related to similar results for IP (informally, we can say "mistrust = misunderstanding"). The universal protocol we exhibit combines an interactive proof system for a PSPACE-complete problem [LFKN92, Sh92] (in which the prover can be simulated in PSPACE) with a Levin-style enumeration [Le73].

Directions for future work

Broadly speaking, there are two directions in which we intend to take this project in the near future. The first is in finding ways to improve the efficiency of the protocol---the use of enumerations incurs a cost to the running time that is exponential in the lengths of the descriptions of the protocols we seek, exponential in the number of bits that are necessary in principle to establish communication. We can show that in our computational setting above, this exponential cost is necessary [JS07] so improving this will entail finding a more restricted setting that is still general enough to be considered "universal." The second direction is to consider a wider array of specific goals, some of which we hope will permit more efficient protocols. An example of such a goal is a test or proof of intelligence. We have some proposals for such proofs of intelligence [JS07], and in the future hope to provide a formal setting demonstrating the validity of such a proof.

Support

This research is partially supported by an NSF Graduate Research Fellowship.

References:

[BM88] Laszlo Babai and Shlomo Moran. A randomized proof system and a hierarchy of complexity classes. JCSS, 36:254--376, 1988.

[BK89] Manuel Blum and Sampath Kannan. Designing programs that check their work. In Proceedings of the 21st Symposium on Theory of Computing, pp. 86--97, 1989.

[Fr60] Hans Freutdenthal. LINCOS: Design of a Language for Cosmic Intercourse. North-Holland Publishing Company, Amsterdam, 1960.

[GMR89] Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The knowledge complexity of interactive proof systems. SIAM J Comput., 18(1):186--208, 1989.

[JS07] Brendan Juba and Madhu Sudan. Towards universal semantic communication. Preliminary manuscript---available at http://theory.lcs.mit.edu/%7Emadhu/papers/juba.pdf

[Le73] Leonid A. Levin. Universal search problems. Probl. Inform. Transm., 9:265--266, 1973.

[LFKN92] Carsten Lund, Lance Fortnow, Howard J. Karloff, and Noam Nisan. Algebraic methods for interactive proof systems. Journal of the ACM, 39(4):859--868, October 1992.