Seminár z teoretickej informatiky - Nadia Labai (3.3.2017)

v piatok 3.3.2017 o 11:00 hod. v miestnosti M/213

28. 02. 2017 14.32 hod.
Od: Rastislav Kráľovič

Prednášajúci:  Nadia Labai

Názov: On the exact learnability of graph parameters: The case of partition functions

Temín: 3.3.2017, 11:00  hod., M/213

We discuss a new direction for research in learning theory and present proof-of-concept.
In the exact learning model, the learner can ask the teacher for the value of the target function on some input, or send the teacher a hypothesized function, and have the teacher accept the hypothesis if it is correct, or return a counterexample if it is incorrect. We say a class of functions is exactly learnable if there is a sufficiently fast learner that always finds a correct hypothesis for a function in this class.
We review how existing exact learning algorithms exploit certain algebraic properties of their target functions, and suggest developing algorithms for function classes with results of a similar flavor -- in particular, for certain classes of graph parameters.
As a first step in this direction, we present an exact learning algorithm for graph parameters which can be represented as a partition function. Examples of such parameters include: the number of independent sets, the number of k-colorings, the number of covering edge sets, and approximations of graph properties. 

The talk is about a recent paper with J.A. Makowsky, "On the exact learnability of graph parameters: The case of partition functions", which may be found here: