Recognizability Equals Definability for Partial k-Paths. - Valentine Kabanets (ICALP, 1997)

Almost k-Wise Independence and Boolean Functions Hard for Read-Once Branching Programs - Valentine Kabanets (Electron. Colloquium Comput. Complex., 1999)

Circuit Minimization Problem - Valentine Kabanets; Jin-yi Cai (Electron. Colloquium Comput. Complex., 1999)

Almost k-Wise Independence and Hard Boolean Functions. - Valentine Kabanets (LATIN, 2000)

Efficiently Approximable Real-Valued Functions - Valentine Kabanets; Charles Rackoff; Stephen A. Cook (Electron. Colloquium Comput. Complex., 2000)

Easiness Assumptions and Hardness Tests: Trading Time for Zero Error. - Valentine Kabanets (J. Comput. Syst. Sci., 2001)

Nonuniformly hard boolean functions and uniform complexity classes. - Valentine Kabanets (2001)

Derandomization: A Brief Overview - Valentine Kabanets (Electron. Colloquium Comput. Complex., 2002)

In search of an easy witness: exponential time vs. probabilistic polynomial time. - Russell Impagliazzo; Valentine Kabanets; Avi Wigderson (J. Comput. Syst. Sci., 2002)

Almost k-wise independence and hard Boolean functions. - Valentine Kabanets (Theor. Comput. Sci., 2003)

Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds. - Valentine Kabanets; Russell Impagliazzo (Comput. Complex., 2004)

Approximately List-Decoding Direct Product Codes and Uniform Hardness Amplification. - Russell Impagliazzo; Ragesh Jaiswal; Valentine Kabanets (FOCS, 2006)

Uniform Hardness Amplification in NP via Monotone Codes. - Joshua Buresh-Oppenheim; Valentine Kabanets; Rahul Santhanam (Electron. Colloquium Comput. Complex., 2006)

Special Issue "Conference on Computational Complexity 2006" Guest Editors' Foreword. - Venkatesan Guruswami; Valentine Kabanets (Comput. Complex., 2007)

On the Complexity of Succinct Zero-Sum Games. - Lance Fortnow; Russell Impagliazzo; Valentine Kabanets; Christopher Umans (Comput. Complex., 2008)

Hardness Amplification via Space-Efficient Direct Products. - Venkatesan Guruswami; Valentine Kabanets (Comput. Complex., 2008)

The complexity of Unique k-SAT: An Isolation Lemma for k-CNFs. - Chris Calabro; Russell Impagliazzo; Valentine Kabanets; Ramamohan Paturi (J. Comput. Syst. Sci., 2008)

An axiomatic approach to algebrization. - Russell Impagliazzo; Valentine Kabanets; Antonina Kolokolova (STOC, 2009)

Security Amplification for InteractiveCryptographic Primitives. - Yevgeniy Dodis; Russell Impagliazzo; Ragesh Jaiswal; Valentine Kabanets (TCC, 2009)

The Black-Box Query Complexity of Polynomial Summation. - Ali Juma; Valentine Kabanets; Charles Rackoff; Amir Shpilka (Comput. Complex., 2009)

Chernoff-Type Direct Product Theorems. - Russell Impagliazzo; Ragesh Jaiswal; Valentine Kabanets (J. Cryptol., 2009)

Approximate List-Decoding of Direct Product Codes and Uniform Hardness Amplification. - Russell Impagliazzo; Ragesh Jaiswal; Valentine Kabanets (SIAM J. Comput., 2009)

Constructive Proofs of Concentration Bounds. - Russell Impagliazzo; Valentine Kabanets (Electron. Colloquium Comput. Complex., 2010)

Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized. - Russell Impagliazzo; Ragesh Jaiswal; Valentine Kabanets; Avi Wigderson (SIAM J. Comput., 2010)

Is the Valiant-Vazirani Isolation Lemma Improvable? - Valentine Kabanets; Osamu Watanabe 001 (Electron. Colloquium Comput. Complex., 2011)

Lower Bounds against Weakly Uniform Circuits. - Ruiwen Chen; Valentine Kabanets (Electron. Colloquium Comput. Complex., 2012)

New Direct-Product Testers and 2-Query PCPs. - Russell Impagliazzo; Valentine Kabanets; Avi Wigderson (SIAM J. Comput., 2012)

