Vi uppvisar ett genomsnittsproblem som är lika svårt som att hitta γ(n)-ungefär kortaste icke-nollvektorer i vissa ndimensionella gitter i värsta fall, för γ(n) = O( ε log n). Den tidigare mest kända faktorn för en icke-trivial klass av lattices var γ(n) = Õ(n). Våra resultat gäller familjer av gitter med speciell algebraisk struktur. Specifikt anser vi gitter som motsvarar ideal i ringen av heltal av ett algebraiskt nummerfält. Det värsta problemet vi förlitar oss på är att hitta ungefärliga kortaste vektorer i dessa gitter, under en lämplig form av förbehandling av nummerfältet. För de anslutningsfaktorer γ(n) vi uppnår, motsvarande beslutsproblem om idealiska gitter är inte kända för att vara NP-hård; i själva verket, de är i P. Men, sök approximation problem verkar fortfarande vara mycket svårt. I själva verket, idealiska gitter är välstuderade objekt i beräkningstal teori, och de mest kända algoritmer för dem verkar inte utföra något bättre än de mest kända algoritmer för allmänna gitter. För att få bästa möjliga anslutningsfaktor, vi omedelbart våra konstruktioner med oändliga familjer av nummerfält som har konstant rot discriminant. Sådana familjer är kända för att existera och kan beräknas, även om det ännu inte finns någon effektiv konstruktion. Vårt arbete motiverar sökandet efter sådana konstruktioner. Även konstruktioner av nummerfält som har rotdiskriminant upp till O(n 2/3− ) skulle ge kopplingsfaktorer bättre än Õ(n). Som ytterligare ett bidrag ger vi minskningar mellan olika värsta tänkbara problem på idealiska gitter, vilket till exempel visar att det kortaste vektorproblemet inte är svårare än det närmaste vektorproblemet. Dessa resultat är jämförbara med tidigare kända minskningar för allmänna gitter.
Till exempel, vissa beslutsproblem i den idealiska lattice familjen med konstant rot discriminant är i P medan motsvarigheterna till allmänna lattice är NP-hård REF.
Lattices that admit logarithmic worst-case to average-case connection factors
{'venue': "STOC '07", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}