Vi studerar certifikat i statiska datastrukturer. I cellsondmodellen är certifikaten de cellsonder som unikt kan identifiera svaret på frågan. Som en naturlig uppfattning av icke-deterministiska cellsonder, lägre gränser för certifikat i datastrukturer omedelbart innebär deterministiska cell-prob lägre gränser. Trots denna extra kraft som orsakas av icke-determinism, bevisar vi att två allmänt använda verktyg för cell-probe nedre gränser: rikedom lemma av Miltersen et al. [10] och direktsumma rikhet lemma av P skatraşcu och Thorup [17], båda innehar för certifikat i datastrukturer med ännu bättre parametrar. Genom att tillämpa dessa lemmas och anta befintliga minskningar, får vi certifikat nedre gränser för en mängd olika statiska datastruktur problem. Dessa certifikat nedre gränser är minst lika bra som de högsta kända cell-sonder nedre gränser för respektive problem. I synnerhet för ungefärligt nära granne (ANN) problem i hamming avstånd, vår nedre gräns förbättrar den senaste tekniken. När utrymmet är strikt linjärt, vår lägre gräns för ANN i d-dimensionella Hamming utrymme blir t =  och (d), som tillsammans med det senaste genombrottet för polynom utvärdering av Larsen [8], är de enda två t =  på (d) lägre gränser någonsin bevisat för eventuella problem i cell-sonden modellen.
Som tidigare nämnts är den högsta cellprob nedre gränsen för dynamisk ANN den statiska (d/ lg(sw/dn)) nedre gränsen för Wang och Yin REF.
Certificates in Data Structures
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}