Is Valiant-Vazirani's isolation probability improvable? - Holger Dell; Valentine Kabanets; Dieter van Melkebeek; Osamu Watanabe 001 (Comput. Complex., 2013)

An Improved Deterministic #SAT Algorithm for Small De Morgan Formulas. - Ruiwen Chen; Valentine Kabanets; Nitin Saurabh (Electron. Colloquium Comput. Complex., 2013)

Compression of Boolean Functions. - Valentine Kabanets; Antonina Kolokolova (Electron. Colloquium Comput. Complex., 2013)

Lower Bounds Against Weakly-Uniform Threshold Circuits. - Ruiwen Chen; Valentine Kabanets; Jeff Kinne (Algorithmica, 2014)

Algebra in Computational Complexity (Dagstuhl Seminar 14391). - Manindra Agrawal; Valentine Kabanets; Thomas Thierauf; Christopher Umans (Dagstuhl Reports, 2014)

Tighter Connections between Derandomization and Circuit Lower Bounds. - Marco Carmosino; Russell Impagliazzo; Valentine Kabanets; Antonina Kolokolova (APPROX-RANDOM, 2015)

Mining Circuit Lower Bound Proofs for Meta-Algorithms. - Ruiwen Chen; Valentine Kabanets; Antonina Kolokolova; Ronen Shaltiel; David Zuckerman (Comput. Complex., 2015)

Learning Algorithms from Natural Proofs. - Marco L. Carmosino; Russell Impagliazzo; Valentine Kabanets; Antonina Kolokolova (CCC, 2016)

Algebraic Methods in Computational Complexity (Dagstuhl Seminar 16411). - Valentine Kabanets; Thomas Thierauf; Jacobo Torán; Christopher Umans (Dagstuhl Reports, 2016)

Pseudorandomness when the odds are against you. - Sergei Artemenko; Russell Impagliazzo; Valentine Kabanets; Ronen Shaltiel (Electron. Colloquium Comput. Complex., 2016)

Expander Construction in VNC1. - Sam Buss; Valentine Kabanets; Antonina Kolokolova; Michal Koucký 001 (Electron. Colloquium Comput. Complex., 2016)

Algorithms from Natural Lower Bounds. - Marco L. Carmosino; Russell Impagliazzo; Valentine Kabanets; Antonina Kolokolova (Electron. Colloquium Comput. Complex., 2016)

Simultaneous Secrecy and Reliability Amplification for a General Channel Model. - Russell Impagliazzo; Ragesh Jaiswal; Valentine Kabanets; Bruce M. Kapron; Valerie King; Stefano Tessaro (IACR Cryptol. ePrint Arch., 2016)

Correlation bounds and #SAT algorithms for small linear-size circuits. - Ruiwen Chen; Valentine Kabanets (Theor. Comput. Sci., 2016)

Agnostic Learning from Tolerant Natural Proofs. - Marco L. Carmosino; Russell Impagliazzo; Valentine Kabanets; Antonina Kolokolova (APPROX-RANDOM, 2017)

Expander Construction in VNC1. - Sam Buss; Valentine Kabanets; Antonina Kolokolova; Michal Koucký 001 (ITCS, 2017)

The Minimum Oracle Circuit Size Problem. - Eric Allender; Dhiraj Holden; Valentine Kabanets (Comput. Complex., 2017)

Fourier Concentration from Shrinkage. - Russell Impagliazzo; Valentine Kabanets (Comput. Complex., 2017)

Does Looking Inside a Circuit Help? - Russell Impagliazzo; Valentine Kabanets; Antonina Kolokolova; Pierre McKenzie; Shadab Romani (Electron. Colloquium Comput. Complex., 2017)

A Polynomial Restriction Lemma with Applications. - Valentine Kabanets; Daniel M. Kane; Zhenjian Lu (Electron. Colloquium Comput. Complex., 2017)

Algebraic Methods in Computational Complexity (Dagstuhl Seminar 18391). - Markus Bläser; Valentine Kabanets; Jacobo Torán; Christopher Umans (Dagstuhl Reports, 2018)

Nisan-Wigderson Pseudorandom Generators for Circuits with Polynomial Threshold Gates. - Valentine Kabanets; Zhenjian Lu (Electron. Colloquium Comput. Complex., 2018)

