Valentine Kabanets

According to our database, Valentine Kabanets authored at least 67 papers between 1997 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2024

Exact Search-to-Decision Reductions for Time-Bounded Kolmogorov Complexity.

Shuichi Hirahara, Valentine Kabanets, Zhenjian Lu, Igor C. Oliveira

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

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

2023

The Power of Natural Properties as Oracles.

Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich

Comput. Complex., December, 2023

Mutual Empowerment between Circuit Obfuscation and Circuit Minimization.

Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich

Electron. Colloquium Comput. Complex., 2023

Improved Learning from Kolmogorov Complexity.

Halley Goldberg, Valentine Kabanets

Electron. Colloquium Comput. Complex., 2023

Synergy Between Circuit Obfuscation and Circuit Minimization.

Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich

Proceedings of the Approximation, 2023

2022

Algebraic and Analytic Methods in Computational Complexity (Dagstuhl Seminar 22371).

Markus Bläser, Valentine Kabanets, Ronen Shaltiel, Jacobo Torán

Dagstuhl Reports, September, 2022

Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity.

Halley Goldberg, Valentine Kabanets, Zhenjian Lu, Igor C. Oliveira

Electron. Colloquium Comput. Complex., 2022

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

2021

LEARN-Uniform Circuit Lower Bounds and Provability in Bounded Arithmetic.

Marco Carmosino, Valentine Kabanets, Antonina Kolokolova, Igor C. Oliveira

Electron. Colloquium Comput. Complex., 2021

Lifting for Constant-Depth Circuits and Applications to MCSP.

Marco Carmosino, Kenneth Hoover, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

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

Algorithms and Lower Bounds for de Morgan Formulas of Low-Communication Leaf Gates.

Valentine Kabanets, Sajin Koroth, Zhenjian Lu, Dimitrios Myrisiotis, Igor C. Oliveira

Electron. Colloquium Comput. Complex., 2020

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

Circuit Lower Bounds for MCSP from Local Pseudorandom Generators.

Mahdi Cheraghchi, Valentine Kabanets, Zhenjian Lu, Dimitrios Myrisiotis

Electron. Colloquium Comput. Complex., 2019

AC⁰[p] Lower Bounds Against MCSP via the Coin Problem.

Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Avishay Tal

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

2018

Satisfiability and Derandomization for Small Polynomial Threshold Circuits.

Valentine Kabanets, Zhenjian Lu

Electron. Colloquium Comput. Complex., 2018

Nisan-Wigderson Pseudorandom Generators for Circuits with Polynomial Threshold Gates.

Valentine Kabanets, Zhenjian Lu

Electron. Colloquium Comput. Complex., 2018

Algebraic Methods in Computational Complexity (Dagstuhl Seminar 18391).

Markus Bläser, Valentine Kabanets, Jacobo Torán, Christopher Umans

Dagstuhl Reports, 2018

2017

A Polynomial Restriction Lemma with Applications.

Valentine Kabanets, Daniel M. Kane, Zhenjian Lu

Electron. Colloquium Comput. Complex., 2017

Does Looking Inside a Circuit Help?

Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Pierre McKenzie, Shadab Romani

Electron. Colloquium Comput. Complex., 2017

Fourier Concentration from Shrinkage.

Russell Impagliazzo, Valentine Kabanets

Comput. Complex., 2017

The Minimum Oracle Circuit Size Problem.

Eric Allender, Dhiraj Holden, Valentine Kabanets

Comput. Complex., 2017

Expander Construction in VNC1.

Sam Buss, Valentine Kabanets, Antonina Kolokolova, Michal Koucký

Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

Agnostic Learning from Tolerant Natural Proofs.

Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova

Proceedings of the Approximation, 2017

2016

Correlation bounds and #SAT algorithms for small linear-size circuits.

Ruiwen Chen, Valentine Kabanets

Theor. Comput. Sci., 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

Algorithms from Natural Lower Bounds.

Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova

Electron. Colloquium Comput. Complex., 2016

Expander Construction in VNC¹.

Sam Buss, Valentine Kabanets, Antonina Kolokolova, Michal Koucký

Electron. Colloquium Comput. Complex., 2016

Pseudorandomness when the odds are against you.

Sergei Artemenko, Russell Impagliazzo, Valentine Kabanets, Ronen Shaltiel

Electron. Colloquium Comput. Complex., 2016

Algebraic Methods in Computational Complexity (Dagstuhl Seminar 16411).

Valentine Kabanets, Thomas Thierauf, Jacobo Torán, Christopher Umans

Dagstuhl Reports, 2016

Learning Algorithms from Natural Proofs.

Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova

Proceedings of the 31st Conference on Computational Complexity, 2016

2015

Mining Circuit Lower Bound Proofs for Meta-Algorithms.

Ruiwen Chen, Valentine Kabanets, Antonina Kolokolova, Ronen Shaltiel, David Zuckerman

