Valentine Kabanets

Available identifiers

zbMath Open kabanets.valentineMaRDI QIDQ230568

List of research outcomes

Publication	Date of Publication	Type
The power of natural properties as oracles	2023-08-16	Paper
Circuit Lower Bounds for MCSP from Local Pseudorandom Generators	2022-12-05	Paper
https://portal.mardi4nfdi.de/entity/Q5091189	2022-07-21	Paper
https://portal.mardi4nfdi.de/entity/Q5091223	2022-07-21	Paper
Algorithms and lower bounds for de morgan formulas of low-communication leaf gates	2022-07-21	Paper
Algorithms and Lower Bounds for De Morgan Formulas of Low-Communication Leaf Gates	2022-03-29	Paper
https://portal.mardi4nfdi.de/entity/Q5009542	2021-08-04	Paper
Agnostic Learning from Tolerant Natural Proofs	2021-07-28	Paper
https://portal.mardi4nfdi.de/entity/Q5121895	2020-09-22	Paper
Expander construction in \(\mathrm{VNC}^1\)	2020-06-02	Paper
Does Looking Inside a Circuit Help	2020-05-26	Paper
Recognizability equals definability for partial k-paths	2018-07-04	Paper
Expander Construction in VNC1	2018-05-03	Paper
The minimum oracle circuit size problem	2017-10-18	Paper
Pseudorandomness when the odds are against you	2017-10-10	Paper
Learning algorithms from natural proofs	2017-10-10	Paper
https://portal.mardi4nfdi.de/entity/Q5351927	2017-08-31	Paper
A polynomial restriction lemma with applications	2017-08-17	Paper
Fourier concentration from shrinkage	2017-07-28	Paper
The Minimum Oracle Circuit Size Problem.	2017-01-24	Paper
Simultaneous Secrecy and Reliability Amplification for a General Channel Model	2016-12-21	Paper
Correlation bounds and \#SAT algorithms for small linear-size circuits	2016-11-24	Paper
An improved deterministic \#SAT algorithm for small De Morgan formulas	2016-11-01	Paper
Correlation Bounds and #SAT Algorithms for Small Linear-Size Circuits	2015-10-29	Paper
Mining circuit lower bound proofs for meta-algorithms	2015-06-23	Paper
New direct-product testers and 2-query PCPs	2015-02-04	Paper
An axiomatic approach to algebrization	2015-02-04	Paper
Lower bounds against weakly-uniform threshold circuits	2015-01-19	Paper
An Improved Deterministic #SAT Algorithm for Small De Morgan Formulas	2014-10-14	Paper
Circuit minimization problem	2014-09-26	Paper
Is Valiant-Vazirani's isolation probability improvable?	2013-07-19	Paper
New Direct-Product Testers and 2-Query PCPs	2013-03-19	Paper
Lower Bounds against Weakly Uniform Circuits	2012-09-25	Paper
The black-box query complexity of polynomial summation	2011-02-18	Paper
Constructive Proofs of Concentration Bounds	2010-09-10	Paper
Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized	2010-09-06	Paper
Derandomizing polynomial identity tests means proving circuit lower bounds	2010-08-16	Paper
Approximate List-Decoding of Direct Product Codes and Uniform Hardness Amplification	2010-04-29	Paper
Hardness amplification via space-efficient direct products	2010-03-15	Paper
Chernoff-type direct product theorems	2009-06-30	Paper
On the complexity of succinct zero-sum games	2009-06-17	Paper
Chernoff-Type Direct Product Theorems	2009-03-10	Paper
Security Amplification for Interactive Cryptographic Primitives	2009-03-03	Paper
https://portal.mardi4nfdi.de/entity/Q5302082	2009-01-05	Paper
Hardness Amplification Via Space-Efficient Direct Products	2008-09-18	Paper
The complexity of Unique \(k\)-SAT: An isolation lemma for \(k\)-CNFs	2008-03-11	Paper
https://portal.mardi4nfdi.de/entity/Q4668730	2005-04-15	Paper
Derandomizing polynomial identity tests means proving circuit lower bounds	2005-02-23	Paper
Almost \(k\)-wise independence and hard Boolean functions.	2003-08-17	Paper
In search of an easy witness: Exponential time vs. probabilistic polynomial time.	2003-05-14	Paper
https://portal.mardi4nfdi.de/entity/Q3152808	2002-10-23	Paper
Easiness assumptions and hardness tests: Trading time for zero error	2002-07-22	Paper
https://portal.mardi4nfdi.de/entity/Q4508376	2000-10-03	Paper

Research outcomes over time

Doctoral students

No records found.

Known relations from the MaRDI Knowledge Graph

Property	Value
MaRDI profile type	MaRDI person profile
instance of	human

This page was built for person: Valentine Kabanets