Satisfiability and Derandomization for Small Polynomial Threshold Circuits. - Valentine Kabanets; Zhenjian Lu (Electron. Colloquium Comput. Complex., 2018)

AC0[p] Lower Bounds Against MCSP via the Coin Problem. - Alexander Golovnev; Rahul Ilango; Russell Impagliazzo; Valentine Kabanets; Antonina Kolokolova; Avishay Tal (ICALP, 2019)

Circuit Lower Bounds for MCSP from Local Pseudorandom Generators. - Mahdi Cheraghchi; Valentine Kabanets; Zhenjian Lu; Dimitrios Myrisiotis (Electron. Colloquium Comput. Complex., 2019)

AC0[p] Lower Bounds against MCSP via the Coin Problem. - Alexander Golovnev; Rahul Ilango; Russell Impagliazzo; Valentine Kabanets; Antonina Kolokolova; Avishay Tal (Electron. Colloquium Comput. Complex., 2019)

Algorithms and Lower Bounds for de Morgan Formulas of Low-Communication Leaf Gates. - Valentine Kabanets; Sajin Koroth; Zhenjian Lu; Dimitrios Myrisiotis; Igor C. Oliveira 001 (Electron. Colloquium Comput. Complex., 2020)

Special Section on the Fifty-Eighth Annual IEEE Symposium on Foundations of Computer Science (FOCS 2017). - Valentine Kabanets; Sofya Raskhodnikova; Chaitanya Swamy (SIAM J. Comput., 2020)

Lifting for Constant-Depth Circuits and Applications to MCSP. - Marco Carmosino; Kenneth Hoover; Russell Impagliazzo; Valentine Kabanets; Antonina Kolokolova (ICALP, 2021)

LEARN-Uniform Circuit Lower Bounds and Provability in Bounded Arithmetic. - Marco Carmosino; Valentine Kabanets; Antonina Kolokolova; Igor C. Oliveira 001 (Electron. Colloquium Comput. Complex., 2021)

A Simpler Proof of the Worst-Case to Average-Case Reduction for Polynomial Hierarchy via Symmetry of Information. - Halley Goldberg; Valentine Kabanets (Electron. Colloquium Comput. Complex., 2022)

Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity. - Halley Goldberg; Valentine Kabanets; Zhenjian Lu; Igor C. Oliveira 001 (Electron. Colloquium Comput. Complex., 2022)

Algebraic and Analytic Methods in Computational Complexity (Dagstuhl Seminar 22371). - Markus Bläser; Valentine Kabanets; Ronen Shaltiel; Jacobo Torán (Dagstuhl Reports, 2022)

Synergy Between Circuit Obfuscation and Circuit Minimization. - Russell Impagliazzo; Valentine Kabanets; Ilya Volkovich (APPROX/RANDOM, 2023)

Improved Learning from Kolmogorov Complexity. - Halley Goldberg; Valentine Kabanets (Electron. Colloquium Comput. Complex., 2023)

Mutual Empowerment between Circuit Obfuscation and Circuit Minimization. - Russell Impagliazzo; Valentine Kabanets; Ilya Volkovich (Electron. Colloquium Comput. Complex., 2023)

The Power of Natural Properties as Oracles. - Russell Impagliazzo; Valentine Kabanets; Ilya Volkovich (Comput. Complex., 2023)

Provability of the Circuit Size Hierarchy and Its Consequences. - Marco Carmosino; Valentine Kabanets; Antonina Kolokolova; Igor Carboni Oliveira; Dimitrios Tsintsilidas (Electron. Colloquium Comput. Complex., 2024)

Consequences of Randomized Reductions from SAT to Time-Bounded Kolmogorov Complexity. - Halley Goldberg; Valentine Kabanets (Electron. Colloquium Comput. Complex., 2024)

Exact Search-to-Decision Reductions for Time-Bounded Kolmogorov Complexity. - Shuichi Hirahara; Valentine Kabanets; Zhenjian Lu; Igor C. Oliveira 001 (Electron. Colloquium Comput. Complex., 2024)

Witness Encryption and NP-hardness of Learning. - Halley Goldberg; Valentine Kabanets (Electron. Colloquium Comput. Complex., 2025)

Chain Rules for Time-Bounded Kolmogorov Complexity. - Valentine Kabanets; Antonina Kolokolova (Electron. Colloquium Comput. Complex., 2025)