| Publication | Date of Publication | Type |
|---|
| Constant-depth circuits vs. monotone circuits | 2024-11-19 | Paper |
| Probabilistic Kolmogorov complexity with applications to average-case complexity | 2024-07-05 | Paper |
| Optimal coding theorems in time-bounded Kolmogorov complexity | 2024-06-24 | Paper |
| A duality between one-way functions and average-case symmetry of information | 2024-05-08 | Paper |
| Unprovability of strong complexity lower bounds in bounded arithmetic | 2024-05-08 | Paper |
Pseudodeterministic algorithms and the structure of probabilistic time
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing | 2023-11-14 | Paper |
Pseudodeterministic algorithms and the structure of probabilistic time
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing | 2023-11-14 | Paper |
| scientific article; zbMATH DE number 7701424 (Why is no real title available?) | 2023-06-26 | Paper |
scientific article; zbMATH DE number 7701424 (Why is no real title available?)
(available as arXiv preprint) | 2023-06-26 | Paper |
Beyond Natural Proofs: Hardness Magnification and Locality
Journal of the ACM | 2023-04-27 | Paper |
scientific article; zbMATH DE number 7650418 (Why is no real title available?)
(available as arXiv preprint) | 2023-02-03 | Paper |
| Hardness magnification near state-of-the-art lower bounds | 2022-07-27 | Paper |
| Parity helps to compute majority | 2022-07-27 | Paper |
| Randomness and intractability in Kolmogorov complexity | 2022-07-21 | Paper |
| scientific article; zbMATH DE number 7561750 (Why is no real title available?) | 2022-07-21 | Paper |
| Algorithms and lower bounds for De Morgan formulas of low-communication leaf gates | 2022-07-21 | Paper |
Expander-based cryptography meets natural proofs
Computational Complexity | 2022-04-12 | Paper |
Algorithms and lower bounds for De Morgan formulas of low-communication leaf gates
ACM Transactions on Computation Theory | 2022-03-29 | Paper |
Hardness magnification near state-of-the-art lower bounds
Theory of Computing | 2022-02-09 | Paper |
| scientific article; zbMATH DE number 7250145 (Why is no real title available?) | 2020-09-22 | Paper |
scientific article; zbMATH DE number 7215291 (Why is no real title available?)
(available as arXiv preprint) | 2020-06-26 | Paper |
| scientific article; zbMATH DE number 7215291 (Why is no real title available?) | 2020-06-26 | Paper |
Conspiracies between learning algorithms, circuit lower bounds, and pseudorandomness
(available as arXiv preprint) | 2020-05-26 | Paper |
| An average-case lower bound against \(\mathsf{ACC}^0\) | 2020-02-12 | Paper |
Beyond Natural Proofs: Hardness Magnification and Locality
(available as arXiv preprint) | 2019-11-19 | Paper |
Consistency of circuit lower bounds with bounded theories
(available as arXiv preprint) | 2019-05-30 | Paper |
On monotone circuits with local oracles and clique lower bounds
Chicago Journal of Theoretical Computer Science | 2018-08-08 | Paper |
| Majority is incompressible by \(\mathrm{AC}^0[p\) circuits] | 2018-01-24 | Paper |
Erdős-Ko-Rado for random hypergraphs: asymptotics and stability
Combinatorics, Probability and Computing | 2017-10-10 | Paper |
Near-optimal small-depth lower bounds for small distance connectivity
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2017-09-29 | Paper |
Learning circuits with few negations
(available as arXiv preprint) | 2017-08-31 | Paper |
Pseudodeterministic constructions in subexponential time
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing | 2017-08-17 | Paper |
Pseudodeterministic constructions in subexponential time
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing | 2017-08-17 | Paper |
Addition is exponentially harder than counting for shallow monotone circuits
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing | 2017-08-17 | Paper |
Unprovability of circuit upper bounds in Cook's theory PV
(available as arXiv preprint) | 2017-05-08 | Paper |
An algebraic formulation of the graph reconstruction conjecture
Journal of Graph Theory | 2016-04-15 | Paper |
An algebraic formulation of the graph reconstruction conjecture
Journal of Graph Theory | 2016-04-15 | Paper |
The power of negations in cryptography
Theory of Cryptography | 2015-07-06 | Paper |
Erratum to ``The Ricean objection: An analogue of Rice's theorem for first-order theories.
Logic Journal of the IGPL | 2009-12-18 | Paper |
The Ricean Objection: An Analogue of Rice's Theorem for First-order Theories
Logic Journal of the IGPL | 2009-01-21 | Paper |
