Deterministic Constructions of High-Dimensional Sets with Small Dispersion

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21340%2F22%3A00363911" target="_blank" >RIV/68407700:21340/22:00363911 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1007/s00453-022-00943-x" target="_blank" >https://doi.org/10.1007/s00453-022-00943-x</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s00453-022-00943-x" target="_blank" >10.1007/s00453-022-00943-x</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Deterministic Constructions of High-Dimensional Sets with Small Dispersion

Popis výsledku v původním jazyce

The dispersion of a point set P subset of[0,1](d) is the volume of the largest box with sides parallel to the coordinate axes, which does not intersect P. It was observed only recently that, for any epsilon > 0, certain randomized constructions provide point sets with dispersion smaller than e and number of elements growing only logarithmically in d. Based on deep results from coding theory, we present explicit, deterministic algorithms to construct such point sets in time that is only polynomial in d. Note that, however, the running-time will be super-exponential in epsilon-1. Our construction is based on the apparently new insight that low-dispersion point sets can be deduced from solutions of certain k-restriction problems, which are well-known in coding theory.

Název v anglickém jazyce

Deterministic Constructions of High-Dimensional Sets with Small Dispersion

Popis výsledku anglicky

The dispersion of a point set P subset of[0,1](d) is the volume of the largest box with sides parallel to the coordinate axes, which does not intersect P. It was observed only recently that, for any epsilon > 0, certain randomized constructions provide point sets with dispersion smaller than e and number of elements growing only logarithmically in d. Based on deep results from coding theory, we present explicit, deterministic algorithms to construct such point sets in time that is only polynomial in d. Note that, however, the running-time will be super-exponential in epsilon-1. Our construction is based on the apparently new insight that low-dispersion point sets can be deduced from solutions of certain k-restriction problems, which are well-known in coding theory.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

<a href="/cs/project/8X20043" target="_blank" >8X20043: Časově frekvenční reprezentace prostoru funkcí</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2022

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Algorithmica

ISSN

0178-4617

e-ISSN

1432-0541

Svazek periodika

84

Číslo periodika v rámci svazku

7

Stát vydavatele periodika

DE - Spolková republika Německo

Počet stran výsledku

19

Strana od-do

1897-1915

Kód UT WoS článku

000761826900001

EID výsledku v databázi Scopus

2-s2.0-85132556754