We build SNARGs for \(\textbf{NP}\) from a new source of hardness—the difficulty of proving mathematical theorems—by leveraging the fact that cryptographic security proofs formalize in weak bounded arithmetic.
We introduce \(\textbf{APX}_1\), a new bounded arithmetic theory that formalizes feasible probabilistic reasoning, aiming to expose more fine-grained proof complexity structure for polynomial time approximate counting.
We introduce an identity testing problem inspired by machine learning compiler design and analyze a simple randomized algorithm. The algorithm is implemented in Mirage and works well in practice.
We prove that Arthur-Merlin protocols with exponential time and a sub-exponential advice requires maximum circuit complexity. Previously, maximum lower bounds are known only for classes in the second level of the polynomial-time hierarchy.
We prove two unconditional structural results about catalytic computation: CL \(\cap\) P = CLP and CBPL = CL.
This paper discusses connections between common concepts in the theory of pseudorandomness: distinguishers, predictors, and certification. Most interestingly, we obtain a new prBPP-complete problem related to derandomizing a lemma of Yao.
This is a follow up work of the STOC 2023 paper with Rahul Ilango and Ryan Williams. We prove stronger hardness results by using more specific cryptographic assumptions.
Following a recent breakthrough of Pich and Santhanam (2021), we prove unprovability of strong complexity lower bounds in the the theory PV and even stronger theories.
We show that the range avoidance problem is hard for deterministic algorithms, assuming NP \(\ne\) coNP and the existence of indistinguishability obfuscation. With a similar approach, we also obtain unprovability results in bounded arithmetic.
We provide unconditional NP-oracle algorithms for solving certain Range Avoidance Problem. This can be viewed as a generalization of ACC circuit lower bounds proved by Ryan Williams.
A follow-up work on the STOC 2022 PRF paper, provide an even more efficient hash function construction and use it to show hardness magnification results.
We obtained the exact circuit complexity of computing pseudorandom functions in various circuit models. We also use these construction to explain the difficulty of proving circuit lower bounds.
We prove that an explicit function in P requires \(3.1n-o(n)\) size to compute by general circuits. This improves an earlier \((3+1/86)n-o(n)\) lower bound for the same function.
We show that with respect to the theory PV, certain lower bounds about communication complexity and Turing machines are equivalent to basic mathematical principles such as the Pigeonhole Principle.
We show unconditional unprovability of complexity upper and lower bounds in intuitionistic bounded arithmetic.
No publications with this topic.