| Publication | Date of Publication | Type |
|---|
Synergy between circuit obfuscation and circuit minimization
| 2025-01-14 | Paper |
Improved learning from Kolmogorov complexity
| 2024-11-19 | Paper |
Probabilistic Kolmogorov complexity with applications to average-case complexity
| 2024-07-05 | Paper |
The power of natural properties as oracles
Computational Complexity | 2023-08-16 | Paper |
Circuit lower bounds for MCSP from local pseudorandom generators
ACM Transactions on Computation Theory | 2022-12-05 | Paper |
Algorithms and lower bounds for De Morgan formulas of low-communication leaf gates
| 2022-07-21 | Paper |
scientific article; zbMATH DE number 7561559 (Why is no real title available?)
| 2022-07-21 | Paper |
Circuit lower bounds for MCSP from local pseudorandom generators
| 2022-07-21 | Paper |
Algorithms and lower bounds for De Morgan formulas of low-communication leaf gates
ACM Transactions on Computation Theory | 2022-03-29 | Paper |
Satisfiability and derandomization for small polynomial threshold circuits
| 2021-08-04 | Paper |
Agnostic Learning from Tolerant Natural Proofs
| 2021-07-28 | Paper |
scientific article; zbMATH DE number 7250147 (Why is no real title available?)
| 2020-09-22 | Paper |
Expander construction in \(\mathrm{VNC}^1\)
Annals of Pure and Applied Logic | 2020-06-02 | Paper |
Does looking inside a circuit help?
| 2020-05-26 | Paper |
Recognizability equals definability for partial k-paths
Automata, Languages and Programming | 2018-07-04 | Paper |
Expander construction in \(\mathsf{VNC}^1\)
| 2018-05-03 | Paper |
The minimum oracle circuit size problem
Computational Complexity | 2017-10-18 | Paper |
Pseudorandomness when the odds are against you
| 2017-10-10 | Paper |
Learning algorithms from natural proofs
| 2017-10-10 | Paper |
Tighter connections between derandomization and circuit lower bounds
| 2017-08-31 | Paper |
A polynomial restriction lemma with applications
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing | 2017-08-17 | Paper |
Fourier concentration from shrinkage
Computational Complexity | 2017-07-28 | Paper |
The Minimum Oracle Circuit Size Problem.
| 2017-01-24 | Paper |
Simultaneous secrecy and reliability amplification for a general channel model
Theory of Cryptography | 2016-12-21 | Paper |
Correlation bounds and \#SAT algorithms for small linear-size circuits
Theoretical Computer Science | 2016-11-24 | Paper |
An improved deterministic \#SAT algorithm for small De Morgan formulas
Algorithmica | 2016-11-01 | Paper |
Correlation bounds and \#SAT algorithms for small linear-size circuits
Lecture Notes in Computer Science | 2015-10-29 | Paper |
Mining circuit lower bound proofs for meta-algorithms
Computational Complexity | 2015-06-23 | Paper |
An axiomatic approach to algebrization
Proceedings of the forty-first annual ACM symposium on Theory of computing | 2015-02-04 | Paper |
New direct-product testers and \(2\)-query PCPs
Proceedings of the forty-first annual ACM symposium on Theory of computing | 2015-02-04 | Paper |
Lower bounds against weakly-uniform threshold circuits
Algorithmica | 2015-01-19 | Paper |
An improved deterministic \#SAT algorithm for small De Morgan formulas
Mathematical Foundations of Computer Science 2014 | 2014-10-14 | Paper |
Circuit minimization problem
Proceedings of the thirty-second annual ACM symposium on Theory of computing | 2014-09-26 | Paper |
Is Valiant-Vazirani's isolation probability improvable?
Computational Complexity | 2013-07-19 | Paper |
New direct-product testers and 2-query PCPs
SIAM Journal on Computing | 2013-03-19 | Paper |
Lower bounds against weakly uniform circuits
Lecture Notes in Computer Science | 2012-09-25 | Paper |
The black-box query complexity of polynomial summation
Computational Complexity | 2011-02-18 | Paper |
Constructive proofs of concentration bounds
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2010-09-10 | Paper |
Uniform direct product theorems: simplified, optimized, and derandomized
SIAM Journal on Computing | 2010-09-06 | Paper |
Derandomizing polynomial identity tests means proving circuit lower bounds
Proceedings of the thirty-fifth annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
Approximate list-decoding of direct product codes and uniform hardness amplification
SIAM Journal on Computing | 2010-04-29 | Paper |
Hardness amplification via space-efficient direct products
Computational Complexity | 2010-03-15 | Paper |
Chernoff-type direct product theorems
Journal of Cryptology | 2009-06-30 | Paper |
On the complexity of succinct zero-sum games
Computational Complexity | 2009-06-17 | Paper |
Chernoff-Type Direct Product Theorems
Advances in Cryptology - CRYPTO 2007 | 2009-03-10 | Paper |
Security Amplification for Interactive Cryptographic Primitives
Theory of Cryptography | 2009-03-03 | Paper |
scientific article; zbMATH DE number 5485571 (Why is no real title available?)
| 2009-01-05 | Paper |
Hardness Amplification Via Space-Efficient Direct Products
LATIN 2006: Theoretical Informatics | 2008-09-18 | Paper |
The complexity of Unique \(k\)-SAT: An isolation lemma for \(k\)-CNFs
Journal of Computer and System Sciences | 2008-03-11 | Paper |
scientific article; zbMATH DE number 2156272 (Why is no real title available?)
| 2005-04-15 | Paper |
Derandomizing polynomial identity tests means proving circuit lower bounds
Computational Complexity | 2005-02-23 | Paper |
Almost \(k\)-wise independence and hard Boolean functions.
Theoretical Computer Science | 2003-08-17 | Paper |
In search of an easy witness: Exponential time vs. probabilistic polynomial time.
Journal of Computer and System Sciences | 2003-05-14 | Paper |
scientific article; zbMATH DE number 1820025 (Why is no real title available?)
| 2002-10-23 | Paper |
Easiness assumptions and hardness tests: Trading time for zero error
Journal of Computer and System Sciences | 2002-07-22 | Paper |
scientific article; zbMATH DE number 1512688 (Why is no real title available?)
| 2000-10-03 | Paper |
