2006-2007 seminars

All known efficient algorithms for computing the determinant of a matrix rely on commutativity of the matrix entries. How important is this property, and could we make use of an algorithm that computes determinants without assuming commutativity? In...

Let $G$ be a graph which contains no subgraphs isomorphic to fixed bipartite graph $H$. Using well known results from Extremal Graph theory, one can show that such $G$ has certain expansion properties, i.e., all small subsets of $G$ have large...

In combinatorial allocation, m items are to be assigned to n players so that their total utility is maximized. This problem has many variants depending on the utility functions involved and possible additional constraints. We consider two variants...

We consider the problem of bounding the absolute value of the correlation between parity and low-degree polynomials modulo q, for odd q >= 3. The boolean function corresponding to the polynomial is 0 on an input iff the polynomial evaluates to 0...

Achieving correlated equilibrium is a problem at the intersection of game theory, cryptography and efficient algorithms. Thus far, however, perfectly rational solutions have been lacking, and the problem has been formulated with somewhat limited...

In this work we study the correlation between low-degree GF(2) polynomials and explicit functions, where the correlation between two functions f,p : {0,1}^n -> {+1,-1} is defined as Correlation(p,f) := | E_x [f(x) p(x)] | = | P_x[f(x) = p(x)] - P_x...

A q-query Locally Decodable Code (LDC) encodes an n-bit message x as an N-bit codeword C(x), such that one can probabilistically recover any bit x_i of the message by querying only q bits of the codeword C(x), even after some constant fraction of...

Cut problems are fundamental to combinatorial optimization, and they naturally arise as intermediate problems in algorithm design. The study of cut problems is inherently connected to the dual notion of flows. In particular, starting with the...