Valentine Kabanets

123 papers A* 13A 21B 4Misc 2Journal 75Unranked 7

Year	Rank	Type	Title / Venue / Authors
2025	J	`jnl`	A Logspace Constructive Proof of L=SL. CoRR Sam Buss, Anant Dhayal, Valentine Kabanets, Antonina Kolokolova, Sasank Mouli
2025	J	`jnl`	A Logspace Constructive Proof of L=SL. Electron. Colloquium Comput. Complex. Sam Buss, Anant Dhayal, Valentine Kabanets, Antonina Kolokolova, Sasank Mouli
2025	J	`jnl`	Chain Rules for Time-Bounded Kolmogorov Complexity. Electron. Colloquium Comput. Complex. Valentine Kabanets, Antonina Kolokolova
2025	A	`conf`	Provability of the Circuit Size Hierarchy and Its Consequences. ITCS Marco Carmosino, Valentine Kabanets, Antonina Kolokolova, Igor C. Oliveira, Dimitrios Tsintsilidas
2025	A	`conf`	Witness Encryption and NP-Hardness of Learning. CCC Halley Goldberg, Valentine Kabanets
2025	J	`jnl`	Witness Encryption and NP-hardness of Learning. Electron. Colloquium Comput. Complex. Halley Goldberg, Valentine Kabanets
2024	A	`conf`	Consequences of Randomized Reductions from SAT to Time-Bounded Kolmogorov Complexity. APPROX/RANDOM Halley Goldberg, Valentine Kabanets
2024	J	`jnl`	Consequences of Randomized Reductions from SAT to Time-Bounded Kolmogorov Complexity. Electron. Colloquium Comput. Complex. Halley Goldberg, Valentine Kabanets
2024	A	`conf`	Exact Search-To-Decision Reductions for Time-Bounded Kolmogorov Complexity. CCC Shuichi Hirahara, Valentine Kabanets, Zhenjian Lu, Igor C. Oliveira
2024	J	`jnl`	Exact Search-to-Decision Reductions for Time-Bounded Kolmogorov Complexity. Electron. Colloquium Comput. Complex. Shuichi Hirahara, Valentine Kabanets, Zhenjian Lu, Igor C. Oliveira
2024	J	`jnl`	Provability of the Circuit Size Hierarchy and Its Consequences. Electron. Colloquium Comput. Complex. Marco Carmosino, Valentine Kabanets, Antonina Kolokolova, Igor Carboni Oliveira, Dimitrios Tsintsilidas
2023	A	`conf`	Improved Learning from Kolmogorov Complexity. CCC Halley Goldberg, Valentine Kabanets
2023	J	`jnl`	Improved Learning from Kolmogorov Complexity. Electron. Colloquium Comput. Complex. Halley Goldberg, Valentine Kabanets
2023	J	`jnl`	Mutual Empowerment between Circuit Obfuscation and Circuit Minimization. Electron. Colloquium Comput. Complex. Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich
2023	A	`conf`	Synergy Between Circuit Obfuscation and Circuit Minimization. APPROX/RANDOM Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich
2023	J	`jnl`	The Power of Natural Properties as Oracles. Comput. Complex. Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich
2022	J	`jnl`	A Simpler Proof of the Worst-Case to Average-Case Reduction for Polynomial Hierarchy via Symmetry of Information. Electron. Colloquium Comput. Complex. Halley Goldberg, Valentine Kabanets
2022	J	`jnl`	Algebraic and Analytic Methods in Computational Complexity (Dagstuhl Seminar 22371). Dagstuhl Reports Markus Bläser, Valentine Kabanets, Ronen Shaltiel, Jacobo Torán
2022	A	`conf`	Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity. CCC Halley Goldberg, Valentine Kabanets, Zhenjian Lu, Igor C. Oliveira
2022	J	`jnl`	Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity. Electron. Colloquium Comput. Complex. Halley Goldberg, Valentine Kabanets, Zhenjian Lu, Igor C. Oliveira
2021	A	`ed.`	36th Computational Complexity Conference, CCC 2021, Toronto, Ontario, Canada (Virtual Conference), July 20-23, 2021 CCC Valentine Kabanets
2021	J	`jnl`	Algorithms and Lower Bounds for De Morgan Formulas of Low-Communication Leaf Gates. ACM Trans. Comput. Theory Valentine Kabanets, Sajin Koroth, Zhenjian Lu, Dimitrios Myrisiotis, Igor C. Oliveira
2021	A*	`conf`	LEARN-Uniform Circuit Lower Bounds and Provability in Bounded Arithmetic. FOCS Marco Carmosino, Valentine Kabanets, Antonina Kolokolova, Igor C. Oliveira
2021	J	`jnl`	LEARN-Uniform Circuit Lower Bounds and Provability in Bounded Arithmetic. Electron. Colloquium Comput. Complex. Marco Carmosino, Valentine Kabanets, Antonina Kolokolova, Igor C. Oliveira
2021	A*	`conf`	Lifting for Constant-Depth Circuits and Applications to MCSP. ICALP Marco Carmosino, Kenneth Hoover, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova
2020	A	`conf`	Algorithms and Lower Bounds for De Morgan Formulas of Low-Communication Leaf Gates. CCC Valentine Kabanets, Sajin Koroth, Zhenjian Lu, Dimitrios Myrisiotis, Igor C. Oliveira
2020	J	`jnl`	Algorithms and Lower Bounds for de Morgan Formulas of Low-Communication Leaf Gates. CoRR Valentine Kabanets, Sajin Koroth, Zhenjian Lu, Dimitrios Myrisiotis, Igor C. Oliveira
2020	J	`jnl`	Algorithms and Lower Bounds for de Morgan Formulas of Low-Communication Leaf Gates. Electron. Colloquium Comput. Complex. Valentine Kabanets, Sajin Koroth, Zhenjian Lu, Dimitrios Myrisiotis, Igor C. Oliveira
2020	J	`jnl`	Circuit Lower Bounds for MCSP from Local Pseudorandom Generators. ACM Trans. Comput. Theory Mahdi Cheraghchi, Valentine Kabanets, Zhenjian Lu, Dimitrios Myrisiotis
2020	J	`jnl`	Expander construction in VNC Ann. Pure Appl. Log. Sam Buss, Valentine Kabanets, Antonina Kolokolova, Michal Koucký
2020	J	`jnl`	Special Section on the Fifty-Eighth Annual IEEE Symposium on Foundations of Computer Science (FOCS 2017). SIAM J. Comput. Valentine Kabanets, Sofya Raskhodnikova, Chaitanya Swamy
2019	A*	`conf`	AC ICALP Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Avishay Tal
2019	J	`jnl`	AC0[p] Lower Bounds against MCSP via the Coin Problem. Electron. Colloquium Comput. Complex. Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Avishay Tal
2019	A*	`conf`	Circuit Lower Bounds for MCSP from Local Pseudorandom Generators. ICALP Mahdi Cheraghchi, Valentine Kabanets, Zhenjian Lu, Dimitrios Myrisiotis
2019	J	`jnl`	Circuit Lower Bounds for MCSP from Local Pseudorandom Generators. Electron. Colloquium Comput. Complex. Mahdi Cheraghchi, Valentine Kabanets, Zhenjian Lu, Dimitrios Myrisiotis
2018	J	`jnl`	Algebraic Methods in Computational Complexity (Dagstuhl Seminar 18391). Dagstuhl Reports Markus Bläser, Valentine Kabanets, Jacobo Torán, Christopher Umans
2018	J	`jnl`	Nisan-Wigderson Pseudorandom Generators for Circuits with Polynomial Threshold Gates. Electron. Colloquium Comput. Complex. Valentine Kabanets, Zhenjian Lu
2018	—	`conf`	Satisfiability and Derandomization for Small Polynomial Threshold Circuits. APPROX-RANDOM Valentine Kabanets, Zhenjian Lu
2018	J	`jnl`	Satisfiability and Derandomization for Small Polynomial Threshold Circuits. Electron. Colloquium Comput. Complex. Valentine Kabanets, Zhenjian Lu
2018	A	`conf`	The Power of Natural Properties as Oracles. CCC Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich
2017	J	`jnl`	A Polynomial Restriction Lemma with Applications. Electron. Colloquium Comput. Complex. Valentine Kabanets, Daniel M. Kane, Zhenjian Lu
2017	A*	`conf`	A polynomial restriction lemma with applications. STOC Valentine Kabanets, Daniel M. Kane, Zhenjian Lu
2017	—	`conf`	Agnostic Learning from Tolerant Natural Proofs. APPROX-RANDOM Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova
2017	J	`jnl`	Does Looking Inside a Circuit Help? Electron. Colloquium Comput. Complex. Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Pierre McKenzie, Shadab Romani
2017	B	`conf`	Does Looking Inside a Circuit Help?. MFCS Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Pierre McKenzie, Shadab Romani
2017	A	`conf`	Expander Construction in VNC1. ITCS Sam Buss, Valentine Kabanets, Antonina Kolokolova, Michal Koucký
2017	J	`jnl`	Fourier Concentration from Shrinkage. Comput. Complex. Russell Impagliazzo, Valentine Kabanets
2017	J	`jnl`	The Minimum Oracle Circuit Size Problem. Comput. Complex. Eric Allender, Dhiraj Holden, Valentine Kabanets
2017	J	`jnl`	The Power of Natural Properties as Oracles. Electron. Colloquium Comput. Complex. Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich
2016	J	`jnl`	Algebraic Methods in Computational Complexity (Dagstuhl Seminar 16411). Dagstuhl Reports Valentine Kabanets, Thomas Thierauf, Jacobo Torán, Christopher Umans
2016	J	`jnl`	Algorithms from Natural Lower Bounds. Electron. Colloquium Comput. Complex. Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova
2016	J	`jnl`	An Improved Deterministic #SAT Algorithm for Small de Morgan Formulas. Algorithmica Ruiwen Chen, Valentine Kabanets, Nitin Saurabh
2016	J	`jnl`	Correlation bounds and #SAT algorithms for small linear-size circuits. Theor. Comput. Sci. Ruiwen Chen, Valentine Kabanets
2016	J	`jnl`	Expander Construction in VNC Electron. Colloquium Comput. Complex. Sam Buss, Valentine Kabanets, Antonina Kolokolova, Michal Koucký
2016	A	`conf`	Learning Algorithms from Natural Proofs. CCC Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova
2016	A	`conf`	Pseudorandomness When the Odds are Against You. CCC Sergei Artemenko, Russell Impagliazzo, Valentine Kabanets, Ronen Shaltiel
2016	J	`jnl`	Pseudorandomness when the odds are against you. Electron. Colloquium Comput. Complex. Sergei Artemenko, Russell Impagliazzo, Valentine Kabanets, Ronen Shaltiel
2016	—	`conf`	Simultaneous Secrecy and Reliability Amplification for a General Channel Model. TCC (B1) Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Bruce M. Kapron, Valerie King, Stefano Tessaro
2016	J	`jnl`	Simultaneous Secrecy and Reliability Amplification for a General Channel Model. IACR Cryptol. ePrint Arch. Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Bruce M. Kapron, Valerie King, Stefano Tessaro
2015	Misc	`conf`	Correlation Bounds and #SAT Algorithms for Small Linear-Size Circuits. COCOON Ruiwen Chen, Valentine Kabanets
2015	J	`jnl`	Mining Circuit Lower Bound Proofs for Meta-Algorithms. Comput. Complex. Ruiwen Chen, Valentine Kabanets, Antonina Kolokolova, Ronen Shaltiel, David Zuckerman
2015	A	`conf`	The Minimum Oracle Circuit Size Problem. STACS Eric Allender, Dhiraj Holden, Valentine Kabanets
2015	—	`conf`	Tighter Connections between Derandomization and Circuit Lower Bounds. APPROX-RANDOM Marco Carmosino, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova
2014	J	`jnl`	Algebra in Computational Complexity (Dagstuhl Seminar 14391). Dagstuhl Reports Manindra Agrawal, Valentine Kabanets, Thomas Thierauf, Christopher Umans
2014	—	`conf`	An Improved Deterministic #SAT Algorithm for Small De Morgan Formulas. MFCS (2) Ruiwen Chen, Valentine Kabanets, Nitin Saurabh
2014	J	`jnl`	Correlation Bounds and #SAT Algorithms for Small Linear-Size Circuits. Electron. Colloquium Comput. Complex. Ruiwen Chen, Valentine Kabanets
2014	A	`conf`	Fourier Concentration from Shrinkage. CCC Russell Impagliazzo, Valentine Kabanets
2014	J	`jnl`	Lower Bounds Against Weakly-Uniform Threshold Circuits. Algorithmica Ruiwen Chen, Valentine Kabanets, Jeff Kinne
2014	A	`conf`	Mining Circuit Lower Bound Proofs for Meta-algorithms. CCC Ruiwen Chen, Valentine Kabanets, Antonina Kolokolova, Ronen Shaltiel, David Zuckerman
2014	J	`jnl`	The Minimum Oracle Circuit Size Problem. Electron. Colloquium Comput. Complex. Eric Allender, Dhiraj Holden, Valentine Kabanets
2013	J	`jnl`	An Improved Deterministic #SAT Algorithm for Small De Morgan Formulas. Electron. Colloquium Comput. Complex. Ruiwen Chen, Valentine Kabanets, Nitin Saurabh
2013	J	`jnl`	Compression of Boolean Functions. Electron. Colloquium Comput. Complex. Valentine Kabanets, Antonina Kolokolova
2013	J	`jnl`	Fourier Concentration from Shrinkage. Electron. Colloquium Comput. Complex. Russell Impagliazzo, Valentine Kabanets
2013	J	`jnl`	Is Valiant-Vazirani's isolation probability improvable? Comput. Complex. Holger Dell, Valentine Kabanets, Dieter van Melkebeek, Osamu Watanabe
2013	J	`jnl`	Mining Circuit Lower Bound Proofs for Meta-Algorithms. Electron. Colloquium Comput. Complex. Ruiwen Chen, Valentine Kabanets, Antonina Kolokolova, Ronen Shaltiel, David Zuckerman
2012	A	`conf`	Is Valiant-Vazirani's Isolation Probability Improvable? CCC Holger Dell, Valentine Kabanets, Dieter van Melkebeek, Osamu Watanabe
2012	Misc	`conf`	Lower Bounds against Weakly Uniform Circuits. COCOON Ruiwen Chen, Valentine Kabanets
2012	J	`jnl`	Lower Bounds against Weakly Uniform Circuits. Electron. Colloquium Comput. Complex. Ruiwen Chen, Valentine Kabanets
2012	J	`jnl`	New Direct-Product Testers and 2-Query PCPs. SIAM J. Comput. Russell Impagliazzo, Valentine Kabanets, Avi Wigderson
2011	J	`jnl`	Is the Valiant-Vazirani Isolation Lemma Improvable? Electron. Colloquium Comput. Complex. Valentine Kabanets, Osamu Watanabe
2010	—	`conf`	Constructive Proofs of Concentration Bounds. APPROX-RANDOM Russell Impagliazzo, Valentine Kabanets
2010	J	`jnl`	Constructive Proofs of Concentration Bounds. Electron. Colloquium Comput. Complex. Russell Impagliazzo, Valentine Kabanets
2010	J	`jnl`	Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized. SIAM J. Comput. Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Avi Wigderson
2009	—	`conf`	An Axiomatic Approach to Algebrization. Algebraic Methods in Computational Complexity Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova
2009	A*	`conf`	An axiomatic approach to algebrization. STOC Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova
2009	J	`jnl`	Approximate List-Decoding of Direct Product Codes and Uniform Hardness Amplification. SIAM J. Comput. Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets
2009	J	`jnl`	Chernoff-Type Direct Product Theorems. J. Cryptol. Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets
2009	J	`jnl`	New Direct-Product Testers and 2-Query PCPs. Electron. Colloquium Comput. Complex. Russell Impagliazzo, Valentine Kabanets, Avi Wigderson
2009	A*	`conf`	New direct-product testers and 2-query PCPs. STOC Russell Impagliazzo, Valentine Kabanets, Avi Wigderson
2009	B	`conf`	Security Amplification for InteractiveCryptographic Primitives. TCC Yevgeniy Dodis, Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets
2009	J	`jnl`	The Black-Box Query Complexity of Polynomial Summation. Comput. Complex. Ali Juma, Valentine Kabanets, Charles Rackoff, Amir Shpilka
2008	J	`jnl`	Hardness Amplification via Space-Efficient Direct Products. Comput. Complex. Venkatesan Guruswami, Valentine Kabanets
2008	J	`jnl`	On the Complexity of Succinct Zero-Sum Games. Comput. Complex. Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, Christopher Umans
2008	J	`jnl`	The complexity of Unique k-SAT: An Isolation Lemma for k-CNFs. J. Comput. Syst. Sci. Chris Calabro, Russell Impagliazzo, Valentine Kabanets, Ramamohan Paturi
2008	J	`jnl`	Uniform Direct-Product Theorems: Simplified, Optimized, and Derandomized. Electron. Colloquium Comput. Complex. Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Avi Wigderson
2008	A*	`conf`	Uniform direct product theorems: simplified, optimized, and derandomized. STOC Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Avi Wigderson
2007	A*	`conf`	Chernoff-Type Direct Product Theorems. CRYPTO Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets
2007	J	`jnl`	Special Issue "Conference on Computational Complexity 2006" Guest Editors' Foreword. Comput. Complex. Venkatesan Guruswami, Valentine Kabanets
2007	J	`jnl`	The black-box query complexity of polynomial summation. Electron. Colloquium Comput. Complex. Ali Juma, Valentine Kabanets, Charles Rackoff, Amir Shpilka
2006	A*	`conf`	Approximately List-Decoding Direct Product Codes and Uniform Hardness Amplification. FOCS Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets
2006	B	`conf`	Hardness Amplification Via Space-Efficient Direct Products. LATIN Venkatesan Guruswami, Valentine Kabanets
2006	J	`jnl`	Uniform Hardness Amplification in NP via Monotone Codes. Electron. Colloquium Comput. Complex. Joshua Buresh-Oppenheim, Valentine Kabanets, Rahul Santhanam
2005	J	`jnl`	Hardness amplification via space-efficient direct products Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Valentine Kabanets
2005	A	`conf`	On the Complexity of Succinct Zero-Sum Games. CCC Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, Christopher Umans
2004	J	`jnl`	Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds. Comput. Complex. Valentine Kabanets, Russell Impagliazzo
2004	J	`jnl`	On the complexity of succinct zero-sum games Electron. Colloquium Comput. Complex. Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, Christopher Umans
2003	J	`jnl`	Almost k-wise independence and hard Boolean functions. Theor. Comput. Sci. Valentine Kabanets
2003	A*	`conf`	Derandomizing polynomial identity tests means proving circuit lower bounds. STOC Valentine Kabanets, Russell Impagliazzo
2003	A	`conf`	The Complexity of Unique k-SAT: An Isolation Lemma for k-CNFs. CCC Chris Calabro, Russell Impagliazzo, Valentine Kabanets, Ramamohan Paturi
2002	J	`jnl`	Derandomization: A Brief Overview Electron. Colloquium Comput. Complex. Valentine Kabanets
2002	J	`jnl`	Derandomization: a brief overview. Bull. EATCS Valentine Kabanets
2002	J	`jnl`	Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds Electron. Colloquium Comput. Complex. Valentine Kabanets, Russell Impagliazzo
2002	J	`jnl`	In search of an easy witness: exponential time vs. probabilistic polynomial time. J. Comput. Syst. Sci. Russell Impagliazzo, Valentine Kabanets, Avi Wigderson
2001	J	`jnl`	Easiness Assumptions and Hardness Tests: Trading Time for Zero Error. J. Comput. Syst. Sci. Valentine Kabanets
2001	A	`conf`	In Search of an Easy Witness: Exponential Time vs. Probabilistic Polynomial Time. CCC Russell Impagliazzo, Valentine Kabanets, Avi Wigderson
2001	—	`—`	Nonuniformly hard boolean functions and uniform complexity classes. Valentine Kabanets
2000	B	`conf`	Almost LATIN Valentine Kabanets
2000	A*	`conf`	Circuit minimization problem. STOC Valentine Kabanets, Jin-Yi Cai
2000	A	`conf`	Easiness Assumptions and Hardness Tests: Trading Time for Zero Error. CCC Valentine Kabanets
2000	J	`jnl`	Efficiently Approximable Real-Valued Functions Electron. Colloquium Comput. Complex. Valentine Kabanets, Charles Rackoff, Stephen A. Cook
1999	J	`jnl`	Almost k-Wise Independence and Boolean Functions Hard for Read-Once Branching Programs Electron. Colloquium Comput. Complex. Valentine Kabanets
1999	J	`jnl`	Circuit Minimization Problem Electron. Colloquium Comput. Complex. Valentine Kabanets, Jin-Yi Cai
1997	A*	`conf`	Recognizability Equals Definability for Partial k-Paths. ICALP Valentine Kabanets