Follow
Valentine Kabanets
Valentine Kabanets
Professor of Computing Science, Simon Fraser University
Verified email at sfu.ca - Homepage
Title
Cited by
Cited by
Year
Derandomizing polynomial identity tests means proving circuit lower bounds
V Kabanets, R Impagliazzo
Proceedings of the thirty-fifth annual ACM symposium on Theory of computing …, 2003
6162003
In search of an easy witness: Exponential time vs. probabilistic polynomial time
R Impagliazzo, V Kabanets, A Wigderson
Journal of Computer and System Sciences 65 (4), 672-694, 2002
2752002
Circuit minimization problem
V Kabanets, JY Cai
Proceedings of the thirty-second annual ACM symposium on Theory of computing …, 2000
2112000
Constructive proofs of concentration bounds
R Impagliazzo, V Kabanets
International Workshop on Randomization and Approximation Techniques in …, 2010
1122010
Uniform direct product theorems: simplified, optimized, and derandomized
R Impagliazzo, R Jaiswal, V Kabanets, A Wigderson
Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, 579-588, 2008
1042008
Learning algorithms from natural proofs
ML Carmosino, R Impagliazzo, V Kabanets, A Kolokolova
31st Conference on Computational Complexity (CCC 2016), 2016
992016
Easiness assumptions and hardness tests: Trading time for zero error
V Kabanets
Journal of Computer and System Sciences 63 (2), 236-252, 2001
982001
The complexity of unique k-SAT: An isolation lemma for k-CNFs
C Calabro, R Impagliazzo, V Kabanets, R Paturi
Journal of Computer and System Sciences 74 (3), 386-393, 2008
962008
Mining circuit lower bound proofs for meta-algorithms
R Chen, V Kabanets, A Kolokolova, R Shaltiel, D Zuckerman
Computational Complexity 24, 333-392, 2015
782015
New direct-product testers and 2-query PCPs
R Impagliazzo, V Kabanets, A Wigderson
Proceedings of the forty-first annual ACM symposium on Theory of computing …, 2009
672009
Approximate list-decoding of direct product codes and uniform hardness amplification
R Impagliazzo, R Jaiswal, V Kabanets
SIAM Journal on Computing 39 (2), 564-605, 2009
602009
Derandomization: A brief overview
V Kabanets
Current Trends in Theoretical Computer Science: The Challenge of the New …, 2002
582002
On the complexity of succinct zero-sum games
L Fortnow, R Impagliazzo, V Kabanets, C Umans
Computational Complexity 17 (3), 353-376, 2008
492008
The power of natural properties as oracles
R Impagliazzo, V Kabanets, I Volkovich
computational complexity 32 (2), 6, 2023
402023
Security Amplification for Interactive Cryptographic Primitives
Y Dodis, R Impagliazzo, R Jaiswal, V Kabanets
Theory of Cryptography: 6th Theory of Cryptography Conference, TCC 2009, San …, 2009
352009
AC0 [p] lower bounds against MCSP via the coin problem
A Golovnev, R Ilango, R Impagliazzo, V Kabanets, A Kolokolova, A Tal
ICALP, 2019
332019
An axiomatic approach to algebrization
R Impagliazzo, V Kabanets, A Kolokolova
Proceedings of the forty-first annual ACM symposium on Theory of computing …, 2009
322009
Recognizability equals definability for partial k-paths
V Kabanets
International Colloquium on Automata, Languages, and Programming, 805-815, 1997
291997
The minimum oracle circuit size problem
E Allender, D Holden, V Kabanets
Computational Complexity 26, 469-496, 2017
282017
An improved deterministic# SAT algorithm for small De Morgan formulas
R Chen, V Kabanets, N Saurabh
Algorithmica 76, 68-87, 2016
282016
The system can't perform the operation now. Try again later.
Articles 1–20