E-viri
Recenzirano
Odprti dostop
-
Guo, Zeyu
Computational complexity, 12/2024, Letnik: 33, Številka: 2Journal Article
We introduce the problem of constructing explicit variety evasive subspace families . Given a family F of subvarieties of a projective or affine space, a collection H of projective or affine k -subspaces is ( F , ϵ ) -evasive if for every V ∈ F , all but at most ϵ -fraction of W ∈ H intersect every irreducible component of V with (at most) the expected dimension. The problem of constructing such an explicit subspace family generalizes both deterministic black-box polynomial identity testing (PIT) and the problem of constructing explicit (weak) lossless rank condensers. Using Chow forms, we construct explicit k -subspace families of polynomial size that are evasive for all varieties of bounded degree in a projective or affine n -space. As one application, we obtain a complete derandomization of Noether’s normalization lemma for varieties of low degree in a projective or affine n -space. In another application, we obtain a simple polynomial-time black-box PIT algorithm for depth-4 arithmetic circuits with bounded top fan-in and bottom fan-in that are not in the Sylvester–Gallai configuration, improving and simplifying a result of Gupta (ECCC TR 14-130). As a complement of our explicit construction, we prove a tight lower bound for the size of k -subspace families that are evasive for degree- d varieties in a projective n -space. When n - k = n Ω ( 1 ) , the lower bound is superpolynomial unless d is bounded. The proof uses a dimension counting argument on Chow varieties that parametrize projective subvarieties.
Avtor
![loading ... loading ...](themes/default/img/ajax-loading.gif)
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.