Seminar of Theoretical Computer Science - Nadia Labai (3.3.2017)

Friday 3.3.2017 at 11:00, Lecture room M/213

---

Nadia Labai:
On the exact learnability of graph parameters: The case of partition functions

Abstract:
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: https://arxiv.org/abs/1606.04056 

web:  http://kedrigern.dcs.fmph.uniba.sk/STI2 
rss:  http://kedrigern.dcs.fmph.uniba.sk/STI2/rss.php

 

 

---