Tata Institute of Fundamental Research
Partial Function Extension with Applications to Property Testing and Learning
PhD Thesis Seminar
Speaker:
Gunjan Kumar
Organiser:
Umang Bhaskar
Date:
Thursday, 2 Dec 2021, 18:00 to 19:00
Venue:
Via Zoom
(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 some 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 monotonicity. 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.
Join Zoom Meeting
https://zoom.us/j/96720853429?pwd=ZUFFdzYvSmQzMWRNOG9PZVNzMHJpdz09
Meeting ID: 967 2085 3429
Passcode: 869836
| Speaker: | Gunjan Kumar |
| Organiser: | Umang Bhaskar |
| Date: | Thursday, 2 Dec 2021, 18:00 to 19:00 |
| Venue: | Via Zoom |
(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 some 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 monotonicity. 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.
Join Zoom Meeting
https://zoom.us/j/96720853429?pwd=ZUFFdzYvSmQzMWRNOG9PZVNzMHJpdz09
Meeting ID: 967 2085 3429
Passcode: 869836
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.
Join Zoom Meeting
https://zoom.us/j/96720853429?pwd=ZUFFdzYvSmQzMWRNOG9PZVNzMHJpdz09
Meeting ID: 967 2085 3429
Passcode: 869836