Efficient Compression in Semigroups
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2601.04747
curl -X POST /api/v1/records/arxiv/2601.04747/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2601.04747/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'