Comput. Complex., 2015

Tighter Connections between Derandomization and Circuit Lower Bounds.

Marco Carmosino, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova

Proceedings of the Approximation, 2015

2014

Algebra in Computational Complexity (Dagstuhl Seminar 14391).

Manindra Agrawal, Valentine Kabanets, Thomas Thierauf, Christopher Umans

Dagstuhl Reports, 2014

Lower Bounds Against Weakly-Uniform Threshold Circuits.

Ruiwen Chen, Valentine Kabanets, Jeff Kinne

Algorithmica, 2014

2013

Compression of Boolean Functions.

Valentine Kabanets, Antonina Kolokolova

Electron. Colloquium Comput. Complex., 2013

An Improved Deterministic #SAT Algorithm for Small De Morgan Formulas.

Ruiwen Chen, Valentine Kabanets, Nitin Saurabh

Electron. Colloquium Comput. Complex., 2013

Is Valiant-Vazirani's isolation probability improvable?

Holger Dell, Valentine Kabanets, Dieter van Melkebeek, Osamu Watanabe

Comput. Complex., 2013

2012

New Direct-Product Testers and 2-Query PCPs.

Russell Impagliazzo, Valentine Kabanets, Avi Wigderson

SIAM J. Comput., 2012

Lower Bounds against Weakly Uniform Circuits.

Ruiwen Chen, Valentine Kabanets

Electron. Colloquium Comput. Complex., 2012

2011

Is the Valiant-Vazirani Isolation Lemma Improvable?

Valentine Kabanets, Osamu Watanabe

Electron. Colloquium Comput. Complex., 2011

2010

Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized.

Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Avi Wigderson

SIAM J. Comput., 2010

Constructive Proofs of Concentration Bounds.

Russell Impagliazzo, Valentine Kabanets

Electron. Colloquium Comput. Complex., 2010

2009

Approximate List-Decoding of Direct Product Codes and Uniform Hardness Amplification.

Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets

SIAM J. Comput., 2009

Chernoff-Type Direct Product Theorems.

Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets

J. Cryptol., 2009

The Black-Box Query Complexity of Polynomial Summation.

Ali Juma, Valentine Kabanets, Charles Rackoff, Amir Shpilka

Comput. Complex., 2009

Security Amplification for InteractiveCryptographic Primitives.

Yevgeniy Dodis, Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets

Proceedings of the Theory of Cryptography, 6th Theory of Cryptography Conference, 2009

An axiomatic approach to algebrization.

Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova

Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

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

Hardness Amplification via Space-Efficient Direct Products.

Venkatesan Guruswami, Valentine Kabanets

Comput. Complex., 2008

On the Complexity of Succinct Zero-Sum Games.

Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, Christopher Umans

Comput. Complex., 2008

2007

Special Issue "Conference on Computational Complexity 2006" Guest Editors' Foreword.

Venkatesan Guruswami, Valentine Kabanets

Comput. Complex., 2007

2006

Uniform Hardness Amplification in NP via Monotone Codes.

Joshua Buresh-Oppenheim, Valentine Kabanets, Rahul Santhanam

Electron. Colloquium Comput. Complex., 2006

Approximately List-Decoding Direct Product Codes and Uniform Hardness Amplification.

Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets

Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

2004

Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds.

Valentine Kabanets, Russell Impagliazzo

Comput. Complex., 2004

2003

Almost k-wise independence and hard Boolean functions.

Valentine Kabanets

Theor. Comput. Sci., 2003

2002

In search of an easy witness: exponential time vs. probabilistic polynomial time.

Russell Impagliazzo, Valentine Kabanets, Avi Wigderson

J. Comput. Syst. Sci., 2002

Derandomization: A Brief Overview

Valentine Kabanets

Electron. Colloquium Comput. Complex., 2002

2001

Nonuniformly hard boolean functions and uniform complexity classes.

Valentine Kabanets

PhD thesis, 2001

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

Valentine Kabanets

J. Comput. Syst. Sci., 2001

2000

Efficiently Approximable Real-Valued Functions

Valentine Kabanets, Charles Rackoff, Stephen A. Cook

Electron. Colloquium Comput. Complex., 2000

Almost <i>k</i>-Wise Independence and Hard Boolean Functions.

Valentine Kabanets

Proceedings of the LATIN 2000: Theoretical Informatics, 2000

1999

Circuit Minimization Problem

Valentine Kabanets, Jin-yi Cai

Electron. Colloquium Comput. Complex., 1999

Almost k-Wise Independence and Boolean Functions Hard for Read-Once Branching Programs

Valentine Kabanets

Electron. Colloquium Comput. Complex., 1999

1997

Recognizability Equals Definability for Partial k-Paths.

Valentine Kabanets

Proceedings of the Automata, Languages and Programming, 24th International Colloquium, 1997