2012-2013 Seminars

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

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

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

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

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

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

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