CSDM Seminars

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

Finding the longest increasing subsequence (LIS) is a classic algorithmic problem. Simple O(n log n) algorithms, based on dynamic programming, are known for solving this problem exactly on arrays of length n. In this talk I'll discuss recent work of...

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

We give a pseudorandom generator, with seed length O(log n), for CC0[p], the class of constant-depth circuits with unbounded fan-in MODp gates, for prime p. More accurately, the seed length of our generator is O(log n) for any constant error epsilon...

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

Locally decodable codes are error-correcting codes that admit efficient decoding algorithms, that can recover any bit of the original message by looking at only a small number of locations of a corrupted codeword. The tradeoff between the rate of a...

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

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

A beautiful conjecture of Erd\H{o}s-Simonovits and Sidorenko states that if $H$ is a bipartite graph, then the random graph with edge density $p$ has in expectation asymptotically the minimum number of copies of $H$ over all graphs of the same order...