Recent Advances in Debordering Methods
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915555571662848 |
|---|---|
| author | Dutta, Pranjal Lysikov, Vladimir |
| author_facet | Dutta, Pranjal Lysikov, Vladimir |
| contents | Border complexity captures functions that can be approximated by low-complexity ones. Debordering is the task of proving an upper bound on some non-border complexity measure in terms of a border complexity measure, thus getting rid of limits. Debordering lies at the heart of foundational complexity theory questions relating Valiant's determinant versus permanent conjecture (1979) and its geometric complexity theory (GCT) variant proposed by Mulmuley and Sohoni (2001). The debordering of matrix multiplication tensors by Bini (1980) played a pivotal role in the development of efficient matrix multiplication algorithms. Consequently, debordering finds applications in both establishing computational complexity lower bounds and facilitating algorithm design. Recent years have seen notable progress in debordering various restricted border complexity measures. In this survey, we highlight these advances and discuss techniques underlying them. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_13049 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Recent Advances in Debordering Methods Dutta, Pranjal Lysikov, Vladimir Computational Complexity Symbolic Computation Algebraic Geometry 68Q17, 68Q15, 14L30 Border complexity captures functions that can be approximated by low-complexity ones. Debordering is the task of proving an upper bound on some non-border complexity measure in terms of a border complexity measure, thus getting rid of limits. Debordering lies at the heart of foundational complexity theory questions relating Valiant's determinant versus permanent conjecture (1979) and its geometric complexity theory (GCT) variant proposed by Mulmuley and Sohoni (2001). The debordering of matrix multiplication tensors by Bini (1980) played a pivotal role in the development of efficient matrix multiplication algorithms. Consequently, debordering finds applications in both establishing computational complexity lower bounds and facilitating algorithm design. Recent years have seen notable progress in debordering various restricted border complexity measures. In this survey, we highlight these advances and discuss techniques underlying them. |
| title | Recent Advances in Debordering Methods |
| topic | Computational Complexity Symbolic Computation Algebraic Geometry 68Q17, 68Q15, 14L30 |
| url | https://arxiv.org/abs/2510.13049 |