Valentine Kabanets: Publications

• R. Impagliazzo, V. Kabanets, and A. Kolokolova

  An axiomatic approach to algebrization

• R. Impagliazzo, V. Kabanets, and A. Wigderson

  New Direct Product testers and 2-query PCPs

• Y. Dodis, R. Impagliazzo, R. Jaiswal, and V. Kabanets

  Security amplification for interactive cryptographic primitives

• R. Impagliazzo, R. Jaiswal, V. Kabanets, and A. Wigderson

  Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized

• A. Juma, V. Kabanets, C. Rackoff, and A. Shpilka

  The Black-Box Query Complexity of Polynomial Summation

• R. Impagliazzo, R. Jaiswal, and V. Kabanets

  Chernoff-type Direct Product Theorems

• J. Buresh-Oppenheim, V. Kabanets, and R. Santhanam

  Hardness Amplification in NP via Monotone Codes

• R. Impagliazzo, R. Jaiswal, and V. Kabanets

  Approximate List-Decoding of Direct Product Codes and Uniform Hardness Amplification (updated October 2007)

• V. Guruswami and V. Kabanets

  Hardness Amplification via Space-Efficient Direct Products

• L. Fortnow, R. Impagliazzo, V. Kabanets, C. Umans,

  On the Complexity of Succinct Zero-Sum Games

• C. Calabro, R. Impagliazzo, V. Kabanets, and R. Paturi,

  The Complexity of Unique k-SAT: An Isolation Lemma for k-CNFs

• V. Kabanets and R. Impagliazzo,

  Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds . (updated 10/8/04)

• V. Kabanets,

  Derandomization: A Brief Overview. (updated 09/06/03)

• R. Impagliazzo, V. Kabanets, and A. Wigderson,

  In Search of an Easy Witness: Exponential Time vs. Probabilistic Polynomial Time.

• V. Kabanets,

  Easiness Assumptions and Hardness Tests: Trading Time for Zero Error.

• V. Kabanets, C. Rackoff, and S.A. Cook,

  Efficiently Approximable Real-Valued Functions.

• V. Kabanets and J.-Y. Cai,

  Circuit Minimization Problem.

• V. Kabanets,

  Almost k-Wise Independence and Hard Boolean Functions.

• V. Kabanets,

  Recognizability Equals Definability for Partial k-Paths .

Dissertations

• Nonuniformly Hard Boolean Functions and Uniform Complexity Classes . PhD Thesis. University of Toronto. October, 2000.
• Recognizability Equals Definability for Partial k-Paths . Master's Thesis. Simon Fraser University. June, 1996.