2 papers
cs.CC2025
The PPP-completeness of the Ward-Szabo theorem
Takashi Ishizuka
Ward and Szabó [WS94] have shown that a complete graph with nodes whose edges are colored by colors and that has at least two colors contains a bichromatic triangle. This…
cs.CC2023
Corrigendum: PLS is contained in PLC
Takashi Ishizuka
Recently, Pasarkar, Papadimitriou, and Yannakakis (ITCS 2023) have introduced the new TFNP subclass called PLC that contains the class PPP; they also have proven that several searc…