2008-2009 Seminars

Jun
16
2009

Computer Science/Discrete Mathematics Seminar II

Extensions to the Method of Multiplicities with Applications to Kakeya Sets and Mergers
10:30am|West Bldg. Lecture Hall

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

Jun
09
2009

Computer Science/Discrete Mathematics Seminar II

Linear Systems Over Composite Moduli
10:30am|West Bldg. Lecture Hall

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

Jun
08
2009

Computer Science/Discrete Mathematics Seminar I

Quasi-One-Way Functions
11:15am|S-101

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

May
26
2009

Computer Science/Discrete Mathematics Seminar I

On the Complexity of Boolean Functions in Different Characteristics
Amir Shpilka
2:00pm|S-101

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

May
26
2009

Computer Science/Discrete Mathematics Seminar II

Constraints, Logic and Derandomization
10:30am|S-101

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