Valentine Kabanets

Associate Professor, School of Computing Science

Contact:

Tel:
778.782.6912
Email:
kabanets@cs.sfu.ca
Fax:
778.782.3045   
Office:
SFU Burnaby, TASC 8011
Personal webpage:  http://www.cs.sfu.ca/~kabanets  

Education

  • Ph.D. Computer Science, University of Toronto, Canada, 2000
  • M.Sc. Computing Science, Simon Fraser University, Canada, 1996
  • B.Sc., National University of Kiev, Ukraine, 1993

Research interests

  • Computational  complexity theory
  • Pseudorandomness and derandomization
  • Circuit lower bounds
  • Logic in complexity theory

Teaching interests

  • Computability and Complexity
  • Data structures and Algorithms

Recently taught courses

  •  CMPT 307 Data structures and algorithms
  •  CMPT 881 Average-case complexity
  •  CMPT 308 Computability and Complexity

Selected recent publications

  • V. Kabanets and R. Impagliazzo, Derandomizing Polynomial Identity Tests means proving circuit lower bounds, Computational Complexity, 13(1-2), pages 1-46, 2004.
  • R. Impagliazzo, V. Kabanets, and A. Kolokolova, An axiomatic approach to algebrization, in STOC’09.
  • R. Impagliazzo, V. Kabanets, and A. Wigderson, New direct product testers and 2-query PCPs, in STOC’09 (to appear in the SIAM Journal on Computing).


Visit website for more information.