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 | 616 | 2003 |
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 | 275 | 2002 |
Circuit minimization problem V Kabanets, JY Cai Proceedings of the thirty-second annual ACM symposium on Theory of computing …, 2000 | 211 | 2000 |
Constructive proofs of concentration bounds R Impagliazzo, V Kabanets International Workshop on Randomization and Approximation Techniques in …, 2010 | 112 | 2010 |
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 | 104 | 2008 |
Learning algorithms from natural proofs ML Carmosino, R Impagliazzo, V Kabanets, A Kolokolova 31st Conference on Computational Complexity (CCC 2016), 2016 | 99 | 2016 |
Easiness assumptions and hardness tests: Trading time for zero error V Kabanets Journal of Computer and System Sciences 63 (2), 236-252, 2001 | 98 | 2001 |
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 | 96 | 2008 |
Mining circuit lower bound proofs for meta-algorithms R Chen, V Kabanets, A Kolokolova, R Shaltiel, D Zuckerman Computational Complexity 24, 333-392, 2015 | 78 | 2015 |
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 | 67 | 2009 |
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 | 60 | 2009 |
Derandomization: A brief overview V Kabanets Current Trends in Theoretical Computer Science: The Challenge of the New …, 2002 | 58 | 2002 |
On the complexity of succinct zero-sum games L Fortnow, R Impagliazzo, V Kabanets, C Umans Computational Complexity 17 (3), 353-376, 2008 | 49 | 2008 |
The power of natural properties as oracles R Impagliazzo, V Kabanets, I Volkovich computational complexity 32 (2), 6, 2023 | 40 | 2023 |
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 | 35 | 2009 |
AC0 [p] lower bounds against MCSP via the coin problem A Golovnev, R Ilango, R Impagliazzo, V Kabanets, A Kolokolova, A Tal ICALP, 2019 | 33 | 2019 |
An axiomatic approach to algebrization R Impagliazzo, V Kabanets, A Kolokolova Proceedings of the forty-first annual ACM symposium on Theory of computing …, 2009 | 32 | 2009 |
Recognizability equals definability for partial k-paths V Kabanets International Colloquium on Automata, Languages, and Programming, 805-815, 1997 | 29 | 1997 |
The minimum oracle circuit size problem E Allender, D Holden, V Kabanets Computational Complexity 26, 469-496, 2017 | 28 | 2017 |
An improved deterministic# SAT algorithm for small De Morgan formulas R Chen, V Kabanets, N Saurabh Algorithmica 76, 68-87, 2016 | 28 | 2016 |