Tata Institute of Fundamental Research
Partial Function Extension with Applications to Learning and Property Testing
PhD Synopsis Seminar
Speaker:
Gunjan Kumar
Date:
Tuesday, 20 Oct 2020, 14:00 to 15:00
Venue:
(Scan to add to calendar)
Abstract:
Partial function extension is a basic problem that underpins multiple research topics in optimization, including learning, property testing, and game theory. Here, we are given a partial function consisting of $n$ points from a domain and a function value at each point. Our objective is to determine if this partial function can be extended to a function defined on the domain, that additionally satisfies a given property, such as linearity. We formally study partial function extension for various complement-free functions.
Our contributions are twofold. Firstly, for the properties studied, we give a combinatorial characterization and bounds on the complexity of partial function extension. Secondly, we develop new connections between partial function extension and learning and property testing, and use these to give new results for these problems.
Zoom link: https://zoom.us/j/91586068203?pwd=Sjk1T1lhR1lYVUhidHN2VVRXeFJoZz09
| Speaker: | Gunjan Kumar |
| Date: | Tuesday, 20 Oct 2020, 14:00 to 15:00 |
| Venue: |
(Scan to add to calendar)
Abstract:
Partial function extension is a basic problem that underpins multiple research topics in optimization, including learning, property testing, and game theory. Here, we are given a partial function consisting of $n$ points from a domain and a function value at each point. Our objective is to determine if this partial function can be extended to a function defined on the domain, that additionally satisfies a given property, such as linearity. We formally study partial function extension for various complement-free functions.
Our contributions are twofold. Firstly, for the properties studied, we give a combinatorial characterization and bounds on the complexity of partial function extension. Secondly, we develop new connections between partial function extension and learning and property testing, and use these to give new results for these problems.
Zoom link: https://zoom.us/j/91586068203?pwd=Sjk1T1lhR1lYVUhidHN2VVRXeFJoZz09
Our contributions are twofold. Firstly, for the properties studied, we give a combinatorial characterization and bounds on the complexity of partial function extension. Secondly, we develop new connections between partial function extension and learning and property testing, and use these to give new results for these problems.
Zoom link: https://zoom.us/j/91586068203?pwd=Sjk1T1lhR1lYVUhidHN2VVRXeFJoZz09