Computer Science and Discrete Mathematics (CSDM)

Theoretical Computer Science and Discrete Mathematics

Rank Bounds for Design Matrices with Applications to Combinatorial Geometry and Locally Correctable Codes

Zeev Dvir
Institute for Advanced Study
October 19, 2010

A (q,k,t)-design matrix is an m x n matrix whose pattern of zeros/non-zeros satisfies the following design-like condition: each row has at most q non-zeros, each column has at least k non-zeros and the supports of every two columns intersect in at most t rows. We prove that for $m\geq n$, the rank of any $(q,k,t)$-design matrix over a field of characteristic zero (or sufficiently large finite characteristic) is at least $n - (qtn/2k)^2$ .

Using this result we derive the following applications:

A Unified Framework for Testing Linear-Invariant Properties

Arnab Bhattacharyya
Massachusetts Institute of Technology
October 18, 2010

In a sequence of recent papers, Sudan and coauthors have investigated the relation between testability of properties of Boolean functions and the invariance of the properties with respect to transformations of the domain. Linear-invariance is arguably the most common such symmetry for natural properties of Boolean functions on the hypercube. Hence, it is an important goal to find necessary and sufficient conditions for testability of linear-invariant properties.

The Complexity of the Non-commutative Determinant

Srikanth Srinivasan
Institute for Advanced Study
October 11, 2010

I will talk about the computational complexity of computing the noncommutative determinant. In contrast to the case of commutative algebras, we know of (virtually) no efficient algorithms to compute the determinant over non-commutative domains. Our results show that the determinant in noncommutative settings can be as hard as the permanent.

Super-uniformity of the typical billiard path (proof included)

Jozsef Beck
Institute for Advanced Study
October 4, 2010

I will describe the proof of the following surprising result: the typical billiard paths form the family of the most uniformly distributed curves in the unit square. I will justify this vague claim with a precise statement. As a byproduct, we obtain the counter-intuitive fact that the complexity of the test set is almost irrelevant. The error term is shockingly small, and it does not matter that we test uniformity with a nice set (like a circle or a square), or with an arbitrarily ugly Lebesgue measurable subset of the unit square.

The Condition Number of a Random Matrix: From von Neumann-Goldstine to Spielman-Teng

Van Vu
Rutgers, The State University of New Jersey
September 27, 2010

The condition number of a matrix is at the heart of numerical linear algebra. In the 1940s von-Neumann and Goldstine, motivated by the problem of inverting, posed the following question:

(1) What is the condition number of a random matrix ?

During the years, this question was raised again and again, by various researchers (Smale, Demmel etc). About ten years ago, motivated by "Smoothed Analysis", Spielman and Teng raised a more general question:

(2) What is the condition number of a randomly perturbed matrix ?

Invariance Principles in Theoretical Computer Science

Carnegie Mellon University; Institute for Advanced Study
September 21, 2010

In this talk I will insult your intelligence by showing a non-original proof of the Central Limit Theorem, with not-particularly-good error bounds. However, the proof is very simple and flexible, allowing generalizations to multidimensional and higher-degree invariance principles. Time permitting, I will also discuss applications to areas of theoretical computer science: property testing, derandomization, learning, and inapproximability.