Faculty

Subscribe to Faculty
Tuesday, April 17, 2012 12:00 am - 1:00 pm EDT (GMT -04:00)

Leonard Schulman: Cryptography from tensor problems

Leonard Schulman, California Institute of Technology

Abstract

We describe a new cryptosystem which (conjecturally) provides both a
trap-door one-way function and a signature scheme. The new system is a
type of "multivariate quadratic" cryptosystem, but is based on a
different trap-door from existing methods, and is simpler.

Wednesday, April 11, 2012 12:00 am - Friday, April 13, 2012 1:00 am EDT (GMT -04:00)

Recent Progress in Quantum Algorithms

One of the main goals of Quantum Computation is to design novel methods for speeding up computations by taking advantage of the surprising effects of quantum mechanics. Many powerful quantum algorithms have been discovered over the last decade, yet a large number of them derive their power from a handful of ingredients. The workshop will review the state of the art in quantum algorithms and complexity, identify problems where methods founded on the laws of quantum physics might play a significant role, and establish common targets.

Monday, April 9, 2012 12:30 pm - 1:00 pm EDT (GMT -04:00)

Aram Harrow: Detecting pure entanglement is easy, so detecting mixed entanglement is hard

Aram Harrow, University of Washington

Abstract

This talk will begin by justifying the first part of the title, by explaining a method to test whether a given multipartite pure state is product or far from product, given only two copies of the state. Next, I'll explain how this test has implications for the computational hardness of a large number of optimization problems.