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 focussed 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.

In this talk, I will describe what complexity theory has to say about such interactions. Most of the talk will focus on how some of the nebulous notions, such as intelligence and understanding, should be defined in this setting. We'll also show how interactive proofs, randomness and one-way functions, can play an enabling role in establishing some meaningful communication. Among the outcomes of our investigation are some proposals for mathematical tests of intelligence.