Abstract: We study the computational complexity of computing solutions for the

straight-cut and square-cut pizza sharing problems. We show that finding an

approximate solution is PPA-hard for the straight-cut problem, and

PPA-complete for the square-cut problem, while finding an exact solution for

the square-cut problem is FIXP-hard and in BU. Our PPA-hardness results apply

even when all mass distributions are unions of non-overlapping squares, and our

FIXP-hardness result applies even when all mass distributions are unions of

weighted squares and right-angled triangles. We also prove that decision variants

of the square-cut problem are hard: the approximate problem is

NP-complete, and the exact problem is ETR-complete.