Logo

Mathematical Sciences Research Institute

Home » DDC - Junior Seminar: Two Effective Concept Classes of PACi Incomparable Degrees

Seminar

DDC - Junior Seminar: Two Effective Concept Classes of PACi Incomparable Degrees October 27, 2020 (09:00 AM PDT - 10:00 AM PDT)
Parent Program:
Location: MSRI: Online/Virtual
Speaker(s) Gihanee Senadheera (Southern Illinois University)
Description

To participate in this seminar, please register here: https://www.msri.org/seminars/25206

The seminar will feature research talks by the six postdoctoral scholars appointed to the Fall 2020 DDC program, along with talks by students and other pre-tenure researchers associated with this program.  Since seminar attendees will have disparate backgrounds, we plan that these talks will not be too advanced, nor will they assume substantial background knowledge.  Our postdocs include number theorists, model theorists, and computable structure theorists, and talks can be expected to span all of these areas.

Video

Two Effective Concept Classes Of PACi Incomparable Degrees

Abstract/Media

To participate in this seminar, please register here: https://www.msri.org/seminars/25206

Abstract:

The Probably Approximately Correct (PAC) learning is a ma chine learning model introduced by Leslie Valiant in 1984.The PACi reducibility refers to the PAC reducibility independent of size and computation time. This reducibility in PAC learn ing resembles the reducibility in Turing computability. In 1957 Friedberg and Muchnik independently solved the Post problem by constructing computably enumerable sets A and B of in comparable degrees using the priority construction method. We adapt this idea to PACi reducibility and construct two the ef fective concept class C0 and C1 such that C0 is not reducible to C1 and vice versa. In future, we could incorporate the size and time complexity to this reducibility and show that there exist PAC incomparable degrees.

Asset no preview Slides 336 KB application/pdf

Two Effective Concept Classes Of PACi Incomparable Degrees

H.264 Video 25156_28654_8597_Two_Effective_Concept_Classes_of_PACi_Incomparable_Degrees.mp4