Efficient Algorithms for Subset Sum by Jesper Nederlof
Explore faster and space-efficient algorithms for Subset Sum problem, presented by Jesper Nederlof and team from Eindhoven University, Netherlands. Learn about efficient solutions for Subset Sum instances, including the Meet in the Middle method and a novel contribution achieving substantial time and space improvements.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Faster Space-Efficient Algorithms for Subset Sum Jesper Nederlof (Eindhoven University, Netherlands) Joint work with Nikhil Bansal, Shashwat Garg, and Nikhil Vyas 1 of 11
Subset Sum Given ints ?1, ,??,?, is there ? ? with ? ? := ? ???= ?? Today: how efficiently can we solve this in the wost case? NP-complete -> exponential time Basic DP [Bellman(50 s)] runs in ? (?) time and space What if ? is huge (i.e 2?)? 2 of 11
Meet in the Middle [HS(JACM74)] 1. Let L = (?1, ,??/2) 2. Compute all possible 2?/2sums 3. For each v ?, check v ? Sort ? + binary search in 3: ? (2?/2) time and space R = (??/2+1, ,??) ? ? ?1, ,??/2 ??/2+1, ,?? x = ? ? y = ? ? ? ? ? ? ? [SS(SICOMP 81)] improved to ? (2?/2) time, ? (2?/4) space Natural question: can we beat O (2?) using polynomial space? 3 of 11
Our contribution Main thm: SSS in ? (20.86?) time and poly space, if given a random oracle is given. 0100111100100 0001010000110 0001101010010 The oracle stores the random bits for us! Weaker assumption than sufficiently strong PRG s Algo i th bit? ????(?) time 0/1 4 of 11
Our contribution Main thm: SSS in ? (20.86?) time and poly space, if given a random oracle is given. Generalization to Knapsack Further generalization to Binary IP with few constraints Random* 3SUM in ?(?2.5) time and ?(log?) space without oracle 5 of 11
Main Idea Consider w(2[?]) = {? ? : x 0,1?} i.e. all possible 2?sums generated by ? = ?1, ,?? Consider w(2[?]) = {? ? : x 0,1?} i.e. all possible 2?sums generated by ? = ?1, ,?? Let ? = |?(2[?])| i.e. # distinct possible sums Let ? = |?(2[?])| i.e. # distinct possible sums Case 1: If d < 20.86? a) Hash mod ?(?), which makes ? = ? (?) b) ? (?) time DP, but in poly space [LN N(STOC 10)] ?(1 + ???) to find coeff. of ?? (few distinct sums) Union bound over d events Case 1: If d < 20.86? a) Hash mod ?(?), which makes t = ? (?) b) ? (?) time DP, but in poly space [LN N(STOC 10)] Interpolates ? ? = ?=1 (few distinct sums) Case 2: If d > 20.86? a) Upper bound max bin size via combinatorics of subset sums b) Use Floyd s cycle finding (and the oracle ) (many distinct sums) 6 of 11
Main Idea Consider w(2[?]) = {? ? : x 0,1?} i.e. all possible 2?sums generated by ? = ?1, ,?? Let ? = |?(2[?])| i.e. # distinct possible sums Case 1: If d < 20.86? a) Hash mod ?(?), which makes t = ? (?) b) ? (?) time DP, but in poly space [LN N(STOC 10)] (few distinct sums) Case 2: If d > 20.86? a) Upper bound max bin size via combinatorics of subset sums b) Use Floyd s cycle finding (and the oracle ) (many distinct sums) 7 of 11
Main Idea (many distinct sums) Case 2: If d > 20.86? a) Upper bound max bin size via combinatorics of subset sums Consider w(2[?]) = {? ? : x 0,1?} i.e. all possible 2?sums generated by ? = ?1, ,?? max bin size ????= ????|{? {0,1}?:? ? = ?}| Let ? = |?(2[?])| i.e. # distinct possible sums Lemma [AKKN(STACS 16)]: ? ???? 21.5? Cool add. comb. result Smoothness Subset Sum distrib. Proved via simple connection with `Uniquely Decodable Code Pairs As d > 20.86?, ???? 20.64? ? ? ???? Histogram 32 0 0 0 0 0 1 Case 1: If d < 20.86? a) Hash mod ?(?), which makes t = ? (?) b) ? (?) time DP, but in poly space [LN N(STOC 10)] (few distinct sums) 1 2 4 8 16 32 1 Case 2: If d > 20.86? a) Proof max bucket size low via combinatorics of subset sums b) Use Floyd s cycle finding (and the oracle ) (many distinct sums) 8 of 11
Meet in the Middle [HS(JACM74)] 1. Let L = (?1, ,??/2) 2. Compute all possible 2?/2sums 3. For each v ?, check v ? Sort ? + binary search in 3: ? (2?/2) time and space R = (??/2+1, ,??) ? ? ?1, ,??/2 ??/2+1, ,?? x = ? ? y = ? ? ? U = ? ? ? ? Looks like the Element Distinctness problem: Given list ? of ? ints find two positions with equal ints, if exist 5 3 4 9 2 10 7 8 1 6 none 5 3 4 3 2 10 7 8 1 6 How many times? ? #???? ???? ?(20.89?) Repeat Using max bin bound!! 1. Define z as the concatenation of x and y 2. (Almost) uniformly sample a solution of ED instance ? 3. Check if `fake solution or a real SSS solution 9 of 11
Sample solution of ED instance A priori for even finding a solution, ?(?2) time seems best with polylog ? space Thm [BCM(FOCS 13)]: ED in ?(?1.5) time, ?(log?) space, if given random oracle Crucially relies on Floyd s rho algorithm LD: Given two lists ?,? ??, is there a common value? Define ? ?,? = ?=1 |? 1? |2+ |? 1? |2 Thm: LD In ? ? ? time and ?(log?) space, if given f ?(?,?) and random oracle ? Refined analysis of [BCM(FOCS 13)]. Sample time ?(?/ ?) 10 of 11
Take-home Messages Cycle finding is a great tool low space algo s Win/win approach for many/few distinct sums Similar idea useful for other problems? To improve [HS(JACM 74)] it remains to `win in the case of few sums Thanks for listening, hope to see you at our poster! 11 of 11
