121 citations · 181 across the 38 of their papers we have counts for
5 papers · 1 filter
Faster Space-Efficient Algorithms for Subset Sum, k-Sum and Related Problems
Nikhil Bansal, Shashwat Garg, Jesper Nederlof +1
We present space efficient Monte Carlo algorithms that solve Subset Sum and Knapsack instances with items using time and polynomial space, where the $O^*(\cdot…
Finding Large Set Covers Faster via the Representation Method
Jesper Nederlof
The worst-case fastest known algorithm for the Set Cover problem on universes with elements still essentially is the simple -time dynamic programming algorithm, and n…
Sharper Upper Bounds for Unbalanced Uniquely Decodable Code Pairs
Per Austrin, Petteri Kaski, Mikko Koivisto +1
Two sets form a Uniquely Decodable Code Pair (UDCP) if every pair , yields a distinct sum , where the addition is over $\mathbb{…
A short note on Merlin-Arthur protocols for subset sum
Jesper Nederlof
In the subset sum problem we are given n positive integers along with a target integer t. A solution is a subset of these integers summing to t. In this short note we show that for…
Subexponential time algorithms for finding small tree and path decompositions
Hans L. Bodlaender, Jesper Nederlof
The Minimum Size Tree Decomposition (MSTD) and Minimum Size Path Decomposition (MSPD) problems ask for a given n-vertex graph G and integer k, what is the minimum number of bags of…