4 papers
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.…
Fast -means Seeding Under The Manifold Hypothesis
Poojan Shah, Shashwat Agrawal, Ragesh Jaiswal
We study beyond worst case analysis for the -means problem where the goal is to model typical instances of -means arising in practice. Existing theoretical approaches provide…
Lattice Based Crypto breaks in a Superposition of Spacetimes
Divesh Aggarwal, Shashwat Agrawal, Rajendra Kumar
We explore the computational implications of a superposition of spacetimes, a phenomenon hypothesized in quantum gravity theories. This was initiated by Shmueli (2024) where the au…
A New Rejection Sampling Approach to -++ With Improved Trade-Offs
Poojan Shah, Shashwat Agrawal, Ragesh Jaiswal
The -++ seeding algorithm (Arthur & Vassilvitskii, 2007) is widely used in practice for the -means clustering problem where the goal is to cluster a dataset $…