Förbättring av Voronoi cellbaserade tekniker [28, 24], ger vi en Las Vegas O(2 n ) förväntad tid och utrymme algoritm för CVPP (förbehandlingsversionen av den närmaste Vector problem, CVP). Detta förbättrar på O(4 n ) deterministisk körtid för Micciancio Voulgaris algoritm [24] (härskande MV) för CVPP 1 på bekostnad av en polynom mängd slumpmässighet (som bara påverkar körtid, inte korrekthet). Som i MV, vår algoritm fortskrider genom att beräkna en kort väg på Voronoi grafen i lattice, där lattice punkter är intilliggande om deras Voronoi celler delar en gemensam aspekt, från ursprunget till en närmaste lattice vektor. Vårt huvudsakliga tekniska bidrag är en randomiserad procedur som med tanke på Voronoi relevanta vektorer av en lattice - de lattice vektorer inducera facetter av Voronoi cell - som förbearbetning och alla "nära nog" lattice pekar mot målet, beräknar en väg till en närmaste lattice vektor av förväntad polynom storlek. Detta förbättrar på O(2 n ) sökväg längd ges av MV algoritmen. Dessutom, som i MV, kan varje kant av sökvägen beräknas med hjälp av en enda iteration över de Voronoi relevanta vektorerna. Som en biprodukt av vårt arbete ger vi också ett optimalt samband mellan geometriska avstånd och stigavstånd på Voronoi-grafen, som vi anser vara av oberoende intresse.
I REF, en 3-stegs "perturbed" linje väg analyserades för att navigera över Voronoi grafen i lattice, där lattice punkter är anslutna om deras associerade Voronoi celler vidrör i en aspekt.
Short Paths on the Voronoi Graph and the Closest Vector Problem with Preprocessing
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}