# 2011-2012 Seminars

May

22

2012

May

21

2012

May

15

2012

### Computer Science/Discrete Mathematics Seminar II

From Irreducible Representations to Locally Decodable Codes

10:30am|West Bldg. Lecture Hall

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

May

01

2012

### Computer Science/Discrete Mathematics Seminar II

Lower Bounds for Matching Vector Codes

Abhishek Bhowmick

10:30am|S-101

Apr

30

2012

### Computer Science/Discrete Mathematics Seminar I

Randomized Greedy Algorithms for the Maximum Matching Problem with New Analysis

11:15am|S-101

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