Program, March 24, 1995

• 9:30-10:00am, Morning Reception in Atrium

• 10:00-11:00am, A Fast Factoring Algorithm for a Quantum Computer

  Peter W. Shor , AT&T Bell Laboratories.
  
  Shor will present a randomized algorithm for factoring integers on a quantum computer. His algorithm takes a number of steps polynomial in the number of digits of the integer to be factored; no such polynomial-time factoring algorithm is known for classical computers. Integer factoring forms the basis of several cryptosystems, including the widely-used RSA cryptosystem. Abstract.

  10:00am-4:00pm, Room 022, Man vs. Machine Chess Match:

  Grandmaster Gennady Sagalchik (Brooklyn College)
  vs.
  1800-node Intel Paragon supercomputer running *Socrates
  ( MIT Lab for Computer Science )
  
  

• 11:00-11:30am, Break

• 11:30am-12:30pm, Factoring Integers by Solving Boolean Equations

  Samuel J. Lomonaco, Jr. , UMBC.
  
  Lomonaco will discuss an algorithm that factors integers by solving Boolean equations. In particular, he will explain how this algorithm has lead to new approaches to factoring and to insights into the complexity of factoring. Abstract.

• 12:30-2:30pm, Buffet Luncheon in Atrium (please register)

• 2:30-3:30pm, Approximation Algorithms via Linear Programming

  David Shmoys , Cornell University.
  
  Linear programming is one of the most useful tools in the design and analysis of approximation algorithms. Shmoys will survey a number of results in this area. Abstract.

• 3:30-4:00pm, Break

• 4:00-5:00pm, The *Socrates Massively Parallel Chess Program

  Bradley C. Kuszmaul , MIT Laboratory for Computer Science.
  
  Kuszmaul will describe the *Socrates Massively Parallel Chess Program and explain how computer chess has helped him understand how to run multithreaded-parallel programs. Abstract.

• 5:00pm, Adjourn