PSEUDO-FINITE HARD INSTANCES FOR A STUDENT-TEACHER GAME WITH A NISAN-WIGDERSON GENERATOR

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F12%3A10127159" target="_blank" >RIV/00216208:11320/12:10127159 - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/67985840:_____/12:00385494

Výsledek na webu

<a href="http://dx.doi.org/10.2168/LMCS-8(3:09)2012" target="_blank" >http://dx.doi.org/10.2168/LMCS-8(3:09)2012</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.2168/LMCS-8(3:09)2012" target="_blank" >10.2168/LMCS-8(3:09)2012</a>

Jazyk výsledku

angličtina

Název v původním jazyce

PSEUDO-FINITE HARD INSTANCES FOR A STUDENT-TEACHER GAME WITH A NISAN-WIGDERSON GENERATOR

Popis výsledku v původním jazyce

For an NP boolean AND coNP function g of the Nisan-Wigderson type and a string b outside its range we consider a two player game on a common input a to the function. One player, a computationally limited Student, tries to find a bit of g(a) that differsfrom the corresponding bit of b. He can query a computationally unlimited Teacher for the witnesses of the values of constantly many bits of g(a). The Student computes the queries from a and from Teacher's answers to his previous queries. It was proved in [Kra11b] that if g is based on a hard bit of a one-way permutation then no Student computed by a polynomial size circuit can succeed on all a. In this paper we give a lower bound on the number of inputs a any such Student must fail on. Using that we show that there is a pseudo-finite set of hard instances on which all uniform students must fail. The hard-core set is defined in a non-standard model of true arithmetic and has applications in a forcing construction from [Kra11a].

Název v anglickém jazyce

PSEUDO-FINITE HARD INSTANCES FOR A STUDENT-TEACHER GAME WITH A NISAN-WIGDERSON GENERATOR

Popis výsledku anglicky

For an NP boolean AND coNP function g of the Nisan-Wigderson type and a string b outside its range we consider a two player game on a common input a to the function. One player, a computationally limited Student, tries to find a bit of g(a) that differsfrom the corresponding bit of b. He can query a computationally unlimited Teacher for the witnesses of the values of constantly many bits of g(a). The Student computes the queries from a and from Teacher's answers to his previous queries. It was proved in [Kra11b] that if g is based on a hard bit of a one-way permutation then no Student computed by a polynomial size circuit can succeed on all a. In this paper we give a lower bound on the number of inputs a any such Student must fail on. Using that we show that there is a pseudo-finite set of hard instances on which all uniform students must fail. The hard-core set is defined in a non-standard model of true arithmetic and has applications in a forcing construction from [Kra11a].

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

<a href="/cs/project/IAA100190902" target="_blank" >IAA100190902: Matematická logika, složitost a algoritmy</a><br>

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2012

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

Logical Methods in Computer Science

ISSN

1860-5974

e-ISSN

—

Svazek periodika

8

Číslo periodika v rámci svazku

3

Stát vydavatele periodika

DE - Spolková republika Německo

Počet stran výsledku

8

Strana od-do

1-8

Kód UT WoS článku

000309447200009

EID výsledku v databázi Scopus

—