Beyond Worst Case Local Computation Algorithms

Amartya Shankha Biswas, Ruidi Cao, Cassandra Marcussen +4

We initiate the study of Local Computation Algorithms on average case inputs. In the Local Computation Algorithm (LCA) model, we are given probe access to a huge graph, and asked t…