# CSDM Seminars

May

03

2011

### Computer Science/Discrete Mathematics Seminar II

CSDM Seminars II will be resume first term of the 2011-12 academic year

10:30am|S-101

May

02

2011

### Computer Science/Discrete Mathematics Seminar I

CSDM Seminars I will resume first term of the 2011-12 academic year

11:15am|S-101

Apr

26

2011

### Computer Science/Discrete Mathematics Seminar II

Quadratic Goldreich-Levin Theorems

10:30am|S-101

Decompositions in theorems in classical Fourier analysis which
decompose a function into large Fourier coefficients and a part
that is pseudorandom
with respect to (has small correlation
with) linear functions. The Goldreich-Levin theorem [GL89]...

Apr

25

2011

### Computer Science/Discrete Mathematics Seminar I

Learning and Testing k-Model Distributions

Rocco Servidio

11:15am|S-101

A k-modal probability distribution over the domain {1,...,N} is one
whose histogram has at most k "peaks" and "valleys". Such
distributions are a natural generalization of the well-studied
class of monotone increasing (or monotone decreasing)...

Apr

22

2011

### MINI-WORKSHOP ON PSEUDORANDOMNESS

On Zaremba's Conjecture

5:00pm|S-101

Inspired by the theory of good lattice points in numerical
integration, Zaremba conjectured in 1972 that for every denominator
q, there is some coprime numerator p, such that the continued
fraction expansion of p/q has uniformly bounded quotients...

Apr

22

2011

### MINI-WORKSHOP ON PSEUDORANDOMNESS

Monotone Expanders -- Constructions and Applications

4:00pm|S-101

A Monotone Expander is an expander graph which can be decomposed
into a union of a constant number of monotone matchings, under some
fixed ordering of the vertices. A matching is monotone if every two
edges (u,v) and (u',v') in it satisfy u v

Apr

22

2011

### MINI-WORKSHOP ON PSEUDORANDOMNESS

The Polynomial Method and Applications From Finite Field Kakeya to Distinct Distances

2:30pm|S-101

Apr

22

2011

### MINI-WORKSHOP ON PSEUDORANDOMNESS

The Correlation of Multiplicative Characters with Polynomials over Finite Fields

11:30am|S-101

This talk will focus on the complexity of the cubic-residue (and higher-residue) characters over GF(2^n) , in the context of both arithmetic circuits and polynomials. We show that no subexponential-size, constant-depth arithmetic circuit over GF(2)...

Apr

22

2011

### MINI-WORKSHOP ON PSEUDORANDOMNESS

Random Walks in Linear Groups

Peter Varju

10:15am|S-101

I will talk about a joint work with Jean Bourgain that establishes spectral gaps for random walks on SL_n(Z/qZ). Let S be a fixed finite and symmetric subset of SL_n(Z) which generates a Zariski dense subgroup. We show that words of length C log(q)...

Apr

19

2011

### Computer Science/Discrete Mathematics Seminar II

New Tools for Graph Coloring

10:30am|S-101

How to color $3$ colorable graphs with few colors is a problem of
longstanding interest. The best polynomial-time algorithm uses
$n^{0.2130}$ colors.
We explore the possibility that
more levels of Lasserre Hierarchy can give improvements over...