Valentine Kabanets

Publication Activity (10 Years)

Years Active: 1997-2024
Publications (10 Years): 51

Top Venues

Electron. Colloquium Comput. Complex.

Computational Complexity Conference

Comput. Complex.

Dagstuhl Reports

Publications

Halley Goldberg, Valentine Kabanets
Consequences of Randomized Reductions from SAT to Time-Bounded Kolmogorov Complexity. Electron. Colloquium Comput. Complex. (2024)
Shuichi Hirahara, Valentine Kabanets, Zhenjian Lu, Igor C. Oliveira
Exact Search-to-Decision Reductions for Time-Bounded Kolmogorov Complexity. Electron. Colloquium Comput. Complex. (2024)
Shuichi Hirahara, Valentine Kabanets, Zhenjian Lu, Igor C. Oliveira
Exact Search-To-Decision Reductions for Time-Bounded Kolmogorov Complexity. CCC (2024)
Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich
The Power of Natural Properties as Oracles. Comput. Complex. 32 (2) (2023)
Halley Goldberg, Valentine Kabanets
Improved Learning from Kolmogorov Complexity. CCC (2023)
Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich
Synergy Between Circuit Obfuscation and Circuit Minimization. APPROX/RANDOM (2023)
Halley Goldberg, Valentine Kabanets
Improved Learning from Kolmogorov Complexity. Electron. Colloquium Comput. Complex. (2023)
Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich
Mutual Empowerment between Circuit Obfuscation and Circuit Minimization. Electron. Colloquium Comput. Complex. (2023)
Halley Goldberg, Valentine Kabanets, Zhenjian Lu, Igor Carboni Oliveira
Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity. Electron. Colloquium Comput. Complex. (2022)
Markus Bläser, Valentine Kabanets, Ronen Shaltiel, Jacobo Torán
Algebraic and Analytic Methods in Computational Complexity (Dagstuhl Seminar 22371). Dagstuhl Reports 12 (9) (2022)
Marco Carmosino, Valentine Kabanets, Antonina Kolokolova, Igor Carboni Oliveira
LEARN-Uniform Circuit Lower Bounds and Provability in Bounded Arithmetic. FOCS (2022)
Halley Goldberg, Valentine Kabanets
A Simpler Proof of the Worst-Case to Average-Case Reduction for Polynomial Hierarchy via Symmetry of Information. Electron. Colloquium Comput. Complex. 29 (2022)
Halley Goldberg, Valentine Kabanets, Zhenjian Lu, Igor Carboni Oliveira
Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity. CCC (2022)
Marco Carmosino, Kenneth Hoover, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova
Lifting for Constant-Depth Circuits and Applications to MCSP. ICALP (2021)
Marco Carmosino, Valentine Kabanets, Antonina Kolokolova, Igor Carboni Oliveira
LEARN-Uniform Circuit Lower Bounds and Provability in Bounded Arithmetic. FOCS (2021)
Marco Carmosino, Valentine Kabanets, Antonina Kolokolova, Igor Carboni Oliveira
LEARN-Uniform Circuit Lower Bounds and Provability in Bounded Arithmetic. Electron. Colloquium Comput. Complex. 28 (2021)
Valentine Kabanets, Sajin Koroth, Zhenjian Lu, Dimitrios Myrisiotis, Igor Carboni Oliveira
Algorithms and Lower Bounds for De Morgan Formulas of Low-Communication Leaf Gates. ACM Trans. Comput. Theory 13 (4) (2021)
Valentine Kabanets, Sofya Raskhodnikova, Chaitanya Swamy
Special Section on the Fifty-Eighth Annual IEEE Symposium on Foundations of Computer Science (FOCS 2017). SIAM J. Comput. 49 (4) (2020)
Valentine Kabanets, Sajin Koroth, Zhenjian Lu, Dimitrios Myrisiotis, Igor Carboni Oliveira
Algorithms and Lower Bounds for de Morgan Formulas of Low-Communication Leaf Gates. CoRR (2020)
Sam Buss, Valentine Kabanets, Antonina Kolokolova, Michal Koucký
. Ann. Pure Appl. Log. 171 (7) (2020)
Valentine Kabanets, Sajin Koroth, Zhenjian Lu, Dimitrios Myrisiotis, Igor Carboni Oliveira
Algorithms and Lower Bounds for De Morgan Formulas of Low-Communication Leaf Gates. Computational Complexity Conference (2020)
Mahdi Cheraghchi, Valentine Kabanets, Zhenjian Lu, Dimitrios Myrisiotis
Circuit Lower Bounds for MCSP from Local Pseudorandom Generators. ACM Trans. Comput. Theory 12 (3) (2020)
Valentine Kabanets, Sajin Koroth, Zhenjian Lu, Dimitrios Myrisiotis, Igor Carboni Oliveira
Algorithms and Lower Bounds for de Morgan Formulas of Low-Communication Leaf Gates. Electron. Colloquium Comput. Complex. 27 (2020)
Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Avishay Tal
[p] Lower Bounds Against MCSP via the Coin Problem. ICALP (2019)
Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Avishay Tal
AC0[p] Lower Bounds against MCSP via the Coin Problem. Electron. Colloquium Comput. Complex. 26 (2019)
Mahdi Cheraghchi, Valentine Kabanets, Zhenjian Lu, Dimitrios Myrisiotis
Circuit Lower Bounds for MCSP from Local Pseudorandom Generators. Electron. Colloquium Comput. Complex. 26 (2019)
Mahdi Cheraghchi, Valentine Kabanets, Zhenjian Lu, Dimitrios Myrisiotis
Circuit Lower Bounds for MCSP from Local Pseudorandom Generators. ICALP (2019)
Valentine Kabanets, Zhenjian Lu
Nisan-Wigderson Pseudorandom Generators for Circuits with Polynomial Threshold Gates. Electron. Colloquium Comput. Complex. 25 (2018)
Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich
The Power of Natural Properties as Oracles. Computational Complexity Conference (2018)
Valentine Kabanets, Zhenjian Lu
Satisfiability and Derandomization for Small Polynomial Threshold Circuits. APPROX-RANDOM (2018)
Valentine Kabanets, Zhenjian Lu
Satisfiability and Derandomization for Small Polynomial Threshold Circuits. Electron. Colloquium Comput. Complex. 25 (2018)
Markus Bläser, Valentine Kabanets, Jacobo Torán, Christopher Umans
Algebraic Methods in Computational Complexity (Dagstuhl Seminar 18391). Dagstuhl Reports 8 (9) (2018)
Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova
Agnostic Learning from Tolerant Natural Proofs. APPROX-RANDOM (2017)
Eric Allender, Dhiraj Holden, Valentine Kabanets
The Minimum Oracle Circuit Size Problem. Comput. Complex. 26 (2) (2017)
Valentine Kabanets, Daniel M. Kane, Zhenjian Lu
A polynomial restriction lemma with applications. STOC (2017)
Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Pierre McKenzie, Shadab Romani
Does Looking Inside a Circuit Help?. MFCS (2017)
Valentine Kabanets, Daniel M. Kane, Zhenjian Lu
A Polynomial Restriction Lemma with Applications. Electron. Colloquium Comput. Complex. 24 (2017)
Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Pierre McKenzie, Shadab Romani
Does Looking Inside a Circuit Help? Electron. Colloquium Comput. Complex. 24 (2017)
Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich
The Power of Natural Properties as Oracles. Electron. Colloquium Comput. Complex. 24 (2017)
Sam Buss, Valentine Kabanets, Antonina Kolokolova, Michal Koucký
Expander Construction in VNC1. ITCS (2017)
Russell Impagliazzo, Valentine Kabanets
Fourier Concentration from Shrinkage. Comput. Complex. 26 (1) (2017)
Sergei Artemenko, Russell Impagliazzo, Valentine Kabanets, Ronen Shaltiel
Pseudorandomness When the Odds are Against You. Computational Complexity Conference (2016)
Ruiwen Chen, Valentine Kabanets
Correlation bounds and #SAT algorithms for small linear-size circuits. Theor. Comput. Sci. 654 (2016)
Sergei Artemenko, Russell Impagliazzo, Valentine Kabanets, Ronen Shaltiel
Pseudorandomness when the odds are against you. Electron. Colloquium Comput. Complex. 23 (2016)
Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova
Algorithms from Natural Lower Bounds. Electron. Colloquium Comput. Complex. 23 (2016)
Valentine Kabanets, Thomas Thierauf, Jacobo Torán, Christopher Umans
Algebraic Methods in Computational Complexity (Dagstuhl Seminar 16411). Dagstuhl Reports 6 (10) (2016)
Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Bruce M. Kapron, Valerie King, Stefano Tessaro
Simultaneous Secrecy and Reliability Amplification for a General Channel Model. TCC (B1) (2016)
Ruiwen Chen, Valentine Kabanets, Nitin Saurabh
An Improved Deterministic #SAT Algorithm for Small de Morgan Formulas. Algorithmica 76 (1) (2016)
Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Bruce M. Kapron, Valerie King, Stefano Tessaro
Simultaneous Secrecy and Reliability Amplification for a General Channel Model. IACR Cryptol. ePrint Arch. 2016 (2016)
Sam Buss, Valentine Kabanets, Antonina Kolokolova, Michal Koucký
. Electron. Colloquium Comput. Complex. 23 (2016)
Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova
Learning Algorithms from Natural Proofs. Computational Complexity Conference (2016)
Ruiwen Chen, Valentine Kabanets
Correlation Bounds and #SAT Algorithms for Small Linear-Size Circuits. COCOON (2015)
Marco Carmosino, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova
Tighter Connections between Derandomization and Circuit Lower Bounds. APPROX-RANDOM (2015)
Eric Allender, Dhiraj Holden, Valentine Kabanets
The Minimum Oracle Circuit Size Problem. STACS (2015)
Ruiwen Chen, Valentine Kabanets, Antonina Kolokolova, Ronen Shaltiel, David Zuckerman
Mining Circuit Lower Bound Proofs for Meta-Algorithms. Comput. Complex. 24 (2) (2015)
Ruiwen Chen, Valentine Kabanets, Antonina Kolokolova, Ronen Shaltiel, David Zuckerman
Mining Circuit Lower Bound Proofs for Meta-algorithms. Computational Complexity Conference (2014)
Ruiwen Chen, Valentine Kabanets, Nitin Saurabh
An Improved Deterministic #SAT Algorithm for Small De Morgan Formulas. MFCS (2) (2014)
Ruiwen Chen, Valentine Kabanets, Jeff Kinne
Lower Bounds Against Weakly-Uniform Threshold Circuits. Algorithmica 70 (1) (2014)
Russell Impagliazzo, Valentine Kabanets
Fourier Concentration from Shrinkage. Computational Complexity Conference (2014)
Manindra Agrawal, Valentine Kabanets, Thomas Thierauf, Christopher Umans
Algebra in Computational Complexity (Dagstuhl Seminar 14391). Dagstuhl Reports 4 (9) (2014)
Ruiwen Chen, Valentine Kabanets
Correlation Bounds and #SAT Algorithms for Small Linear-Size Circuits. Electron. Colloquium Comput. Complex. 21 (2014)
Eric Allender, Dhiraj Holden, Valentine Kabanets
The Minimum Oracle Circuit Size Problem. Electron. Colloquium Comput. Complex. 21 (2014)
Holger Dell, Valentine Kabanets, Dieter van Melkebeek, Osamu Watanabe
Is Valiant-Vazirani's isolation probability improvable? Comput. Complex. 22 (2) (2013)
Ruiwen Chen, Valentine Kabanets, Nitin Saurabh
An Improved Deterministic #SAT Algorithm for Small De Morgan Formulas. Electron. Colloquium Comput. Complex. 20 (2013)
Valentine Kabanets, Antonina Kolokolova
Compression of Boolean Functions. Electron. Colloquium Comput. Complex. 20 (2013)
Ruiwen Chen, Valentine Kabanets, Antonina Kolokolova, Ronen Shaltiel, David Zuckerman
Mining Circuit Lower Bound Proofs for Meta-Algorithms. Electron. Colloquium Comput. Complex. 20 (2013)
Russell Impagliazzo, Valentine Kabanets
Fourier Concentration from Shrinkage. Electron. Colloquium Comput. Complex. 20 (2013)
Ruiwen Chen, Valentine Kabanets
Lower Bounds against Weakly Uniform Circuits. COCOON (2012)
Holger Dell, Valentine Kabanets, Dieter van Melkebeek, Osamu Watanabe
Is Valiant-Vazirani's Isolation Probability Improvable? Computational Complexity Conference (2012)
Ruiwen Chen, Valentine Kabanets
Lower Bounds against Weakly Uniform Circuits. Electron. Colloquium Comput. Complex. 19 (2012)
Russell Impagliazzo, Valentine Kabanets, Avi Wigderson
New Direct-Product Testers and 2-Query PCPs. SIAM J. Comput. 41 (6) (2012)
Valentine Kabanets, Osamu Watanabe
Is the Valiant-Vazirani Isolation Lemma Improvable? Electron. Colloquium Comput. Complex. 18 (2011)
Russell Impagliazzo, Valentine Kabanets
Constructive Proofs of Concentration Bounds. APPROX-RANDOM (2010)
Russell Impagliazzo, Valentine Kabanets
Constructive Proofs of Concentration Bounds. Electron. Colloquium Comput. Complex. 17 (2010)
Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Avi Wigderson
Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized. SIAM J. Comput. 39 (4) (2010)
Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets
Chernoff-Type Direct Product Theorems. J. Cryptol. 22 (1) (2009)
Russell Impagliazzo, Valentine Kabanets, Avi Wigderson
New Direct-Product Testers and 2-Query PCPs. Electron. Colloquium Comput. Complex. 16 (2009)
Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets
Approximate List-Decoding of Direct Product Codes and Uniform Hardness Amplification. SIAM J. Comput. 39 (2) (2009)
Ali Juma, Valentine Kabanets, Charles Rackoff, Amir Shpilka
The Black-Box Query Complexity of Polynomial Summation. Comput. Complex. 18 (1) (2009)
Yevgeniy Dodis, Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets
Security Amplification for InteractiveCryptographic Primitives. TCC (2009)
Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova
An Axiomatic Approach to Algebrization. Algebraic Methods in Computational Complexity (2009)
Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova
An axiomatic approach to algebrization. STOC (2009)
Russell Impagliazzo, Valentine Kabanets, Avi Wigderson
New direct-product testers and 2-query PCPs. STOC (2009)
Venkatesan Guruswami, Valentine Kabanets
Hardness Amplification via Space-Efficient Direct Products. Comput. Complex. 17 (4) (2008)
Chris Calabro, Russell Impagliazzo, Valentine Kabanets, Ramamohan Paturi
The complexity of Unique k-SAT: An Isolation Lemma for k-CNFs. J. Comput. Syst. Sci. 74 (3) (2008)
Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Avi Wigderson
Uniform Direct-Product Theorems: Simplified, Optimized, and Derandomized. Electron. Colloquium Comput. Complex. 15 (079) (2008)
Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, Christopher Umans
On the Complexity of Succinct Zero-Sum Games. Comput. Complex. 17 (3) (2008)
Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Avi Wigderson
Uniform direct product theorems: simplified, optimized, and derandomized. STOC (2008)
Venkatesan Guruswami, Valentine Kabanets
Special Issue "Conference on Computational Complexity 2006" Guest Editors' Foreword. Comput. Complex. 16 (2) (2007)
Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets
Chernoff-Type Direct Product Theorems. CRYPTO (2007)
Ali Juma, Valentine Kabanets, Charles Rackoff, Amir Shpilka
The black-box query complexity of polynomial summation. Electron. Colloquium Comput. Complex. 14 (125) (2007)
Venkatesan Guruswami, Valentine Kabanets
Hardness Amplification Via Space-Efficient Direct Products. LATIN (2006)
Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets
Approximately List-Decoding Direct Product Codes and Uniform Hardness Amplification. FOCS (2006)
Joshua Buresh-Oppenheim, Valentine Kabanets, Rahul Santhanam
Uniform Hardness Amplification in NP via Monotone Codes. Electron. Colloquium Comput. Complex. 13 (154) (2006)
Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, Christopher Umans
On the Complexity of Succinct Zero-Sum Games. Computational Complexity Conference (2005)
Venkatesan Guruswami, Valentine Kabanets
Hardness amplification via space-efficient direct products Electron. Colloquium Comput. Complex. (057) (2005)
Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, Christopher Umans
On the complexity of succinct zero-sum games Electron. Colloquium Comput. Complex. (001) (2004)
Valentine Kabanets, Russell Impagliazzo
Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds. Comput. Complex. 13 (1-2) (2004)
Chris Calabro, Russell Impagliazzo, Valentine Kabanets, Ramamohan Paturi
The Complexity of Unique k-SAT: An Isolation Lemma for k-CNFs. Computational Complexity Conference (2003)
Valentine Kabanets, Russell Impagliazzo
Derandomizing polynomial identity tests means proving circuit lower bounds. STOC (2003)

Valentine Kabanets.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Valentine Kabanets