Bounds for Unbalanced Uniquely Decodable Code Pairs Study
Explore the study on Sharper Upper Bounds for Unbalanced Uniquely Decodable Code Pairs by Jesper Nederlof and collaborators, focusing on isoperimetric inequality, warm-up bound, and main bound. Discover the implications for additive combinatorics and delve into the history of uniquely decodable code pairs. Delve into the main question of determining the maximum size of the code pairs, along with a reference to past works on the subject.
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
Sharper Upper Bounds for Unbalanced Uniquely Decodable Code Pairs Jesper Nederlof ISIT 2016 Joint work with Per Austrin, Petteri Kaski and Mikko Koivisto HIIT+Aalto University, Helsinki HIIT, Helsinki KTH, Stockholm
Outline Introduction + brief overview previous work Our approach Isoperimetric inequality Warm-up bound Sketch main bound Our motivation for this problem: A consequence for additive combinatorics Further remarks and research
? + ? = {a + b: a,b ? ?}, a + b is addition over ?. Uniquely Decodable Code Pairs (UDCP) Pair ?,? {0,1}? s.t. ? + ? = ? |?|. ? = {10,01},? = {00,01,11} is UDCP: ? + ? = {10,11,21,01,02,12} Is ? = 001,010,101 ,? = {011,110,111} UDCP? No: 001+111=101+011 If ? + ? = ? |?|, then ? ? = ? |?|: If ?1 ?1= ?2 ?2 then ?1+ ?2= ?2+ ?1
? + ? = {a + b: a,b ? ?}, a + b is addition over ?. Uniquely Decodable Code Pairs (UDCP) Pair ?,? {0,1}? s.t. ? + ? = ? |?|. ? = {10,01},? = {00,01,11} is UDCP: ? + ? = {10,11,21,01,02,12} 1011100 1101101 0000000 1010011 0101010 1111101 1100111 1100111 1011100 1101101 0000000 1010011 0101010 1111101 Unbalanced: ? huge 1 0 1 0 0 1 1 1 0 ?? ? 2 1 ? 0011001 1010101 0011011 0110110 0110110 0011001 1010101 0011011 0 0 1 1 0 1 1 0 1 0
Some (incomplete) History ? = 2??, ? = 2??. Main Question: How large can ? + ? be? If (A,B) is UDCP, so is ({?1?2:?1,?2 ?}, {?1?2:?1,?2 ?}) So whenever ? even, previous example gives ? = 2?/2, ? = 3?/2 ? = .5,? 0.792, ? + ? 1.292 Kasami & Lin 76 ? + ? 1.292
Some (incomplete) History ? = 2??, ? = 2??. Several works: ? + ? 1.5 Define ??= { ?,? ? ?:|? ?| = ?} |??| ? + ? or ? ? determines ?,? (? ?,? b) or (? ?,? ?) determines ? + ?,? ? sym. difference ? ?2min ?,? ?(vT 78) ? + ? 1.5 Ahlswede 71 Liao 72 Lindstr m 72 v Tilborg 78 Kasami & Lin 76 ? + ? 1.292
Some (incomplete) History ? = 2??, ? = 2??. Several works: ? + ? 1.5 Define ??= { ?,? ? ?:|? ?| = ?} |??| ? + ? or ? ? determines ?,? (? ?,? b) or (? ?,? ?) determines ? + ?,? ? sym. difference ? ?2min ?,? ?(vT 78) ? + ? 1.5 ? 1 ? 1 ? 0.25 Ahlswede 71 Liao 72 Lindstr m 72 Kasami et al. 82 v Tilborg 78 Mattas & sterg rd 05 v Tilborg 83 vd Braak 84 Kasami & Lin 76 ? + ? 1.292 ? + ? 1.31781 v Tilborg & vd Braak 85 ? + ? 1.30366
Some (incomplete) History ? = ?1 1 gives ? = ?2 < 0.4922. ? + ? 1.5 ? 1 ? 1 ? 0.25 Ahlswede 71 Liao 72 Lindstr m 72 Urbanke & Li 98 Kasami et al. 82 v Tilborg 78 Mattas & sterg rd 05 ? + ? 1.31781 v Tilborg 83 vd Braak 84 Kasami & Lin 76 ? + ? 1.292 v Tilborg & vd Braak 85 ? + ? 1.30366
Some (incomplete) History ? = ?1 1 gives ? = ?2 < 0.4798. ? + ? 1.5 ? 1 ? 1 ? 0.25 Ahlswede 71 Liao 72 Lindstr m 72 Urbanke & Li 98 Kasami et al. 82 v Tilborg 78 Mattas & sterg rd 05 v Tilborg 83 vd Braak 84 Ordentlich & Shayevitz 15 Kasami & Lin 76 ? + ? 1.292 ? + ? 1.31781 v Tilborg & vd Braak 85 ? + ? 1.30366
Some (incomplete) History ? + ? 1.5 ? + ? 1.5 0 From Schleger & Grant `coordinated multiuser communications ? 1 ? 1 ? 0.25 Ahlswede 71 Liao 72 Lindstr m 72 Urbanke & Li 98 Kasami et al. 82 v Tilborg 78 Mattas & sterg rd 05 v Tilborg 83 vd Braak 84 Ordentlich & Shayevitz 15 Kasami & Lin 76 ? + ? 1.292 ? + ? 1.31781 v Tilborg & vd Braak 85 ? + ? 1.30366
Some (incomplete) History .48 .42 .44 .46 .5 Our main result: ? 0.4229+ ? ? ? + ? 1.5 ? + ? 1.5 0 From Schleger & Grant `coordinated multiuser communications ? 1 ? 1 ? 0.25 Ahlswede 71 Liao 72 Lindstr m 72 Urbanke & Li 98 Kasami et al. 82 v Tilborg 78 We Mattas & sterg rd 05 v Tilborg 83 vd Braak 84 Ordentlich & Shayevitz 15 Kasami & Lin 76 ? + ? 1.292 ? + ? 1.31781 v Tilborg & vd Braak 85 ? + ? 1.30366
Isoperimetric Inequality For ? {0,1}?,0 ? 1, y ?? is a ?-noisy copy of y: with probability1 + ? ??, , 2 ??= 1 ??,with probability1 ? B . 2 ? 0?: ? uniform ? 1?: ? = ? =1 ? ? ??:? ? ? Theorem (Mossel et al.): 1 ? + 1 ? +2? A 2 1 ? 1 ? ? 1 ?2 2 Pr ? ??[? ?,? ?]
Warm-up bound Large fraction of a,b ? ?are close in HD by iso. ineq But only few can be close pairs by vT s bound (*similar tension between vT s bound and iso. ineq used by UL) 1 ? + 1 ? +2? 1 ? 1 ? ? 1 ?2 2 ? ? ? 1 + ? 2 1 ? 2 ? ??[? ?,? ?] = 2 ? Pr |??| ? ? ? ? 1+? 2 1 ? 2 ? ?2? 2 ? ? 2 2?3 ??. Setting ? = 0.3838 gives ? 0.4777 + 2 ? Intuitively, we lower and upper bound |??| for some ?
Main Bound Let ? = 2??, ? = 2??. Think ? = 1 ? for small ?. Isoperimetric inequality is tight if A and B Hamming balls far away from each other. But then A,B cannot be a good UDCP B We argue in two steps: 1. ? has to be spread out using an encoding argument 2. Use this for a refined version of the warm-up bound A
Main Bound ? projected to ? Step 1: with an encoding argument, find a partition ?,? of {1, ,?} such that ? , ? ?/2, ?? 2? ? ? Step 2: Study the number of pairs ?,? ? ? with |?? ??| small and ?? ?? |?|/2 Lower bound with iso. ineq. using ? = 0.654 on L, ? = 0 on R Upper bound by encoding argument ?? ?? ?? ??
Our Motivation Let ? ?. We study two parameters ? ? = max ? ?(?) = |{? ?:? {0,1}?}| If ? ? 21 ? ? for small ?, upper bound ?(?) Useful for finding faster algo s for Subset Sum problem Similar to `Inverse Littlewood-Offord questions in additive combinatorics ? {0,1}?:? ? = ?
?(?) ?(?) w Histogram 0 0 0 0 0 32 1 1 2 4 8 16 32 64 128 256 512 1024 1 2048 1 2 3 4 5 3 16 3 20 58 90 267 493 869 961 1000 1153 1246 1598 1766 1922 9 7005
Connection to UDCPs Let ? {0,1}? be s.t. for all ?1,?2 ?: ? ?1= ? ?2 implies ?1= ?2 Let ? {0,1}? be s.t. for all ?1,?2 ?: ?1= ? ?2 Can take ? = |?(?)|, ? = ? ? (?,?) is UDCP: suppose ?1,?2 ?,?1,?2 ? ?1+ ?1= ?2+ ?2 ? (?1+ ? ?1) = ? (?2+ ? ?2) ? (?1+ ? ?1) = ? (?2+ ? ?2) ? (?1+ ? ?1) = ? (?2+ ? ?2) ?
Connection to UDCPs Let ? {0,1}? be s.t. for all ?1,?2 ?: ? ?1= ? ?2 implies ?1= ?2 Let ? {0,1}? be s.t. for all ?1,?2 ?: ?1= ? ?2 Can take ? = |?(?)|, ? = ? ? (?,?) is UDCP: suppose ?1,?2 ?,?1,?2 ? ?1+ ?1= ?2+ ?2 ? (?1+ ? ?1) = ? (?2+ ? ?2) ? (?1+ ? ?1) = ? (?2+ ? ?2) ? (?1+ ? ?1) = ? (?2+ ? ?2) ?
Connection to UDCPs Let ? {0,1}? be s.t. for all ?1,?2 ?: ? ?1= ? ?2 implies ?1= ?2 Let ? {0,1}? be s.t. for all ?1,?2 ?: ?1= ? ?2 Can take ? = |?(?)|, ? = ? ? (?,?) is UDCP: suppose ?1,?2 ?,?1,?2 ? ?1+ ?1= ?2+ ?2 ? (?1+ ? ?1) = ? (?2+ ? ?2) ? (?1+ ? ?1) = ? (?2+ ? ?2) ? (?1+ ? ?1) = ? (?2+ ? ?2) ? (?1+ ?1= ?2 ?1= ?2 ?
Connection to UDCPs Let ? {0,1}? be s.t. for all ?1,?2 ?: ? ?1= ? ?2 implies ?1= ?2 Let ? {0,1}? be s.t. for all ?1,?2 ?: ?1= ? ?2 ? Corollaries: ? ? ? ? 21.5? If ? ? 21 ? ?, ? ? 2(0.4223+ ?)?
Further Remarks OS also used a projection property We use UDCP property to prove projection property Can ? + ? = 1.5? Can provided methods be used to exclude this? If ? 1, sharpen 0.25 ? 0.4223 Let ? ? 2??,? > 0. Is there ? ? ? s.t. ? ? 21 ? ?? Thanks for listening!
