8c469b1f 
 XPost: cs.bboard, columbia.general.bboard 
 From: rocco@news.cs.columbia.edu 
  
 Columbia's own Krysta Svore will be speaking on Wed at 10:00am (CS 
 Conference Room) in a Quantum/Theory seminar. 
  
 And Columbia's own David Phillips will be speaking on Thurs at 2:30 (CS 
 Conference Room) in a Theory seminar. 
  
 Abstracts for both talks are below.  Hope to see you there! 
  
 -- Rocco 
  
 **************************************** 
  
 QUANTUM/THEORY SEMINAR 
 10:00am, Wednesday, March 30, 2005 
 CS Conference Room 
 Title: "Pseudothreshold or threshold? - Identifying quantum 
  fault-tolerance thresholds" 
  
 Speaker: Krysta Svore 
         Department of Computer Science 
         Columbia University 
  
 Joint work with Andrew Cross and Isaac Chuang, MIT 
  
 ABSTRACT 
  
 Being able to determine a true threshold value for quantum gates is 
 critical for fault-tolerant quantum computing.  We analyze and study 
 pseudothresholds, that is, fault-tolerant threshold results which may 
 not indicate the true threshold value, and their relation to more 
 accurate fault-tolerance thresholds.  We expand upon the definition of 
 pseudothreshold and identify several properties of fault-tolerance studies 
 that can lead to a pseudothreshold result.  We show differences between 
 a pseudothreshold and a more accurate threshold result for both classical 
 and quantum error correcting codes.  This difference can be more than an 
 order of magnitude.  Our goal is to emphasize the need for higher levels 
 of concatenation and the consideration of more parameters in a threshold 
 analysis to obtain a more reliable threshold result. 
  
 **************************************** 
  
 THEORY SEMINAR 
 2:30pm, Thursday, March 31, 2005 
 CS Conference Room 
 Title: "Approximation Algorithms for Semidefinite Packing Problems with 
  Applications to Max-Cut and Graph Coloring" 
  
 Speaker: David Phillips 
          IEOR 
          Columbia University 
  
 ABSTRACT 
  
 We describe the semidefinite analog of the vector packing problem, and 
 show that the semidefinite programming relaxations for MAXCUT [Goemans and 
 Williamson (1995)] and graph coloring [Karger, Motwani and Sudan (1998)] 
 are in this class of problems. We extend a method of Bienstock and Iyengar 
 (2004) which was based on ideas from Nesterov (2003) to design an 
 algorithm for computing $\\epsilon$-approximate solutions for this class of 
 semidefinite programs. Our algorithm is in the spirit of Klein and Lu 
 (1996), and decreases the dependence of the run-time on $\\epsilon$ from 
 $\\epsilon^{-2}$ to $\\epsilon^{-1}$. For sparse graphs, our method is 
 faster than the best specialized interior point methods. A significant 
 feature of our method is that it treats both the MAXCUT and the graph 
 coloring problem in a unified manner. 
  
 --- SoupGate-Win32 v1.05 
  * Origin: you cannot sedate... all the things you hate (1:229/2)