Property Testing & PAC Learning
| Talking persons: |
| Tobias Brunsch |
| Abstract: |
| Es geht um das Testen und Lernen Boolescher Funktionen unter Kenntnis "weniger" Funktionswerte. Dabei liegt der Fokus auf dem Zusammenhang, der zwischen beiden besteht. Zum Abschluss wird ein Polynomialzeit-Algorithmus zum Lernen von k-KNFs vorgestellt. |
| Times: |
| part 1: Wednesday 14th May 2008, 5.45 pm - 7.00 pm, room 1/208A part 2: Wednesday 21st May 2008, 5.45 pm - 7.00 pm, room 1/208A |
| Literatur: |
| O. Goldreich, S. Goldwasser, D. Ron. "Property Testing and Its Connection to Learning and Approximation". Journal of the ACM, 45(4):653-750, July 1998. L.G. Valiant. "A theory of the learnable". Communications of the ACM, 27(11):1134-1142, November 1984. |
