Fine-Grained Complexity via Quantum Natural Proofs
- LecturerMr. Yan-Lin Chen (Algorithm and Complexity group, CWI and QuSoft)
Host: Kai-Min Chung - Time2025-06-05 (Thu.) 13:30 ~ 15:30
- LocationAuditorium 101 at IIS new Building
Abstract
Buhrman, Patro, and Speelman presented a framework of conjectures that together form a quantum analogue of the strong exponential-time hypothesis and its variants. They called it the QSETH framework. In this paper, using a notion of quantum natural proofs (built from natural proofs introduced by Razborov and Rudich), we show how part of the QSETH conjecture that requires properties to be `compression oblivious' can in many cases be replaced by assuming the existence of quantum-secure pseudorandom functions, a standard hardness assumption. Combined with techniques from Fourier analysis of Boolean functions, we show that properties such as PARITY and MAJORITY are compression oblivious for certain circuit class Λ if subexponentially secure quantum pseudorandom functions exist in Λ, answering an open question in [Buhrman-Patro-Speelman 2021].