Simple Circuit Extensions for XOR in PTIME

Marco Carmosino, Ngu Dang, Tim Jackman

The Minimum Circuit Size Problem for Partial Functions ($MCS{P}^{\ast }$) is hard assuming the Exponential Time Hypothesis (ETH) (Ilango, 2020). This breakthrough hardness result leveraged…