Valentine Kabanets

Antonina Kolokolova

Electron. Colloquium Comput. Complex., 2025

Provability of the Circuit Size Hierarchy and Its Consequences.

[BibT_eX]

[DOI]

Dimitrios Tsintsilidas

Proceedings of the 16th Innovations in Theoretical Computer Science Conference, 2025

Witness Encryption and NP-Hardness of Learning.

[BibT_eX]

[DOI]

Proceedings of the 40th Computational Complexity Conference, 2025

2024

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

[BibT_eX]

[DOI]

Proceedings of the 39th Computational Complexity Conference, 2024

Consequences of Randomized Reductions from SAT to Time-Bounded Kolmogorov Complexity.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2024

2023

Mutual Empowerment between Circuit Obfuscation and Circuit Minimization.

[BibT_eX]

[DOI]

Ilya Volkovich

Electron. Colloquium Comput. Complex., 2023

Improved Learning from Kolmogorov Complexity.

[BibT_eX]

[DOI]

Proceedings of the 38th Computational Complexity Conference, 2023

Synergy Between Circuit Obfuscation and Circuit Minimization.

[BibT_eX]

[DOI]

Ilya Volkovich

Proceedings of the Approximation, 2023

2022

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

[BibT_eX]

[DOI]

Dagstuhl Reports, September, 2022

A Simpler Proof of the Worst-Case to Average-Case Reduction for Polynomial Hierarchy via Symmetry of Information.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2022

Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity.

[BibT_eX]

[DOI]

Proceedings of the 37th Computational Complexity Conference, 2022

2021

Lifting for Constant-Depth Circuits and Applications to MCSP.

[BibT_eX]

[DOI]

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

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

[BibT_eX]

[DOI]

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

2020

Special Section on the Fifty-Eighth Annual IEEE Symposium on Foundations of Computer Science (FOCS 2017).

[BibT_eX]

[DOI]

Sofya Raskhodnikova

Chaitanya Swamy

SIAM J. Comput., 2020

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

[BibT_eX]

[DOI]

Proceedings of the 35th Computational Complexity Conference, 2020

2019

AC0[p] Lower Bounds against MCSP via the Coin Problem.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2019

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

[BibT_eX]

[DOI]

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

Circuit Lower Bounds for MCSP from Local Pseudorandom Generators.

[BibT_eX]

[DOI]

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

2018

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

[BibT_eX]

[DOI]

Zhenjian Lu

Electron. Colloquium Comput. Complex., 2018

Algebraic Methods in Computational Complexity (Dagstuhl Seminar 18391).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2018

The Power of Natural Properties as Oracles.

[BibT_eX]

[DOI]

Ilya Volkovich

Proceedings of the 33rd Computational Complexity Conference, 2018

Satisfiability and Derandomization for Small Polynomial Threshold Circuits.

[BibT_eX]

[DOI]

Zhenjian Lu

Proceedings of the Approximation, 2018

2017

A polynomial restriction lemma with applications.

[BibT_eX]

[DOI]

Daniel M. Kane

Zhenjian Lu

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Does Looking Inside a Circuit Help?.

[BibT_eX]

[DOI]

Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science, 2017

Expander Construction in VNC1.

[BibT_eX]

[DOI]

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

Agnostic Learning from Tolerant Natural Proofs.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2017

2016

Algorithms from Natural Lower Bounds.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

Expander Construction in VNC1.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

Algebraic Methods in Computational Complexity (Dagstuhl Seminar 16411).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2016

Simultaneous Secrecy and Reliability Amplification for a General Channel Model.

[BibT_eX]

[DOI]

Proceedings of the Theory of Cryptography - 14th International Conference, 2016

Learning Algorithms from Natural Proofs.

[BibT_eX]

[DOI]

Proceedings of the 31st Conference on Computational Complexity, 2016

Pseudorandomness When the Odds are Against You.

[BibT_eX]

[DOI]

Proceedings of the 31st Conference on Computational Complexity, 2016

2015

The Minimum Oracle Circuit Size Problem.

[BibT_eX]

[DOI]

Eric Allender

Dhiraj Holden

Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science, 2015

Correlation Bounds and #SAT Algorithms for Small Linear-Size Circuits.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics - 21st International Conference, 2015

Tighter Connections between Derandomization and Circuit Lower Bounds.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2015

2014

Algebra in Computational Complexity (Dagstuhl Seminar 14391).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2014

