3.1n-o(n) Circuit Lower Bounds for Explicit Functions
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.
Posts by Collection
publications
The Exact Complexity of Pseudorandom Functions and the Black-Box Natural Proof Barrier for Bootstrapping Results in Computational Complexity
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.
Extremely Efficient Constructions of Hash Functions, with Applications to Hardness Magnification and PRFs
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.
Range Avoidance, Remote Point, and Hard Partial Truth Tables via Satisfying-Pairs Algorithms
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.
Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic
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.
Unprovability of Strong Complexity Lower Bounds in Bounded Arithmetic
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.
Hardness of Range Avoidance and Remote Point for Restricted Circuits via Cryptography
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.
Distinguishing, Predicting, and Certifying: On the Long Reach of Partial Notions of Pseudorandomness
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.
The Structure of Catalytic Space: Capturing Randomness and Time via Compression
We prove two unconditional structural results about catalytic computation: CL \(\cap\) P = CLP and CBPL = CL.
Maximum Circuit Lower Bounds for Exponential-Time Arthur Merlin
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.
On the Unprovability of Circuit Size Bounds in Intuitionistic \(S^1_2\)
We show unconditional unprovability of complexity upper and lower bounds in intuitionistic bounded arithmetic.
Identity Testing for Circuits with Exponentiation Gates
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.
Reverse Mathematics of Complexity Lower Bounds
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.
A Theory for Probabilistic Polynomial-Time Reasoning
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.
SNARGs for NP from Unprovability of Mathematical Theorems (Or: How to Use the Simplicity of Cryptographic Reasoning)
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.
teaching
Teaching experience 1
Undergraduate course, University 1, Department, 2014
This is a description of a teaching experience. You can use markdown like any other post.
Teaching experience 2
Workshop, University 1, Department, 2015
This is a description of a teaching experience. You can use markdown like any other post.