## Computer Science and Discrete Mathematics

Theoretical Computer Science and Discrete Mathematics

## Randomness and Pseudo-randomness

Avi Wigderson
October 5, 2011 (All day)

Avi Wigderson, Herbert H. Maass Professor in the School of Mathematics, gave a Friends Forum in October 2011, entitled Randomness and Pseudo-randomness.

## Existence of Small Families of t-wise Independent Permutations and t-Designs Via Local Limit Theorems

Shachar Lovett
September 20, 2011 - 10:30am

We show existence of rigid combinatorial objects that previously were not known to exist. Specifically, we consider two families of objects:

1. A family of permutations on n elements is t-wise independent if it acts uniformly on tuples of t elements. Constructions of small families of t-wise independent permutations are known only for $$t=1,2,3$$ . We show that there exist small families of t-wise independent permutations for all t , whose size is $$n^{O(t)}$$ .

## A PRG for Gaussian Polynomial Threshold Functions

Daniel Kane
Harvard University
March 15, 2011 - 10:30am

We define a polynomial threshold function to be a function of the form f(x) = sgn(p(x)) for p a polynomial. We discuss some recent techniques for dealing with polynomial threshold functions, particular when evaluated on random Gaussians. We show how to use these ideas to produce a pseudo random generator for degree-d polynomial threshold functions of Gaussians with seed length poly(2^d,log(n),epsilon^{-1}) .

## On the Fourier Spectrum of Symmetric Boolean Functions

Amir Shpilka
Technion; on leave at Microsoft Research New England
March 14, 2011 - 11:15am

It is well-known that any Boolean function f:{-1,+1}^n \to {-1,+1} can be written uniquely as a polynomial f(x) = \sum_{S subset [n]} f_s \prod_{i in S} x_i. The collection of coefficients (f_S's) this expression are referred to (with good reason) as the Fourier spectrum of f. The Fourier spectrum has played a central role in modern computer science by converting combinatorial and algorithmic questions about f into algebraic or analytic questions about the spectrum.

## The Graph Removal Lemma

Jacob Fox
Massachusetts Institute of Technology
November 8, 2010 - 11:15am

Let H be a fixed graph with h vertices. The graph removal lemma states that every graph on n vertices with o(nh) copies of H can be made H-free by removing o(n2) edges. We give a new proof which avoids Szemeredi's regularity lemma and gives a better bound. This approach also works to give improved bounds for the directed and multicolored analogues of the graph removal lemma. This answers questions of Alon and Gowers.

## CSDM - The Tame Algebra

Yuval Flicker
The Ohio State University
December 7, 2009 - 11:00am

Member, School of Mathematics
April 26, 2011 - 10:30am

Decompositions in theorems in classical Fourier analysis which decompose a function into large Fourier coefficients and a part that is pseudorandom

## Learning and Testing k-Model Distributions

Rocco Servidio
Columbia University
April 25, 2011 - 11:15am

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

## Quantum Fingerprints that Keep Secrets

Dmitry Gavinsky
NEC Research Laboratories
April 18, 2011 - 11:15am

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 classically this is not achievable; our construction is quantum, and it gives a new example of (unconditional) qualitative advantage of quantum computers.

## New Tools for Graph Coloring

Rong Ge
Princeton University
April 19, 2011 - 10:30am

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 previous algorithms. While the case of general graphs is still open, we can give analyse the Lasserre relaxation for two interesting families of graphs.