1 problem

0 votes0 replies0 views
Hardness conjecture for distinguishing planted and random noisy 3-XOR instances
3-XOR distinguishing hardness conjecture. There is some constant $\eta<1/4$ such that no algorithm that succeeds for the 3-XOR distinguishing problem with $m=o(d^{3/2})$ runs in po…
Conjectureopen3-xor computational-hardness tensor-completionarXiv posted 2 days ago

Hardness conjecture for distinguishing planted and random noisy 3-XOR instances