3 papers
cs.CR2026
Spectral Method attacks Sparse LWE, Sparse LPN and Beyond
Shashwat Agrawal, Amitabha Bagchi, Rajendra Kumar
Given a set of -sparse linear equations over a ring , we give algorithms to determine whether the right-hand sides are random or have a secret assignment planted with noise.…
quant-ph2025
Fine-Grained Complexity via Quantum Natural Proofs
Yanlin Chen, Yilei Chen, Rajendra Kumar +2
Buhrman, Patro, and Speelman presented a framework of conjectures that together form a quantum analogue of the strong exponential-time hypothesis and its variants. They called it t…
quant-ph2025
QSETH strikes again: finer quantum lower bounds for lattice problem, strong simulation, hitting set problem, and more
Yanlin Chen, Yilei Chen, Rajendra Kumar +2
While seemingly undesirable, it is not a surprising fact that there are certain problems for which quantum computers offer no computational advantage over their respective classica…