2026-07-26T00:06:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20602 2024-08-23T05:50:29Z ddc:004 open_access

Query Maintenance Under Batch Changes with Small-Depth Circuits Datta, Samir Khan, Asif Mukherjee, Anish Tschirbs, Felix Vortmeier, Nils Zeume, Thomas Dynamic complexity theory parallel computation dynamic algorithms Which dynamic queries can be maintained efficiently? For constant-size changes, it is known that constant-depth circuits or, equivalently, first-order updates suffice for maintaining many important queries, among them reachability, tree isomorphism, and the word problem for context-free languages. In other words, these queries are in the dynamic complexity class DynFO. We show that most of the existing results for constant-size changes can be recovered for batch changes of polylogarithmic size if one allows circuits of depth 𝒪(log log n) or, equivalently, first-order updates that are iterated 𝒪(log log n) times. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Samir Datta and Asif Khan and Anish Mukherjee and Felix Tschirbs and Nils Vortmeier and Thomas Zeume 2024 Is Part Of LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2024.46 urn:nbn:de:0030-drops-206027 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.46 eng https://creativecommons.org/licenses/by/4.0/legalcode