| Publication | Date of Publication | Type |
|---|
| New PRGs for unbounded-width/adaptive-order read-once branching programs | 2024-11-14 | Paper |
| New lower bounds and derandomization for ACC, and a derandomization-centric view on the algorithmic method | 2024-09-25 | Paper |
| Black-Box constructive proofs are unavoidable | 2024-09-25 | Paper |
| Truly low-space element distinctness and subset sum via pseudorandom hash functions | 2024-07-19 | Paper |
| Extremely efficient constructions of hash functions, with applications to hardness magnification and PRFs | 2024-07-05 | Paper |
Constructive separations and their consequences
TheoretiCS | 2024-07-03 | Paper |
| Towards multi-pass streaming lower bounds for optimal approximation of \textsf{Max-Cut} | 2024-05-14 | Paper |
| When Arthur has neither random coins nor time to spare: superfast derandomization of proof systems | 2024-05-08 | Paper |
| scientific article; zbMATH DE number 7829235 (Why is no real title available?) | 2024-04-09 | Paper |
| scientific article; zbMATH DE number 7829277 (Why is no real title available?) | 2024-04-09 | Paper |
Simple and fast derandomization from very hard functions: eliminating randomness at almost no cost
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing | 2023-11-14 | Paper |
Inverse-exponential correlation bounds and extremely rigid matrices from a new derandomized XOR lemma
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing | 2023-11-14 | Paper |
Almost optimal super-constant-pass streaming lower bounds for reachability
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing | 2023-11-14 | Paper |
Improved Merlin-Arthur protocols for central problems in fine-grained complexity
Algorithmica | 2023-08-17 | 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 |
| Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity | 2022-07-27 | Paper |
| Relations and equivalences between circuit lower bounds and karp-lipton theorems | 2022-07-27 | Paper |
scientific article; zbMATH DE number 7559066 (Why is no real title available?)
(available as arXiv preprint) | 2022-07-18 | Paper |
Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization
SIAM Journal on Computing | 2022-05-31 | Paper |
Efficient Construction of Rigid Matrices Using an NP Oracle
SIAM Journal on Computing | 2022-03-11 | Paper |
Broadcast Congested Clique
Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing | 2021-01-20 | Paper |
Strong average-case lower bounds from non-trivial derandomization
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing | 2021-01-19 | Paper |
Sharp threshold results for computational complexity
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing | 2021-01-19 | Paper |
On the hardness of approximate and exact (bichromatic) maximum inner product
Theory of Computing | 2020-12-17 | Paper |
| scientific article; zbMATH DE number 7250154 (Why is no real title available?) | 2020-09-22 | Paper |
On the power of statistical zero knowledge
SIAM Journal on Computing | 2020-08-25 | Paper |
Nearly optimal separation between partially and fully retroactive data structures
(available as arXiv preprint) | 2020-08-25 | Paper |
An improved algorithm for incremental DFS tree in undirected graphs
(available as arXiv preprint) | 2020-08-25 | Paper |
Complexity-theoretic foundations of quantum supremacy experiments
(available as arXiv preprint) | 2020-05-26 | Paper |
Bootstrapping results for threshold circuits ``just beyond known lower bounds
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing | 2020-01-30 | Paper |
Beyond Natural Proofs: Hardness Magnification and Locality
(available as arXiv preprint) | 2019-11-19 | Paper |
An equivalence class for orthogonal vectors
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-10-15 | Paper |
Fine-grained complexity meets \(\mathrm{IP} = \mathrm{PSPACE}\)
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-10-15 | Paper |
| Adaptivity vs. postselection, and hardness amplification for polynomial approximation | 2018-04-19 | Paper |
| An algorithm based on the gradient-Hamilton decomposition theory of vector fields | 2010-07-08 | Paper |
Limit analysis of structures containing flaws based on a modified elastic compensation method
European Journal of Mechanics. A. Solids | 2008-04-07 | Paper |
