CSDM Seminars

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