Average-Case Reductions for k k -XOR and Tensor PCA
Guy Bresler, Alina Harbuzova · 2026
Read Average-Case Reductions for k k -XOR and Tensor PCA by Guy Bresler, Alina Harbuzova (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-19016.txt.
Introduction
Guy Bresler and Alina Harbuzova link two hard average case problems so that progress on one moves the other. Both problems hide a secret signal inside noise: one in a set of equations, the other in a tensor, a multi way grid. Both can be seen as noisy views of the same rank one signal.
The pair build fast reductions that turn one problem into the other on average. Reductions are the webbing of complexity theory: they show which problems stand or fall together. Tying these two helps researchers carry algorithms and hardness results across a gap that once split the field.
Catalog record
| CREATOR | Guy Bresler, Alina Harbuzova |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 369 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-19016