Med tanke på en ingång x, och ett sökproblem F, lokala beräkningsalgoritmer (LCAs) genomföra tillgång till angivna platser för y i en juridisk utgång y  på F (x), med hjälp av polylogaritmisk tid och utrymme. Mansour et al., (2012), hade tidigare visat hur man konverterar vissa online-algoritmer till LCAs. I detta arbete utvecklar vi den typen av arbete och utvecklar nya tekniker för att utforma LCA och begränsa deras rymd- och tidskomplexitet. Våra bidrag är fyrafaldiga: (1) Vi förbättrar avsevärt drifttider och utrymmeskrav för LCAs för tidigare resultat, (2) vi expanderar och bättre definiera familjen av online-algoritmer som kan konverteras till LCAs med hjälp av våra tekniker, (3) vi visar att våra resultat gäller för en större familj av grafer än tidigare resultat, och (4) våra bevis är enklare och mer koncisa än de tidigare bevismetoderna. Till exempel visar vi hur man konstruerar LCAs som kräver O(log n log log n) utrymme och O(log 2 n) tid (och förväntad tid O(log log n)) för problem som maximal matchning på en stor familj av grafer, i motsats till de hädanefter bästa resultaten som krävde O(log 3 n) utrymme och O(log 4 n) tid, och tillämpas på en mindre familj av grafer.
REF utvidgade dessa resultat till en bredare familj av grafer och fick bättre tids- och rymdgränser.
New Techniques and Tighter Bounds for Local Computation Algorithms
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}