Hanlin Ren

collaborators

3 papers

cs.CC2026

Many Proof Complexity Generators Inside One Demi-Bits Generator

Xin Li, Hanlin Ren, Yan Zhong

For a propositional proof system $P$ and a polynomial-time function $G : {0, 1}^{n} \to {0, 1}^{N}$ ( $N > 10 n$ ), we say that $G$ is a *proof complexity generator* against…

cs.CC2026

The Weak Rank Principle: Lower Bounds and Applications

Michal Garl\'\ik, Svyatoslav Gryaznov, Hanlin Ren +1

Given two symbolic matrices $X$ and $Y$ of dimensions $m \times n$ and $n \times m$ , the *weak rank principle* (WRank) states the equation $X Y = A$ is unsatisfiable when $m > n$ and ra…

cs.CC2025

New Algebrization Barriers to Circuit Lower Bounds via Communication Complexity of Missing-String

Lijie Chen, Yang Hu, Hanlin Ren

The *algebrization barrier*, proposed by Aaronson and Wigderson (STOC '08, ToCT '09), captures the limitations of many complexity-theoretic techniques based on arithmetization. Not…