Faster Space-Efficient Algorithms for Subset Sum

This research discusses faster and space-efficient algorithms for Subset Sum and related problems, introducing techniques like Meet-in-the-Middle (MitM) approach and Monte Carlo algorithm. It also covers topics such as Floyds Cycle Finding, Element Distinctness (ED) by BCM, List Disjointness, and Subset Sum distributions. The research presents advancements in solving subset sum problems with improved time complexity and space efficiency.

• Algorithms
• Subset Sum
• Space-Efficient
• Monte Carlo
• Meet-in-the-Middle

smarc Follow

Uploaded on Sep 19, 2024 | 0 Views

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. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. Faster Space-Efficient Algorithms for Subset Sum, k-Sum and related problems (available at arXiv:1612.02788) Nikhil Bansal, Shashwat Garg, Jesper Nederlof, Nikhil Vyas disclaimer: no turtles or hares were harmed during this research

2. 0100111100100 0001010000110 0001101010010 Subset Sum Given: integers ?1, ,??,? Asked: is there an ? ? with ? ???= ?? Focus on instances with small ? The `classic results: ? (2?) time, ? (1) space (trivial) ? (2?/2) time, ? (2?/2) space HS(JACM72) Introduces `Meet-in-the-Middle (MitM) approach ? (2?/2) time, ? (2?/4) space SS(SICOMP81) Algo i th bit? ? (1) time 0/1 Main Result: There is a Monte Carlo algorithm for Subset Sum using ? (20.86?) time and ? 1 space, assuming random read-only access to random bits

3. BCM (FOCS13): Shuffle function Floyd: Cycle Finding HS (JACM72): MitM Crypto: List merging BCM:Element Distinctness AKKN (STACS16): Subset Sum distribution is smooth List Disjointness (with small freqs2) Hash mod p LN(STOC10): Save space with DFT Subset Sum (few distinct sums) Subset Sum (many distinct sums) Subset Sum

4. BCM (FOCS13): Shuffle function Floyd: Cycle Finding BCM:Element Distinctness

5. Element Distinctness (ED) by BCM Given list z ??with ? ????(?) Asked if all values are distinct In ?(?) time, ?(?) space, ?(?2) time, ? log? space Theorem(BCM): ?(?1.5) time, ?(log?) space, assuming random read-only access to random bits To prove, let s first assume ? = ?, and let ? ? := ?? Thus we seek ? ? with ? ? = ?(?)

6. Floyds Cycle Finding Finds such ?,? using little space Basic algo in crypto, much more obscure in TCS View ? as digraph (with arcs (?,?(?))) s

7. Floyds Cycle Finding Finds such ?,? using little space Basic algo in crypto, much more obscure in TCS View ? as digraph (with arcs (?,?(?))) i s j T = #steps turtle (6 in ex) p= stem-length (3 in ex), q=cycle length (6 in ex) 2T=T+xq -> T=xq -> T+p=xq+p

8. Floyds Cycle Finding Finds such ?,? using little space Basic algo in crypto, much more obscure in TCS View ? as digraph (with arcs (?,?(?))) i s j Only works if start outside cycle! Works well if ? is random: Probly ? reached after ?( ?) steps (birthday paradox)

9. `Shuffling f Theorem(BCM): ?(?1.5) time, ?(log?) space, assuming random read-only access to random bits What if ? is not random? `shuffle ? Let : ? [?] be a random function Cannot remember , but use assumed oracle Define ? ? = ?? Use Floyd to sample ? ? such that ? ? = ?(?) (?,?) is a bad pair if ?? = (??) but ?? ?? Expect at most ?2/? bad pairs Using ? ? samples, expect to see real solution

10. BCM (FOCS13): Shuffle function Floyd: Cycle Finding Crypto: List merging BCM:Element Distinctness List Disjointness (with small freqs2)

11. List Disjointness Given two lists ?,? ??, ? ????(?) Asked do they share a common value? ? = (1, 9, 2, 4, 9, 4, 6, 5, 2) Very similar to ED; but want values from different lists 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 O n ? time, ?(log?) space algorithm for List Disjointness, if given ? ?,? ? assuming random read-only access to random bits

12. List Disjointness Theorem: There is an O n ? time, ?(log?) space algorithm for List Disjointness, if given ? ?,? ? assuming random read-only access to random bits Define ? ??by merging ?,? E.g. just concatenate ? and ? In paper we set ??:= ??or ??:= ??with prob .5 Sample ?,? such that ? ? = ?(?) as before If ? ? = ?(?) and ? ?, also check ??= ??or ??= ?? Need ?(?,?) samples Expect ?(?/ ?(?,?)) vertices needed for a sample

