# 2012-2013 Seminars

May

14

2013

May

13

2013

### Computer Science/Discrete Mathematics Seminar I

Association Schemes, Non-Commutative Polynomials and Lasserre Lower Bounds for Planted Clique

1:30pm|S-101

Finding cliques in random graphs and the closely related "planted"
clique variant, where a clique of size k is planted in a random
G(n,1/2) graph, have been the focus of substantial study in
algorithm design. Despite much effort, the best known...

May

13

2013

### Computer Science/Discrete Mathematics Seminar I

Nondeterministic Direct Product Reductions and the Success Probability of SAT Solvers

10:30am|S-101

In this talk I will describe nondeterministic reductions which
yield new direct product theorems (DPTs) for Boolean circuits. In
our theorems one assumes that a function F is "mildly hard" against
*nondeterministic* circuits of some size s(n)...

May

07

2013

May

06

2013

### Computer Science/Discrete Mathematics Seminar I

Tight Bounds for Set Disjointness in the Message-Passing Model

Rotem Oshman

11:15am|S-101

In many distributed systems, the cost of computation is dominated
by the cost of communication between the machines participating in
the computation. Communication complexity is therefore a very
useful tool in understanding distributed computation...

Apr

30

2013

### Computer Science/Discrete Mathematics Seminar II

Combinatorial Walrasian Equilibrium

Michal Feldman

10:30am|S-101

We study algorithms for combinatorial market design problems, where
a collection of objects are priced and sold to potential buyers
subject to equilibrium constraints. We introduce the notion of a
combinatorial Walrasian equilibium (CWE) as a...

Apr

29

2013

### Computer Science/Discrete Mathematics Seminar I

Cryptography and Preventing Collusion in Second Price (Vickery) Auctions

Michael Rabin

11:15am|S-101

We present practically efficient methods for proving correctness of
announced results of a computation while keeping input and
intermediate values information theoretically secret. These methods
are applied to solve the long standing problem of...

Apr

23

2013

### Computer Science/Discrete Mathematics Seminar II

Uncertainty Principle

10:30am|S-101

Informally, uncertainty principle says that function and its
Fourier transform can not be both concentrated. Uncertainty
principle has a lot of applications in areas like compressed
sensing, error correcting codes, number theory and many others....

Apr

22

2013

### Computer Science/Discrete Mathematics Seminar I

Diffuse Decompositions of Polynomials

Daniel Kane

11:15am|S-101

We study some problems relating to polynomials evaluated either at
random Gaussian or random Bernoulli inputs. We present some new
work on a structure theorem for degree-d polynomials with Gaussian
inputs. In particular, if p is a given degree-d...

Apr

16

2013