Vicky Choi Assistant Professor Department of Computer Science Virginia Tech Office: Room 304 Phone: (703) 538-3774; Fax: (703) 538-8348 Email: vchoi@(virginia tech's email address)

Research Interest:

Quantum Computation. Design, analysis and implementation of algorithms in bioinformatics, computational chemistry, computational geometry, and discrete mathematics.

Teaching:

• Spring 2011: CS5114 Theory of Algorithms (NVC & VT-MENA), CS5104 Computability and Complexity ( Scholar@VT)
• Fall 2010: CS5114 Theory of Algorithms
• Spring 2010: CS5104 Computational Complexity, CS6104 Adiabatic Quantum Computation
• Fall 2009: CS5114 Theory of Algorithms
• Spring 2009: CS4104 Data and Algorithm Analysis, CS6104 Quantum Computation
• Fall 2006: CS5124 Algorithms in Bioinformatics
• Spring 2006: CS5984 Algorithms in Structural Bioinformatics
• Fall 2005: CS5114 Theory of Algorithms
• Spring 2005: CS6104 Algorithms in Structural Bioinformatics
• Fall 2004: CS4104 Data and Algorithm Analysis

Current Research on Quantum Computation:

• Introduction to Adiabatic Quantum Computation. [presentation]
• Minor-Embedding in Adiabatic Quantum Computation. [presentation]
• Minor-Embedding in Adiabatic Quantum Computation: I. The Parameter Setting Problem. Quantum Information Processing, Volume 7, Number 5, 2008, page 193 -- 209. arXiv:quant-ph/0804.4884
• Minor-Embedding in Adiabatic Quantum Computation: II. Minor-universal Graph Design. arXiv:quant-ph/1001.3116 To appear at Quantum Information Processing.
• Adiabatic Quantum Optimization Algorithms
  • First Order Quantum Phase Transition in Adiabatic Quantum Computation. (with Mohammad Amin) arXiv:quant-ph/0904.1387 Phys. Rev. A. 2009.
  • Adiabatic Quantum Algorithms for the NP-complete MIS, Exact Cover and 3SAT Problems. arXiv:quant-ph/1004.2226 Presented at QAMF'2010, Vancouver, Canada, July 23, 2010. [presentation]
  • Avoid First Order Quantum Phase Transition by Change Problem Hamiltonians arXiv:quant-ph/1010.1220
  • Different Adiabatic Quantum Optimization Algorithms for the NP-Complete Exact Cover and 3SAT Problems. arXiv:quant-ph/1010.1221
  • Different Adiabatic Quantum Optimization Algorithms for the NP-Complete Exact Cover Problem. To appear at Proc Nat'l Acad Sci(PNAS).

Some Earlier Work:

Microarray Data Analysis using Galois (Concept) Lattice:

• Faster Algorithms for Constructing a Galois/Concept Lattice. Presented at SIAM Conference on Discrete Mathematics 2006, University of Victoria, Canada. [(pdf)](arXiv:cs.DM/0602069)
• Microarray Data Analysis (with Reinhard Laubenbacher, Karen Duca, Vy Lam and Yang Huang) [(pdf)]. Presented at DIMACS Workshop on Clustering Problems in Biological Networks, Piscataway, NJ, May 9--11, 2006. APBC 2007. Journal of Bioinformatics and Computational Biology, Vol 6, No.1, 2008.

Protein Small-Molecule Docking and Conformation Analysis:

• V. Choi. Yucca: An efficient algorithm for small molecule docking. Chemistry and Biodiversity, Issue 11, 2005, pp1517 -- 1524. [preprint(pdf)] Presented at the Symposium on Computational Methods in Drug Design, Switzerland, 2005. [presentation(ppt)]
• V. Choi. On Updating Torsion Angles of Molecular Conformations. DIMACS Workshop on Information Processing by Protein Structures in Molecular Recognition, June 13-14 2005. Journal of Chemical Information and Modeling (formerly JCICS) 46 (1), 2006, pp438 -- 444. [preprint(pdf)] [presentation(ppt)]

Sequence Assembly of the Human Genome

• BARNACLE's assembly of December 2001 freeze of the human genome
• The Sequence and Assembly of Highly Duplicated Regions in the Human Genome. Genome Sequencing & Biology meeting at Cold Spring Harbor Laboratory 2002.  
• Barnacle: An Assembly Algorithm for Clone-based Sequences of Whole Genomes. Gene,  320, 165-176, 2003.