Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > JOSEPH ZALEWSKI:
All reports by Author Joseph Zalewski:

TR23-027 | 8th March 2023
Joseph Zalewski

Some Lower Bounds Related to the Missing String Problem

We prove that a $O(k \log k)$-probe local algorithm for $k$-Missing String presented by Vyas and Williams is asymptotically optimal among a certain class of algorithms for this problem. The best lower bound we are aware of for the general case is still $\Omega(k)$.

more >>>



ISSN 1433-8092 | Imprint