Local Computation the LOCAC model [Linial '87]: In t rounds:each node can collect information up to distance t. Locally Checkable Labeling (LCL)problems [Noar,Stockmeyer 293]: CSPs with local constraints. Construct a feasible solution: vertex/edge coloring,Lovasz local lemma Find local optimum:MIS,MM Approximate global optimum: maximum matching,minimum vertex cover,minimum dominating set network G(E) Q:"What locally definable problems are locally computable?" by local constraints in O(1)rounds or in small number of roundsLocal Computation • CSPs with local constraints. • Construct a feasible solution: vertex/edge coloring, Lovász local lemma • Find local optimum: MIS, MM • Approximate global optimum: maximum matching, minimum vertex cover, minimum dominating set Locally Checkable Labeling (LCL) problems [Noar, Stockmeyer ’93] : Q: “What locally definable problems are locally computable?” the LOCAL model [Linial ’87]: network G(V,E) • In t rounds: each node can collect information up to distance t. by local constraints in O(1) rounds or in small number of rounds