Subset Sum and Related Problems - Insights and Algorithms
Explore Subset Sum and related problems, including efficient algorithms for Subset Sum, k-Sum, List Disjointness, and Floyds Cycle Finding. Learn about notable theorems and Monte Carlo algorithms for these computational challenges.
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
Subset Sum (and related problems) Jesper Nederlof (Eindhoven University) Based on [Part 1] Bansal, Garg, N, Vyas Faster Space-Efficient Algorithms for Subset Sum, k-Sum, and Related Problems [STOC 17, SICOMP 18] [Part 2] Austrin, Kaski, Koivisto, N Subset Sum in the Absence of Concentration [STACS 2015] Austrin, Kaski, Koivisto, N Dense Subset Sum May Be the Hardest [STACS 2016]
0100111100100 0001010000110 0001101010010 Subset Sum Given integers ?1, ,??,? find ? ? with ? ???= ? ?(??) time by DP ? ? time, poly space [LN N, STOC 10] ? ? + ? time, or ?(??) time poly space [B SODA 17] not in ? (?1 ?) time under SETH [ABHS, SODA 19] ? (2?) time, poly space (? omits poly factors in input) ? (2?/2) time, ? (2?/2) space [HS, JACM 72] ? (2?/2) time, ? (2?/4) space [SS, SICOMP81] Theorem: There is a Monte Carlo algorithm for Subset Sum using ? (20.86?) time and poly space, assuming random read-only access to random bits Algo i th bit? ????(?) time 0/1
List Disjointness Given two lists ?,? ??, ? ????(?) Asked do they share a common value? ? = (1, 9, 2, 4, 9, 4, 6, 5, 2) Define ? ? = ? [?]|? 1? |2; i.e p ? = 1 + 4 22 ? ?,? = ? ? + ? ? Counts number of pseudo-solutions ? = (7, 8, 5, 0, 3, 7, 3, 0, 8) Theorem: There is an ? ? ? time, ?(log?) space algorithm for List Disjointness, if given ? ?,? ? assuming random read-only access to random bits
Floyds Cycle Finding Define ? ? := ??, ?? ?, ? > ? We are interested* in distinct ?,? with ? ? = ?(?) View ? as digraph (with arcs (?,?(?))) ? ? s
Floyds Cycle Finding Define ? ? := ??, ?? ?, ? > ? We are interested* in distinct ?,? with ? ? = ?(?) View ? as digraph (with arcs (?,?(?))) ? ? i s j
Meet in the Middle [HS JACM 72] Ints ?1, ,??,?. Denote w ? ? ??? Reduce SSS on ? integers to List Disjointness on lists of length 2?/2; run the sorting algo ? ? ?1, ,??/2, ??/2+1, ,?? ? = ? ? ? = ? ? ? ? ? ? ? LD instance solved in ?(2?/2polylog(2?/2)) time, which is O (2?/2). Also uses 2?/2space
Meet in the Middle [HS JACM 72] Ints ?1, ,??,?. Denote w ? ? ??? Reduce SSS on ? integers to List Disjointness on lists of length 2?/2; run the sorting algo. new ?1, ,??/2, ??/2+1, ,??? ? ? = ? ? ? = ? ? ? ? ? ? ? ? 1 space, ? (2?/2?(?,?)) time ? ? = {?,? ?:? ? = ? ? } 2? If ??= 0, ? ? ,? ? = 2?-> 2?time How do instances with ? ? 20.99?look?
Smoothness Subset Sums [AKKN, STACS16] Lemma: ? ? |{? ? :? ?}| 6?/2 ?? ?(?) |{? ? :? ?}| Histogram 322 0 0 0 0 0 1 32 12 1 2 4 8 16 32 6 12+ 4 22+ 6 32 = 76 1 2 3 4 5 16
Smoothness Subset Sums [AKKN, STACS16] Lemma: ? ? |{? ? :? ?}| 6?/2 If ? ? > 1.99?or ? ? > 1.99?, then either |{? ? :? ?}| 1.99?/2or |{? ? :? ?}| 1.99?/2. ? 21.99 ? 2 1.999? But then ? ? :? ? 2 Lemma: Can solve instance ?1, ,??,? in time O ( ? ? :? ? ) and poly space. Hash numbers mod a prime of O Run ? ? time ? (1) space DFT algo [LN, STOC 10] ? ? :? ?
Part 2 [AKKN, STACS15,16] Goal: Solve Subset Sum in ? (20.49999?) time. We are still not there yet Some recent progress: ? (20.3113?) `cryptography time [HJ, EUROCRYPT 10] ? (20.49999?) time if max ? [AKKN, STACS 16] Algorithm returns 20.49? almost solutions if it fails 20.49? ? ? :? ?
Representation Method [HJ10] [?] ? Seek for a set in ? List ?/2, check if ? B ? for all pairs ?,? listed ? ? gives rise to Thus we can restrict our search to 1/2?fraction of pairs as follows: [?] [?] ?/2 2?pairs (representatives) Only consider needle
Representation Method [HJ10] [?] ? Seek for a set in ? List ?/2, check if ? B ? for all pairs ?,? listed ? ? gives rise to Thus we can restrict our search to 1/2?fraction of pairs 2 /2? for Subset Sum restrict search space to only for fixed ? quickly enumerate and check candidates for ? Specifically, pick ? 2?, ?? ? ? Check all ?,? with ? ? ??, ? ? ?? ?? as follows: [?] [?] ?/2 2?pairs (representatives) ? ? ? Seems bad idea: ?/2 ? ?/2/2?candidates for ?
Concluding Remarks Crypto people have many cool algorithmic ideas Cycle finding is a great tool low space algo s Representation method gives unchampioned run times Also used to solve ?-element Set Cover in ? (21 ?5?) time, if the target Set Cover is of size ?? Win/win approach for many/few distinct sums based on smoothness subset sum distribution To improve over O (2?/2) time for Subset Sum it remains to `win in the case of few sums Thanks for listening!
