2008-2009 Seminars

The 'method of multiplicities' (which is a variant of the polynomial method in combinatorics) is a very effective method to derive combinatorial bounds on the size of certain sets in vector spaces over finite fields. In this work we extend this...

We study solution sets to systems of 'generalized' linear equations of the form ell_i (x_1, x_2,...,x_n) \in A_i (mod m) where ell_1,...,ell_t are linear forms in n Boolean variables, each A_i is an arbitrary subset of Z_m, and m is a composite...

Ideally, one would want to base the security of standard cryptographic primitives (such as pseudorandom generators) on widely believed worst-case complexity assumptions like P does not equal NP. However, it is currently not known if this is possible...

Every Boolean function on n variables can be expressed as a unique multivariate polynomial modulo p for every prime p. In this work, we study how the degree of a function in one characteristic affects its complexity in other characteristics. We...

In their seminal paper Feder and Vardi proved that every problem in the class Monotone Monadic Strict NP (MMSNP) is random polynomial-time equivalent to a finite union of Constraint Satisfaction Problems (CSP). The class MMSNP is the "largest...