För inmatning x, låt F (x) betecknar uppsättningen outputs som är de "legala" svaren för en beräkningsproblem F. Antag x och medlemmar av F (x) är så stora att det inte finns tid att läsa dem i sin helhet. Vi föreslår en modell av lokala beräkningsalgoritmer som för en given inmatning x, stödja frågor från en användare till värden för angivna platser y i i en laglig utgång y  på F (x). När mer än en laglig utdata y finns för ett givet x, bör den lokala beräkningsalgoritmen utdata på ett sätt som överensstämmer med minst ett sådant y. Lokala beräkningsalgoritmer är avsedda att destillera de gemensamma egenskaperna hos flera koncept som har dykt upp i olika algoritmiska delfält, inklusive lokal distribuerad beräkning, lokala algoritmer, lokalt decodable koder, och lokal rekonstruktion. Vi utvecklar en teknik, baserad på kända konstruktioner av små provutrymmen av k-wise oberoende slumpvariabler och Becks analys i hans algoritmiska tillvägagångssätt till Lovász Local Lemma, som under vissa förhållanden kan tillämpas för att konstruera lokala beräkningsalgoritmer som körs i polylogaritmisk tid och rum. Vi tillämpar denna teknik för maximal oberoende uppsättning beräkningar, schemaläggning radionät sändningar, hypergraph färgläggning och tillfredsställande k-SAT formler.
Nyligen, Rubinfeld et al. REF införde en modell som omfattar begrepp från flera algoritmiska delfält, såsom lokalt decodable-koder, lokal återuppbyggnad och lokal distribuerad beräkning.
Fast Local Computation Algorithms
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}