Given a circuit $G: \{0, 1\}^n \to \{0, 1\}^m$ with $m > n$, the *range avoidance* problem ($\text{Avoid}$) asks to output a string $y\in \{0, 1\}^m$ that is not in the range of $G$. Besides its profound connection to circuit complexity and explicit construction problems, this problem is also related ... more >>>

Razborov and Rudich's natural proofs barrier roughly says that it is computationally hard to certify that a uniformly random truth table has high circuit complexity. In this work, we show that the natural proofs barrier (specifically, Rudich's conjecture that there are no NP-constructive natural properties against $P/poly$) implies the following ... more >>>

One important question in algebraic complexity is understanding the complexity of polynomial ideals (Grochow, Bulletin of EATCS 131, 2020). Andrews and Forbes (STOC 2022) studied the determinantal ideals $I^{\det}_{n,m,r}$ generated by the $r\times r$ minors of $n\times m$ matrices. Over fields of characteristic zero or of sufficiently large characteristic, they ... more >>>