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

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

Apr
18
2011

Computer Science/Discrete Mathematics Seminar I

Quantum Fingerprints that Keep Secrets
Dmitry Gavinsky
11:15am|S-101

In a joint work with Tsuyoshi Ito we have constructed a fingerprinting scheme (i.e., hashing) that leaks significantly less than log(1/epsilon) bits about the preimage, where epsilon is the error ("collision") probability. It is easy to see that...

Apr
11
2011

Computer Science/Discrete Mathematics Seminar I

Graph Sparsification by Edge-Connectivity and Random Spanning Trees
Nick Harvey
11:15am|S-101

A "sparsifier" of a graph is a weighted subgraph for which every cut has approximately the same value as the original graph, up to a factor of (1 +/- eps). Sparsifiers were first studied by Benczur and Karger (1996). They have wide-ranging...

Apr
05
2011

Computer Science/Discrete Mathematics Seminar II

Zero-One Rounding of Singular Vectors
10:30am|S-101

Given a matrix $A$, it can be shown that there is a vector $z \in 0,1^n$ for which $|Az|/|Z| \geq |A|_2/C \log(n)$ (a0/1 sum of columns of $A$ which witnesses its large spectral norm) for instance by discretizing the top singular vector of $A$ and...

Apr
04
2011

Computer Science/Discrete Mathematics Seminar I

Improved Bounds for the Randomized Decision Tree Complexity of Recursive Majority
Ashwin Nayak
11:15am|S-101

Recursive Majority-of-three (3-Maj) is a deceptively simple problem in the study of randomized decision tree complexity. The precise complexity of this problem is unknown, while that of the similarly defined Recursive NAND tree is completely...

Mar
29
2011

Computer Science/Discrete Mathematics Seminar II

General Hardness Amplification of Predicates and Puzzles
Grant Schoenbeck
10:30am|S-101

In this talk, I will give new proofs for the hardness amplification of fficiently samplable predicates and of weakly verifiable puzzles. More oncretely, in the first part of the talk, I will give a new proof of Yao's XOR-Lemma as well as related...