Suryajith Chillara

Recently, Forbes, Kumar and Saptharishi [CCC, 2016] proved that there exists an explicit $d^{O(1)}$-variate and degree $d$ polynomial $P_{d} \in VNP$ such that if any depth four circuit $C$ of bounded formal degree $d$ which computes a polynomial of bounded individual degree $O(1)$, that is functionally equivalent to $P_d$, then ... more >>>

Tuomas Hakoniemi , Nutan Limaye, Iddo Tzameret

Strong algebraic proof systems such as IPS (Ideal Proof System; Grochow-Pitassi JACM 2018) offer a general model for

deriving polynomials in an ideal and refuting unsatisfiable propositional formulas, subsuming most standard propositional proof systems. A major approach for lower bounding the size of IPS refutations is the Functional Lower Bound ...
more >>>