An ETH-based quasipolynomial lower bound for Dualization

Dualizing monotone Boolean functions (or equivalently, enumerating minimal transversals in hypergraphs) is a long-standing problem whose output-polynomial-time solvability remains open. While various special cases have been extensively studied, the state-of-the-art algorithm for the general case, due to Fredman and Khachiyan, runs in quasipolynomial time. This paper presents a subexponential-time reduction from $\text{textsc}3SAT$ to the complement of $\text{textsc}Dual$: Given a 3CNF formula with $n$ variables, the reduction constructs hypergraphs $\mathcal{H}$ and $\mathcal{L}$ of total size $2^{\text{bigoh}(n^{2\mathrm{/}3}(\log n{)}^{1\mathrm{/}3})}$ such that $\mathcal{L}\subseteq \text{Tr}(\mathcal{H})$ and the formula is satisfiable if and only if $\mathcal{L}\mathrm{\ne }\text{Tr}(\mathcal{H})$. As a consequence of this reduction, assuming the Exponential Time Hypothesis (ETH), neither $\text{textsc}Dual$ nor $\text{textsc}Dualization$ admits an algorithm running in $N^{o(\sqrt{\log N\mathrm{/}\log \log N})}$ time, where $N$ is the input size for $\text{textsc}Dual$ and the combined input and output size for $\text{textsc}Dualization$. In particular, $\text{textsc}Dualization$ cannot be solved in output-polynomial time under ETH.