Unambiguous parity-query complexity
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F25%3A00635633" target="_blank" >RIV/67985840:_____/25:00635633 - isvavai.cz</a>
Výsledek na webu
<a href="https://doi.org/10.1002/rsa.70010" target="_blank" >https://doi.org/10.1002/rsa.70010</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1002/rsa.70010" target="_blank" >10.1002/rsa.70010</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Unambiguous parity-query complexity
Popis výsledku v původním jazyce
We give a lower bound of (Formula presented.) on the unambiguous randomized parity-query complexity of the approximate majority problem—that is, on the lowest randomized parity-query complexity of any function over (Formula presented.) whose value is “ (Formula presented.) ” if the Hamming weight of the input is at most (Formula presented.), is “ (Formula presented.) ” if the weight is at least (Formula presented.), and may be arbitrary otherwise.
Název v anglickém jazyce
Unambiguous parity-query complexity
Popis výsledku anglicky
We give a lower bound of (Formula presented.) on the unambiguous randomized parity-query complexity of the approximate majority problem—that is, on the lowest randomized parity-query complexity of any function over (Formula presented.) whose value is “ (Formula presented.) ” if the Hamming weight of the input is at most (Formula presented.), is “ (Formula presented.) ” if the weight is at least (Formula presented.), and may be arbitrary otherwise.
Klasifikace
Druh
J<sub>imp</sub> - Článek v periodiku v databázi Web of Science
CEP obor
—
OECD FORD obor
10101 - Pure mathematics
Návaznosti výsledku
Projekt
<a href="/cs/project/GA25-16311S" target="_blank" >GA25-16311S: Složitost výpočtů, komunikace, a vyhledávání</a><br>
Návaznosti
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Ostatní
Rok uplatnění
2025
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ů
Údaje specifické pro druh výsledku
Název periodika
Random Structures and Algorithms
ISSN
1042-9832
e-ISSN
1098-2418
Svazek periodika
66
Číslo periodika v rámci svazku
3
Stát vydavatele periodika
US - Spojené státy americké
Počet stran výsledku
17
Strana od-do
e70010
Kód UT WoS článku
001497708000005
EID výsledku v databázi Scopus
2-s2.0-105005225562