Query-Efficient Computation in Property Testing and Learning Theory

Hoe kunnen we rekenkundige problemen oplossen wanneer we simpelweg niet genoeg tijd hebben om alle invoer te verwerken? Binnen de theoretische informatica wil men inzicht krijgen in de grenzen van de rekenkracht van verschillende rekenmodellen. Ook houdt men zich bezig met het karakteriseren van de middelen die nodig zijn om bepaalde problemen op te lossen. Dit soort problemen zijn bij uitstek geschikt om bestudeerd te worden met het property testing model (het testen van eigenschappen). Bij property testing wordt met algoritmen onderscheid gemaakt tussen objecten die een gewenste eigenschap hebben, en objecten die daar ver vandaan staan. David García Soriano zocht gerandomiseerde testers die problemen met zo min mogelijk functie-aanroepen oplossen (bovengrenzen), alsook rigoureuze bewijzen die laten zien waarom er geen significant betere oplossingen kunnen bestaan (ondergrenzen). Hij maakte daarbij onder meer gebruik van technieken uit de kansrekening, grafentheorie en getallentheorie.

• View at Worldcat