2 papers
cs.DS2026
Clustering with Non-adaptive Subset Queries
Hadley Black, Euiwoong Lee, Arya Mazumdar +1
Recovering the underlying -clustering of a set of points by asking pair-wise same-cluster queries has garnered significant interest in the past few years. Given a query…
cs.CC2025
Inapproximability of Finding Sparse Vectors in Codes, Subspaces, and Lattices
Vijay Bhattiprolu, Venkatesan Guruswami, Euiwoong Lee +1
Finding sparse vectors is a fundamental problem that arises in several contexts including codes, subspaces, and lattices. In this work, we prove strong inapproximability results fo…