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

CREATORGuy Bresler, Alina Harbuzova
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE369 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-19016

Browse the full library · About the Tower of Babel