13. BCM (FOCS13): Shuffle function Floyd: Cycle Finding HS (JACM72): MitM Crypto: List merging BCM:Element Distinctness List Disjointness (with small freqs2) Subset Sum (many distinct sums)

14. Meet in the Middle 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

15. Meet in the Middle 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, ,??? ? new ? = ? ? ? = ? ? ? ? ? ? ? ? 1 space, ? (2?/2?) time ? ? = {?,? ?:? ? = ? ? } 2? If ??= 0, ? ? ,? ? = 2?and no improvement How do instances with ? ? 20.99?look?

16. BCM (FOCS13): Shuffle function Floyd: Cycle Finding HS (JACM72): MitM Crypto: List merging BCM:Element Distinctness AKKN (STACS16): Subset Sum distribution is smooth List Disjointness (with small freqs2) Subset Sum (many distinct sums)

17. Subset Sum Distribution is smooth (AKKN) 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

18. Subset Sum Distribution is smooth (AKKN) Lemma: ? ? |{? ? :? ?}| 6?/2 We use this as follows: Suppose ? ? :? ? ? ? :? ? and thus ? ? 6?/2/20.49? 20.99? 20.99?then 20.49? 20.99?, can solve SSS in Lemma: If ? ? :? ? ? (2?/220.99?) = ? (20.995?) time and ? 1 space, assuming random read-only access to random bits

19. Subset Sum Distribution is smooth (AKKN) Lemma: ? ? |{? ? :? ?}| 6?/2 Proof sketch: There exists a frequent sum ? s.t. Bv= {? 0,1?/2:? ? = ?}; ?? ?(?)/2?/2 Let ? {0,1}?/2be such that for all ?1,?2 ? ?1 ? = ?2 ? implies ?1= ?2 Then |? + ??| = ? |??|: Suppose ?1+ ?1= ?2+ ?2(add in ?/2) ? (?1+ ? ?1) = ? (?2+ ? ?2) ? (?1+ ? ?1) = ? (?2+ ? ?2) ? ?1+ ? ?1) = ? ?2+ ? ?2) ? ?1+ ? ?1) = ? ?2+ ? ?2) ? + ?? {0,1,2}?/2 Thus ? ?? = ? + ?? 3?/2 ?1= ?2 ?1= ?2

20. BCM (FOCS13): Shuffle function Floyd: Cycle Finding HS (JACM72): MitM Crypto: List merging BCM:Element Distinctness AKKN (STACS16): Subset Sum distribution is smooth List Disjointness (with small freqs2) Hash mod p + DFT Subset Sum (few distinct sums) Subset Sum (many distinct sums) Subset Sum

21. Subset Sum with few Distinct Sums Lemma: Can solve instance ?1, ,??,? in time O ( ? ? :? ? ) and ? 1 space. Done by hashing numbers mod a prime of order ? ? :? ? and run ? ? time ? (1) space algorithm, that uses DFT. Combining with previous lemma we obtain Main Result : There is a Monte Carlo for Subset Sum using ? (20.995?) time and ? 1 space, assuming random read-only access to random bits Left out many optimization to get ? (20.86?)

22. BCM (FOCS13): Shuffle function Floyd: Cycle Finding HS (JACM72): MitM Crypto: List merging BCM:Element Distinctness AKKN (STACS16): Subset Sum distribution is smooth List Disjointness (with small freqs2) Hash mod p + DFT Subset Sum (few distinct sums) Random k-Sum Subset Sum (many distinct sums) Subset Sum Knapsack & Binary Linear Programming NvdZvL (MFCS12):Reduce without adding variables

23. Further Results Theorem: Binary LP on ? vars and ? constraints in ? 20.86?log ?? ?? ? is max integer, assuming random read-only access to random bits time and ? (1) space where ? Using reduction to Subset Sum Also time/space tradeoffs for List Disjointness using methods of BCM List Disjointness in ? (? ?/?) time given ? ?2/? space.

24. Further Research How strong is random bits assumptions exactly? Weaker than the existence of sufficiently strong PRG s Still don t know the exact (low-space) complexity of ED!! Can we do something problem specific? Solve Subset Sum in time ? 20.5 ? ? Great open question, progress made recently (AKKN) Study Subset Sum combinatorics Connection by AKKN relates this to UDCP s If spike of size 2??for some constant ? > 0, upper bound #?? 21 ? ?for some ? > 0 depending on ? > 0

25. Take-home Messages Cycle finding is a great tool low space algo s Win/win approach for many/few distinct sums Thanks for listening!! Slides available at http://www.win.tue.nl/~jnederlo/; paper available at arXiv