<!doctype html public "-//W3C//DTD W3 HTML//EN">

<html><head><style type="text/css"><!--

blockquote, dl, ul, ol, li { padding-top: 0 ; padding-bottom: 0 }

 --></style><title>MIT Quantum Information Processing Special Seminar

Announc</title></head><body>

<div>This week's Theory of Computation seminar should be of interest

to subscribers to this list:</div>

<div><br></div>

<hr>

<div align="center"><font size="+2"><b>Quantum Encodings and

Applications to Communication Complexity and Locally Decodable

Codes</b></font></div>

<div align="center"><br></div>

<div align="center"><font size="+1"><i>by</i> Iordanis Kerenidis

(<i>Postdoctoral Associate, MIT Math Dept.</i>)</font></div>

<div align="center"><font size="+1">Tuesday, October 5, 2004 at 4:00

PM in Room 32-G449 (Kiva)</font></div>

<div align="center"><br></div>

<div align="center"><u>ABSTRACT</u></div>

<div><br></div>

<blockquote>Quantum computation and information has become a central

research area in theoretical computer science. It studies how

information is encoded in nature according to the laws of quantum

mechanics and what this means for its computational power. The ability

of a quantum system to be in a superposition of states enables us to

store an exponential amount of information in a quantum system.

However, this information is accessible only indirectly via

measurements. Our goal is precisely to investigate the fundamental

question of how information is encoded and processed in quantum

mechanical systems.</blockquote>

<blockquote><br></blockquote>

<blockquote>We investigate their power relative to classical encodings

in the model of one-way communication complexity and show that they

can be exponentially more efficient, answering a long-standing open

question in the area of quantum communication complexity. Furthermore,

we show how the theory developed for the study of quantum information

can be employed in order to answer questions about classical coding

theory and complexity by proving an exponential lower bound for

2-query Locally Decodable Codes. This is the first example where

quantum techniques are essential in resolving a purely classical

question.</blockquote>

<blockquote><br></blockquote>

<blockquote>No previous knowledge of quantum computing is

assumed.</blockquote>

<blockquote><br></blockquote>

</body>

</html>