VLDB 2026 Research / reviewers in the wild / expert
Lukas Lück
dblp:313/2787
· DBLP profile ↗
2ranked-venue papers
0as first author
2since 2021 · last 2026
—ORCID · none
Domains — the database's venue-derived domains; a paper can count in several
Theory of computation · 2 · 2 since 2021
| Year | Publication | Venue | Position |
|---|---|---|---|
| 2026 | Streaming word problems
Markus Lohrey, Lukas Lück, Julio Xochitemol |
Inf. Comput. | 2 |
| 2022 | Streaming Word ProblemsabstractWe study deterministic and randomized streaming algorithms for word problems of finitely generated groups. For finitely generated linear groups, metabelian groups and free solvable groups we show the existence of randomized streaming algorithms with logarithmic space complexity for their word problems. We also show that the class of finitely generated groups with a logspace randomized streaming algorithm for the word problem is closed under several group theoretical constructions: finite extensions, direct products, free products and wreath products by free abelian groups. We contrast these results with several lower bound. An example of a finitely presented group, where the word problem has only a linear space randomized streaming algorithm, is Thompson’s group F. Markus Lohrey, Lukas Lück |
MFCS | 2 |