Previous Conferences & Workshops

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

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

The goal of hardness amplification is to take a function f : {0,1}^n --> {0,1} that is mildly average-case hard (i.e., very "small" circuit fails to compute f on at least a 1/poly(n) fraction of inputs), and produce a new function f' that is very...

In a joint work with Bob Kohn, we give a new control-type interpretation on the level-set approach to motion by curvature and related interface motion laws. More precisely, we give a family of discrete-time, two-person games whose value functions...

This will be an overview of the paper hep-th/0306238 written jointly with N. Nekrasov. Our main idea is the interpretation of the low-energy effective prepotential of the N=2 supersymmetric gauge theory as the free energy of a certain natural...