39 citations · 78 across the 10 of their papers we have counts for
Showing cs.CCShow all
3 papers · 1 filter
cs.CC2023
-SUM in the Sparse Regime
Shweta Agrawal, Sagnik Saha, Nikolaj I. Schwartzbach +2
In the average-case -SUM problem, given integers chosen uniformly at random from , the objective is to find a ``solution'' set of numbers that sum to $0…
cs.CC2021
ZHED is NP-complete
Sagnik Saha, Erik D. Demaine
We prove that the 2017 puzzle game ZHED is NP-complete, even with just 1 tiles. Such a puzzle is defined by a set of unit-square 1 tiles in a square grid, and a target square of th…
cs.CC2021
NP-completeness of the Active Time Scheduling Problem
Sagnik Saha, Manish Purohit
In this paper, we study the active time scheduling problem. We are given n jobs with integral processing times each of which has an integral release time and deadline. The goal is…