En k-query lokalt decodable kod (LDC) C :  på n → π N kodar varje meddelande x till ett kodord C(x) så att varje symbol av x kan probabilistically återställas genom att fråga endast k koordinater av C(x), även efter en konstant bråkdel av koordinaterna har korrumperats. Yekhanin (i J ACM 55:1-16, 2008) konstruerade en 3-query LDC av subexponentiell längd, N = exp(exp(O(log n/ log log n))), under antagandet att det finns oändligt många Mersenne primes. Efremenko (i Proceedings of the 41st annual ACM symposium on theory of computing, ACM, New York, 2009) konstruerade en 3-query LDC av längd N 2 = exp(exp( O( ε log n log n)))) utan antagande, och en 2 r-query LDC av längd N r = exp( exp( Exp( O( r log n(log log n) r−1 ))), för varje heltal r ≥ 2. Itoh och Suzuki (i IEICE Trans Inform Syst E93-D 2:263-270, 2010) gav en kompositionsmetod i Efremenko ram och konstruerade en 3 · 2 r−2 -query LDC av längd N r, för varje heltal r ≥ 4, vilket förbättrade fråge komplexiteten i Efremenkos LDC av samma längd med en faktor av 3/4. Den viktigaste ingrediensen i Efremenkos konstruktion är Grolmusz konstruktion för super-polynom storlek set-system med begränsade korsningar, över Z m, där m har en viss "bra" algebraisk egendom (relaterat till "algebraic niceness" egendom Yechanin i J ACM 55:1-16, 2008). Efremenko byggde en 3-query LDC baserad på m = 511 och vänster som ett öppet problem för att hitta andra nummer som erbjuder samma fastighet för LDC konstruktioner. I denna uppsats utvecklar vi den algebraiska teorin bakom Yekhanins konstruktioner (i J ACM 55: [1][2][3][4][5][6][8][9][10][11][13][14][15][16] 2008) och Efremenko (i det 41:a årliga ACM-symposiet om datateori, ACM, New York, 2009), i ett försök att förstå den "algebraiska finheten" 160 Chee et al. c c 22 (2013) fenomen i Z m. Vi visar att varje heltal m = pq = 2 t − 1, där p, q och t är prime, har samma goda algebraiska egendom som m = 511 som tillåter besparingar i frågekomplex. Vi identifierar 50 nummer av denna form genom datorsökning, som tillsammans med 511, sedan tillämpas för att få förbättringar på frågekomplex via Itoh och Suzukis komposition metod. Mer exakt, vi konstruerar en 3 r/2 -query LDC för varje positivt heltal r < 104 och a (3/4) 51 · 2 r -query LDC för varje heltal r ≥ 104, båda längd N r, förbättra 2 r frågor som används av Efremenko (i Proceedings av 41: a årliga ACM symposiet om teori om datorteknik, ACM, New York, 2009) och 3 · 2 r‐2 frågor som används av Itoh och Suzuki (i IEICE Trans Inform Syst E93-D 2:263-270, 2010). Vi får också nya effektiva privata system för insamling av information (PIR) från de nya frågeeffektiva de minst utvecklade länderna.
För ρ = 3 r/2 > 3, Chee et al. REF erhöll en ρ-query lokalt decodable kod längd N = exp( Exp( O( r log n(log log n) r-1 )))) under antagandet att det finns oändligt många Mersenne nummer av formen pq ( p och q är olika primer).
Query-Efficient Locally Decodable Codes of Subexponential Length
{'venue': 'computational complexity', 'journal': 'computational complexity', 'mag_field_of_study': ['Computer Science', 'Mathematics']}