CSDM Seminars

Oct
18
2010

Computer Science/Discrete Mathematics Seminar I

A Unified Framework for Testing Linear-Invariant Properties
Arnab Bhattacharyya
11:15am|S-101

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

Oct
12
2010

Computer Science/Discrete Mathematics Seminar II

Approximating the Longest Increasing Subsequence in Polylogarithmic Time
10:30am|S-101

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

Oct
11
2010

Computer Science/Discrete Mathematics Seminar I

The Complexity of the Non-commutative Determinant
11:15am|S-101

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

Oct
05
2010

Computer Science/Discrete Mathematics Seminar II

Pseudorandom Generators for CCO[p] and the Fourier Spectrum of Low-Degree Polynomials Over Finite Fields
10:30am|S-101

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

Oct
04
2010

Computer Science/Discrete Mathematics Seminar I

Super-uniformity of the typical billiard path (proof included)
Jozsef Beck
11:15am|S-101

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

Sep
28
2010

Computer Science/Discrete Mathematics Seminar II

High-Rate Codes with Sublinear Time Decoding
10:30am|S-101

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

Sep
27
2010

Computer Science/Discrete Mathematics Seminar I

The Condition Number of a Random Matrix: From von Neumann-Goldstine to Spielman-Teng
11:15am|S-101

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

Sep
21
2010

Computer Science/Discrete Mathematics Seminar II

Invariance Principles in Theoretical Computer Science
10:30am|S-101

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

Sep
20
2010

Computer Science/Discrete Mathematics Seminar I

Dependent Random Choice and Approximate Sidorenko's Conjecture
Benny Sudakov
11:15am|S-101

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