2012-2013 Seminars

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

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

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