Lower Bounds Against Weakly-Uniform Threshold Circuits.

[BibT_eX]

[DOI]

Jeff Kinne

Algorithmica, 2014

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

[BibT_eX]

[DOI]

Nitin Saurabh

Proceedings of the Mathematical Foundations of Computer Science 2014, 2014

Fourier Concentration from Shrinkage.

[BibT_eX]

[DOI]

Proceedings of the IEEE 29th Conference on Computational Complexity, 2014

Mining Circuit Lower Bound Proofs for Meta-algorithms.

[BibT_eX]

[DOI]

Proceedings of the IEEE 29th Conference on Computational Complexity, 2014

2013

Compression of Boolean Functions.

[BibT_eX]

[DOI]

Antonina Kolokolova

Electron. Colloquium Comput. Complex., 2013

2012

Lower Bounds against Weakly Uniform Circuits.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics - 18th Annual International Conference, 2012

Is Valiant-Vazirani's Isolation Probability Improvable?

[BibT_eX]

[DOI]

Proceedings of the 27th Conference on Computational Complexity, 2012

2011

Is the Valiant-Vazirani Isolation Lemma Improvable?

[BibT_eX]

[DOI]

Osamu Watanabe

Electron. Colloquium Comput. Complex., 2011

2010

Constructive Proofs of Concentration Bounds.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2010

2009

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

[BibT_eX]

[DOI]

Ragesh Jaiswal

SIAM J. Comput., 2009

The Black-Box Query Complexity of Polynomial Summation.

[BibT_eX]

[DOI]

Comput. Complex., 2009

Security Amplification for InteractiveCryptographic Primitives.

[BibT_eX]

[DOI]

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

New direct-product testers and 2-query PCPs.

[BibT_eX]

[DOI]

Avi Wigderson

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

An Axiomatic Approach to Algebrization.

[BibT_eX]

[DOI]

Antonina Kolokolova

Proceedings of the Algebraic Methods in Computational Complexity, 11.10. - 16.10.2009, 2009

2008

Uniform direct product theorems: simplified, optimized, and derandomized.

[BibT_eX]

[DOI]

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

2007

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

[BibT_eX]

[DOI]

Venkatesan Guruswami

Comput. Complex., 2007

Chernoff-Type Direct Product Theorems.

[BibT_eX]

[DOI]

Ragesh Jaiswal

Proceedings of the Advances in Cryptology, 2007

2006

Uniform Hardness Amplification in NP via Monotone Codes.

[BibT_eX]

[DOI]

Joshua Buresh-Oppenheim

Rahul Santhanam

Electron. Colloquium Comput. Complex., 2006

Hardness Amplification Via Space-Efficient Direct Products.

[BibT_eX]

[DOI]

Venkatesan Guruswami

Proceedings of the LATIN 2006: Theoretical Informatics, 2006

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

[BibT_eX]

[DOI]

Ragesh Jaiswal

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

2005

On the Complexity of Succinct Zero-Sum Games.

[BibT_eX]

[DOI]

Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 2005

2003

Almost k-wise independence and hard Boolean functions.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2003

Derandomizing polynomial identity tests means proving circuit lower bounds.

[BibT_eX]

[DOI]

Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

The Complexity of Unique k-SAT: An Isolation Lemma for k-CNFs.

[BibT_eX]

[DOI]

Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003

2002

Derandomization: A Brief Overview

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2002

2001

Nonuniformly hard boolean functions and uniform complexity classes.

[BibT_eX]

[DOI]

PhD thesis, 2001

In Search of an Easy Witness: Exponential Time vs. Probabilistic Polynomial Time.

[BibT_eX]

[DOI]

Avi Wigderson

Proceedings of the 16th Annual IEEE Conference on Computational Complexity, 2001

2000

Efficiently Approximable Real-Valued Functions

[BibT_eX]

[DOI]

Charles Rackoff

Stephen A. Cook

Electron. Colloquium Comput. Complex., 2000

Circuit minimization problem.

[BibT_eX]

[DOI]

Jin-yi Cai

Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Almost k-Wise Independence and Hard Boolean Functions.

[BibT_eX]

[DOI]

Proceedings of the LATIN 2000: Theoretical Informatics, 2000

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

[BibT_eX]

[DOI]

Proceedings of the 15th Annual IEEE Conference on Computational Complexity, 2000

1999

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1999

1997

Recognizability Equals Definability for Partial k-Paths.

[BibT_eX]

[DOI]