Tolerant Bipartiteness Testing in Dense Graphs

Arijit Ghosh, Gopinath Mishra, Rahul Raychaudhury +1

Bipartite testing has been a central problem in the area of property testing since its inception in the seminal work of Goldreich, Goldwasser and Ron [FOCS'96 and JACM'98]. Though…