| 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 |
