{"id":"arxiv/2601.04747","url":"https://arxiv.org/abs/2601.04747","tags":["math.RA","cs.CC","math.GR"],"score":0,"title":"Efficient Compression in Semigroups","domain":"math.RA","source":"arxiv","authors":["Florian Stober","Alexander Thumm","Armin Weiß"],"reviews":0,"subject":"math.RA","summary":"Straight-line programs are a central tool in several areas of computer science, including data compression, algebraic complexity theory, and the algorithmic solution of algebraic equations. In the algebraic setting, where straight-line programs can be interpreted as circuits over algebraic structures such as semigroups or groups, they have led to deep insights in computational complexity. A key result by Babai and Szemerédi (1984) showed that finite groups afford efficient compression via straight-line programs, enabling the design of a black-box computation model for groups. Building on…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-01-08","reactions":{}}