## Saturday, May 05, 2007

### Algorithms, Inference and Statistical Physics (Santa Fe)

How can I refuse to go to a meeting as broad as Algo, Inference and Statistical Physics? It was held recently at Santa Fe. Wonderful crowd of several coding/information/communication theorists, some physicists, and a handful of algorithmii (Dimitris Achlioptas, Asish Goel). David Tse gave a nice talk on how much information can be routed in a sensor network (his result improves on the seminal work by Gupta and Kumar), more below. There were talks on message passing algorithms, the relationship between Belief Propagation and LP, and others including network coding, and (:-) may be) even physics.

Here is a technical issue. The Bernoulli random graph is G(n,p) where each edge in an n-node graph appears independently with probability p. The geometric random graph is G(n,r) where n nodes are randomly placed on Euclidean plane and any two nodes within distance r have an edge between them. One can analyze G(n,r) much like G(n,p), but the key difference is that the edges are not independent in G(n,r).

While a lot of papers have analyzed properties of G(n,r) recently, for a long time I thought they should really just behave like a grid, and they should be easy to analyze using simple gridding techniques. Gopal and I managed to that for some basic problems in a SODA paper. The capacity result of \sqrt{n} from Gupta, Kumar paper also seems to indicate the grid-like behavior of G(n,r). In a paper that proved thresholds for monotone properties of G(n,r), the authors Goel, Rai and Krishnamchari used red-blue matching, and in a recent talk, Ashish at this workshop formalized some claims about upper and lower bounding G(n,r) by grids for estimating certain properties. So a question:

Can the information capacity results of Gupta and Kumar, or the recent ones by A. Ozgur, O. Leveque and David Tse (OLT), be rephrased as follows: G(n,r) for a particular property (routing,information exchange, whatever), behaves like a well-known graph (mesh, clique or a linked list of some depth)? Studying such property on these well-known graphs is more straightforward. In particular, OLT result that uses recursive multi-transmit, multi-receive routing protocol to transmit O(n^(1-\eps)) bits per pair from n source-destination pairs(Gupta and Kumar showed O(n^{1/2})) is interesting and does it show G(n,r) is like a YYY-type (clique?) graph of some size? This is a speculative question, probably much too vague to think about it.