MENU

Valentine Kabanets

Professor
Computing Science

Areas of interest

Research Interests:
Computational complexity theory
Pseudorandomness and derandomization
Circuit lower bounds
Logic in complexity theory

Teaching Interests:
Computability and Complexity
Data structures and Algorithms

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

Courses

This instructor is currently not teaching any courses.

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).