2011-2012 Seminars

May
14
2012

Computer Science/Discrete Mathematics Seminar I

Are Lattice Based Cryptosystems Secure Enough?
Nisheeth Vishnoi
11:15am|S-101
The security of several cryptosystems is based on our apparent inability to solve the following computational problem: given as input a basis B for a lattice and a target vector t , find the lattice point closest to t. This problem, referred to as...
May
08
2012

Computer Science/Discrete Mathematics Seminar II

Pseudorandomness from Shrinkage
10:30am|S-101
One powerful theme in complexity theory and pseudorandomness in the past few decades has been the use of lower bounds to give pseudorandom generators (PRGs). However, the general results using this hardness vs. randomness paradigm suffer a...
May
07
2012

Computer Science/Discrete Mathematics Seminar I

Topology of Norms Defined by Systems of Linear forms
11:15am|S-101
Gowers' uniformity norms are defined by average of a function over specific sets of linear forms. We study norms that are similarly defined by a system of linear forms. We prove that for bounded complex functions over $F_p^n$, each such norm is...
Apr
24
2012

Computer Science/Discrete Mathematics Seminar II

Pseudorandom Generators for Read-Once ACC^0
10:30am|S-101
We consider the problem of constructing pseudorandom generators for read-once circuits. We give an explicit construction of a pseudorandom generator for the class of read-once constant depth circuits with unbounded fan-in AND, OR, NOT and...
Apr
23
2012

Computer Science/Discrete Mathematics Seminar I

Computational Entropy
11:15am|S-101
Shannon's notion of entropy measures the amount of "randomness" in a process. However, to an algorithm with bounded resources, the amount of randomness can appear to be very different from the Shannon entropy. Indeed, various measures of...