Previous Conferences & Workshops

Nov
30
2004

Computer Science/Discrete Mathematics Seminar II

On Random Bernoulli Matrices: Singularity and Determinant
10:30am|S-101

We study properties of random Bernoulli matrices. In particular, we determine the typical value of the determinant. We also obtain a new bound on the probability that the matrix is singular. Joint work with T. Tao.

Nov
29
2004

Computer Science/Discrete Mathematics Seminar I

An Unconditional Study of Computational Zero Knowledge
11:15am|S-101

We prove a number of general theorems about CZK, the class of problems possessing computational zero-knowledge proofs. Our results are *unconditional*, in contrast to most previous works on CZK which rely on the assumption that one-way functions...

Nov
23
2004

Computer Science/Discrete Mathematics Seminar II

Learnability and Automatizability
Michael Alekhnovich
10:30am|S-101

We consider the complexity of properly learning concept classes, i.e. when the learner must output a hypothesis of the same form as the unknown concept. We present the following new upper and lower bounds on well-known concept classes: 1. We show...