2 papers
cs.CC2026
Maximum Matching and Related Problems in Catalytic Logspace
Srijan Chakraborty, Samir Datta, Aryan Kusre +2
Understanding the power of space-bounded computation with access to catalytic space has been an important theme in complexity theory over the recent years. One of the key algorithm…
cs.CC2025
IPS Lower Bounds for Formulas and Sum of ROABPs
Prerona Chatterjee, Utsab Ghosal, Partha Mukhopadhyay +1
We give new lower bounds for the fragments of the Ideal Proof System (IPS) introduced by Grochow and Pitassi (JACM 2018). The Ideal Proof System is a central topic in algebraic pro…