Efficient Subset Sum and Related Problems Overview

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

0100111100100 0001010000110 0001101010010 Subset Sum Given integers ?1, ,??,? find ? ? with ? ???= ? ?(??) time by DP ? ? + ? randomized time B(SODA 17) ?(??) randomized time, poly space B(SODA 17) ? (2?) time, poly space (? omits poly factors in input) ? (2?/2) time, ? (2?/2) space HS(JACM72) ? (2?/2) time, ? (2?/4) space SS(SICOMP81) Can solve any instance in either ? (20.49991?) time or ? (20.999?) time and poly space AKKN(STACS 16) Algo i th bit? ????(?) time 0/1 Main Result: There is a Monte Carlo algorithm for Subset Sum using ? (20.86?) time and poly space, assuming random read-only access to random bits

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

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

Element Distinctness (ED): BCM(FOCS13) Given z ??with ? ????(?), are all values distinct? Unlimited space: ?(?) time (sort) ?(log ?) space: ?(?2) time (brute-force) Suppose ? ? ??; find a repeated value-pair whp Unlimited space: ?( ?) time ( ?( ?) samples) ?(????) space: ?(?) time ( ?(1) samples and compare) Theorem(BCM): ?(?1.5) time, ?(log?) space, assuming random read-only access to random bits We ll first see ?( ?) time, ?(log?) space if ? ? ?? Approach: set ? ? = ??, and use cycle finding to find ? ? such that ? ? = ? ?

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

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 in first round (6 in ex) p= stem-length (3 in ex), q=cycle length (6 in ex) 2T=T+xq -> T=xq -> T+p=xq+p

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 assuming ? is random: ? and ? are ?( ?) whp (birthday paradox)

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

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

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 ? n ? time, ?(log?) space algorithm for List Disjointness, if given ? ?,? ? assuming random read-only access to random bits

List Disjointness Theorem: There is an ? 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 1/2 Sample ?,? such that ? ? = ?(?) as before If ? ? = ?(?) and ? ?, also check ??= ??or ??= ?? Need ?(?,?) samples Expect ?(?/ ?(?,?)) vertices needed for a sample

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)

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

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?-> 2?time How do instances with ? ? 20.99?look?

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)

Subset Sum Distribution is smooth (AKKN) Lemma: ? ? |{? ? :? ?}| 6?/2 Note: 6?/2< 21.3? ?? ?(?) |{? ? :? ?}| 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

Subset Sum Distribution is smooth (AKKN) Lemma: ? ? |{? ? :? ?}| 6?/2 Note: 6?/2< 21.3? 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 Cor: If ? ? :? ? ? (2?/220.99?) = ? (20.995?) time and poly space, assuming random read-only access to random bits Proof of Lemma uses a connection to UDCP s

Uniquely Decodable Code Pairs (UDCP) Pair ?1,?2 {0,1}?s.t. ?1+ ?2 = ?1|?2|. ?1+ ?2= {x + y: x,y ?1 ?2}, x + y is addition over ?. ?11011100 1101101 0000000 1010011 0101010 1111101 1100111 1100111 1011100 1101101 0000000 1010011 0101010 1111101 1 0 1 0 0 1 1 1 0 ?? 2 1 ?20011001 1010101 0011011 0110110 0110110 0011001 1010101 0011011 0 0 1 1 0 1 1 0 1 0

Uniquely Decodable Code Pairs (UDCP) Pair ?1,?2 {0,1}?s.t. ?1+ ?2 = ?1|?2|. ?1= {10,01},?2= {00,01,11} is UDCP: ?1+ ?2= {10,11,21,01,02,12} ?1+ ?2 {0,1,2}? 3? Side remark: In general ?1||?2 21.5?is best known (elegant upper bound, might tell afterwards)

Subset Sum Distribution is smooth (AKKN) Lemma: ? ? |{? ? :? ?}| 6?/2 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 |? + ??| = ? |??| (i.e. ?,??is a UDCP): Suppose ?1+ ?1= ?2+ ?2(add in ?/2) ? (?1+ ? ?1) = ? (?2+ ? ?2) ? (?1+ ? ?1) = ? (?2+ ? ?2) ? ?1+ ? ?1) = ? ?2+ ? ?2) ? ?1+ ? ?1) = ? ?2+ ? ?2) ?1= ?2 ?1= ?2 Thus ? ?? = ? + ?? 3?/2 lemma follows: ? ? ? ??2?/2? 6?/2

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

Subset Sum with few Distinct Sums Lemma: Can solve instance ?1, ,??,? in time O ( ? ? :? ? ) and poly 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 poly space, assuming random read-only access to random bits Omitted optimization to get the ? (20.86?)

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

Further Results Theorem: Binary LP on ? vars, ? constraints, max int ? in time ? 20.86?log ?? ?? ? assuming random read-only access to random bits and poly space, Using reduction to Subset Sum NvLvdZ (MFCS 12) Established by simple recursive rounding scheme Theorem: Random 3-Sum in ?(?2.5) time and log? space if ints independently and u.a.r from [?] with ? ????(?) being a multiple of ? Time/space tradeoffs for List Disjointness By extending techniques from BCM List Disjointness in ?(? ?/?) time given ? ?2/? space

Further Research How strong is random oracle assumption exactly? Weaker than the existence of sufficiently strong PRG s Still don t know exact (low-space) complexity of ED!! Can we do something specific for SSS? Solve Subset Sum in time ? 20.5 ? ? Can restrict to ?1, ,??,,? 20.997?AKKN (STACS 16) Show ?1 ?2 21.49999?for UDCP ?1,?2 {0,1}? True if ?1 20.995?AKKN (ISIT 16) Big open question in information theory Study Subset Sum combinatorics If spike of size 2??for some constant ? > 0, bound |{? ? :? [?]}| 21 ? ?for some ? ?(?) > 0

Take-home Messages Cycle finding is a great tool low space algo s Several worst-case algo s for SSS are inspired on techniques from the literature of average-case complexity of SSS: Cycle finding in poly space setting (this work) Howgrave-Graham approach in exp. space setting (AKKN) Win/win approach for many/few distinct sums In exponential space setting it remains to `win in the case of few sums Thanks for listening!!