EVENT DETAILS AND ABSTRACT

Title: Probabilistic Proof of Existence Versus Explicit Construction
Speaker: Professor Laszlo Babai
Speaker Info: University of Chicago
Brief Description:
Special Note:
Abstract:

Following the late Paul Erdos, it has become a common technique to show the existence of interesting combinatorial objects by constructing an appropriate probability space and then demonstrating that most members of the space have the desired property.

This type of argument leaves the tantalizing question of how to construct even one of the objects shown to exist in abundance. In addition to their aesthetic appeal, questions of this type have become a matter of essence to the theory of computing.

The rare success stories in the quest for explicit constructions has invariably involved tools (ranging from the elementary to the profound) from algebra and number theory. We shall discuss some of these results and mention open questions. As an appetizer, I attach such an open question, originating from the theory of computing.

The talk will be accessible to all graduate students. No background in combinatorics or the theory of computing is required.

-----------------------------------------------------------

Appetizer: Robustness of rank under sign-preserving changes

Def: Let M be an n x n matrix whose entries are 1 and -1. Let s(M) denote the minimum rank of an n x n matrix which is obtained from M by changing its entries to nonzero real numbers while preserving the sign of each entry.

Remark: Using a result from real algebraic geometry, one can show that for most n x n matrices M, s(M) > n/32.

Open problem: Construct an explicit M such that s(M) > 100 log n.

Conjecture: Let S be the n x n Sylvester matrix (n=2^k, S is the k-fold tensor power of the 2 x 2 matrix (1,1;1,-1)). Then s(S) > cn for some positive constant c.