E-viri
-
Golovnev, Alexander; Posobin, Gleb; Regev, Oded; Weinstein, Omri
2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), 2020-Nov.Conference Proceeding
Proving super-logarithmic data structure lower bounds in the static group model has been a fundamental challenge in computational geometry since the early 80's. We prove a polynomial (n^{\Omega(1)}) lower bound for an explicit range counting problem of n^{3} convex polygons in \mathbb{R}^{2} (each with n^{\tilde{O}(1)} facets/semialgebraic-complexity), against linear storage arithmetic data structures in the group model. Our construction and analysis are based on a combination of techniques in Diophantine approximation, pseudorandomness, and compressed sensing-in particular, on the existence and partial derandomization of optimal binary compressed sensing matrices in the polynomial sparsity regime (k=n^{1-\delta}) . As a byproduct, this establishes a (logarithmic) separation between compressed sensing matrices and the stronger RIP property.
Vnos na polico
Trajna povezava
- URL:
Faktor vpliva
Dostop do baze podatkov JCR je dovoljen samo uporabnikom iz Slovenije. Vaš trenutni IP-naslov ni na seznamu dovoljenih za dostop, zato je potrebna avtentikacija z ustreznim računom AAI.
Leto | Faktor vpliva | Izdaja | Kategorija | Razvrstitev | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Baze podatkov, v katerih je revija indeksirana
Ime baze podatkov | Področje | Leto |
---|
Povezave do osebnih bibliografij avtorjev | Povezave do podatkov o raziskovalcih v sistemu SICRIS |
---|
Vir: Osebne bibliografije
in: SICRIS
To gradivo vam je dostopno v celotnem besedilu. Če kljub temu želite naročiti gradivo, kliknite gumb Nadaljuj.