Mathematical and computational perspectives on the Boolean and binary rank and their relation to the real rank
This survey provides a comprehensive overview of the study of the binary and Boolean rank from both a mathematical and a computational perspective, with particular emphasis on their relationship to the real rank. We review the basic definitions of these rank functions and present the main alternative formulations of the binary and Boolean rank, together with their computational complexity and their deep connection to the field of communication complexity. We summarize key techniques used to establish lower and upper bounds on the binary and Boolean rank, including methods from linear…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2601.13900
curl -X POST /api/v1/records/arxiv/2601.13900/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2601.13900/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'