Valentine Kabanets: Publications

Halley Goldberg, Valentine Kabanets, Zhenjian Lu, Igor Carboni Oliveira
Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity
Halley Goldberg, Valentine Kabanets
A Simpler Proof of the Worst-Case to Average-Case Reduction for Polynomial Hierarchy via Symmetry of Information
Marco Carmosino, Valentine Kabanets, Antonina Kolokolova, Igor Carboni Oliveira
LEARN-Uniform Circuit Lower Bounds and Provability in Bounded Arithmetic
Marco Carmosino, Kenneth Hoover, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova
Lifting for Constant-Depth Circuits and Applications to MCSP
V. Kabanets, S. Koroth, Z. Lu, D. Myrisiotis, and I. Oliveira
Algorithms and Lower Bounds for de Morgan Formulas of Low-Communication Leaf Gates
A. Golovnev, R. Ilango, R. Impagliazzo, V. Kabanets, A. Kolokolova, and A. Tal
AC0[p] Lower Bounds against MCSP via the Coin Problem
M. Cheraghchi, V. Kabanets, Z. Lu, and D. Myrisiotis
Circuit Lower Bounds for MCSP from Local Pseudorandom Generators
V. Kabanets and Z. Lu
Satisfiability and Derandomization for Small Polynomial Threshold Circuits
R. Impagliazzo, V. Kabanets, and I. Volkovich
The Power of Natural Properties as Oracles
V. Kabanets, D.M. Kane, and Z. Lu
A Polynomial Restriction Lemma with Applications
R. Impagliazzo, V. Kabanets, A. Kolokolova, P. McKenzie, and S. Romani
Does Looking Inside a Circuit Help?
M. Carmosino, R. Impagliazzo, V. Kabanets, and A. Kolokolova
Agnostic Learning from Tolerant Natural Proofs
S. Buss, V. Kabanets, A. Kolokolova, and M. Koucký
Expander Construction in VNC¹
R. Impagliazzo, R. Jaiswal, V. Kabanets, B. Kapron, V. King, S. Tesssaro
Simultaneous Secrecy and Reliability Amplification for a General Channel Model
S. Artemenko, R. Impagliazzo, V. Kabanets, and R. Shaltiel
Pseudorandomness When the Odds Are Against You
M. Carmosino, R. Impagliazzo, V. Kabanets, and A. Kolokolova
Learning Algorithms from Natural Proofs
M. Carmosino, R. Impagliazzo, V. Kabanets, and A. Kolokolova
Tighter Connections between Derandomization and Circuit Lower Bounds
R. Chen and V. Kabanets
Correlation Bounds and #SAT Algorithms for Small Linear-Size Circuits
E. Allender, D. Holden, and V. Kabanets
The Minimum Oracle Circuit Size Problem
R. Impagliazzo and V. Kabanets
Fourier Concentration from Shrinkage
R. Chen, V. Kabanets, and N. Saurabh
An Improved Deterministic #SAT Algorithm for Small De Morgan Formulas
R. Chen, V. Kabanets, A. Kolokolova. R. Shaltiel, and D. Zuckerman
Mining circuit lower bound proofs for meta-algorithms
V. Kabanets and A. Kolokolova
Compression of Boolean Functions
R. Chen, V. Kabanets, and J. Kinne
Lower bounds against weakly-uniform threshold circuits
H. Dell, D. van Melkebeek, V. Kabanets, and O. Watanabe
Is Valiant-Vazirani's isolation probability improvable?
R. Impagliazzo and V. Kabanets
Constructive proofs of concentration bounds
R. Impagliazzo, V. Kabanets, and A. Kolokolova
An axiomatic approach to algebrization
R. Impagliazzo, V. Kabanets, and A. Wigderson
New direct product testers and 2-query PCPs
Y. Dodis, R. Impagliazzo, R. Jaiswal, and V. Kabanets
Security amplification for interactive cryptographic primitives
R. Impagliazzo, R. Jaiswal, V. Kabanets, and A. Wigderson
Uniform direct product theorems: Simplified, optimized, and derandomized
A. Juma, V. Kabanets, C. Rackoff, and A. Shpilka
The black-box query complexity of polynomial summation
R. Impagliazzo, R. Jaiswal, and V. Kabanets
Chernoff-type direct product theorems
J. Buresh-Oppenheim, V. Kabanets, and R. Santhanam
Hardness amplification in NP via monotone codes
R. Impagliazzo, R. Jaiswal, and V. Kabanets
Approximate list-decoding of direct product codes and uniform hardness amplification
V. Guruswami and V. Kabanets
Hardness amplification via space-efficient direct products
L. Fortnow, R. Impagliazzo, V. Kabanets, C. Umans,
On the complexity of succinct zero-sum games
C. Calabro, R. Impagliazzo, V. Kabanets, and R. Paturi,
The complexity of Unique k-SAT: An isolation lemma for k-CNFs
V. Kabanets and R. Impagliazzo,
Derandomizing Polynomial Identity Tests means proving circuit lower bounds
V. Kabanets,
Derandomization: A brief overview
R. Impagliazzo, V. Kabanets, and A. Wigderson,
In search of an easy witness: Exponential time vs. probabilistic polynomial time
V. Kabanets,
Easiness assumptions and hardness tests: Trading time for zero error
V. Kabanets, C. Rackoff, and S.A. Cook,
Efficiently approximable real-valued functions
V. Kabanets and J.-Y. Cai,
Circuit minimization problem
V. Kabanets,
Almost k-wise independence and hard Boolean functions
V. Kabanets,
Recognizability equals definability for partial k-paths

Dissertations

Nonuniformly hard Boolean functions and uniform complexity classes PhD Thesis, University of Toronto, October 2000.
Recognizability equals definability for partial k-paths MSc Thesis, Simon Fraser University, June 1996.

Back to home page