Exposition
Occasionally, I write expositions of other results that I found interesting. In these expositions, I present the proofs of these results in a way that I myself finds the most intuitive and easy to understand. I hope that other researchers will also find these expositions useful, so I make some of the most polished ones public.
Disclaimer:
Sometimes I will sacrifice rigor for intuition and easier understanding.
All the mistakes are solely mine.
Exposition List
Filter by topic: all circuit lower bounds relativization cryptography meta-complexity
From Ignorant Decision Trees to Barriers to Infinitely-Often Lower Bounds
Summary: I wrote this exposition when I was confused about the claims in [BFT'98] and [Aaronson'06] that there is an oracle world relative to which $\mathsf{MA}_{\mathsf{EXP}}$ and $\mathsf{PEXP}$ have polynomial-size circuits. Proving a ($\mathsf{MA}^{\mathsf{dt}}$ or $\mathsf{PP}^{\mathsf{dt}}$) decision-tree lower bound for the Missing-String problem only gives an oracle world where such circuit upper bounds hold infinitely often. In this exposition, we identify a property called ignorance which is (slightly) stronger than lower bounds for Missing-String, and show that ignorance of decision trees imply almost everywhere circuit upper bounds in oracle worlds. We also rephrase the oracle separations of [BFT'98] and [Aaronson'06] in terms of decision tree lower bounds for Missing-String.
Hardness Along the Boundary: Towards One-Way Functions from the Worst-case Hardness of Time-Bounded Kolmogorov Complexity, originally by Yanyi Liu and Rafael Pass
Summary: The main result I write about is that the worst-case hardness of the "boundary $\mathrm{K}^{\mathrm{poly}}$" problem implies the existence of one-way functions. I also discuss the possibility of using their results to base the existence of OWFs on the exponential hardness of (the standard gap version of) time-bounded Kolmogorov complexity.
Failure of Symmetry of Information for Randomized Computations, originally by Jinqiao Hu, Yahel Manor, and Igor C. Oliveira
Summary: The main result I write about is that SoI for $\mathrm{rKt}$ implies a fast randomized algorithm for $\mathrm{rKt}$. I also improve their results by removing a $\log n$ factor in the overhead using a simpler proof.
Lower Bounds for Levin–Kolmogorov Complexity, originally by Nicholas Brandt
Summary: I write about a simplified proof of this paper's main result that $\mathrm{MKtP} \not\in \mathsf{DTIME}[O(n)]$, found by GPT-6 Astra.
|