CSDM Seminars

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

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

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

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

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

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

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

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