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 >>>

Strong lower bounds of the form $2^{(1-\epsilon)n}$, where $n$ is the number of variables and $\epsilon>0$ is arbitrarily small (i.e., bounds consistent with the Strong ETH), are exceptionally rare in proof complexity. The seminal work of Beck and Impagliazzo (STOC 2013) achieved such a bound for regular resolution, and the ... more >>>

Quantifying and understanding the complexity of mathematical proofs is a fundamental question in proof complexity. At the qualitative level, bounded arithmetic formalizes the notion of feasible proofs, where all functions implicit in proofs are from certain complexity classes. For instance, Cook's theory PV (STOC'75) captures proofs using only polynomial-time computable ... more >>>