Cancelled: Approximate Modularity Revisited
This event has been cancelled.
Speaker:
Inbal Talgam-Cohen
, Hebrew University
Date: Tuesday, April 18, 2017
Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone
Public: Yes
Location: 32-G449 (Kiva)
Event Type:
Room Description:
Host: Pritish Kamath and Akshay Degwekar, CSAIL MIT
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu
Speaker URL: None
Speaker Photo:
None
Reminders to:
seminars@csail.mit.edu, theory-seminars@csail.mit.edu
Reminder Subject:
TALK: Inbal Talgam-Cohen: Approximate Modularity Revisited
Abstract: Set functions with convenient properties (such as submodularity) often arise in algorithmic game theory, and allow for improved properties of optimization algorithms and mechanisms. It is natural to ask (e.g., in the context of data driven applications) how robust such properties are, and whether small deviations from them can be tolerated. We consider two such questions in the important special case of linear set functions. One question that we address is whether any set function that approximately satisfies the modularity equation (linear functions satisfy the modularity equation exactly) is close to a linear function. The answer to this is positive (in a precise formal sense) as shown by Kalton and Roberts [1983] (and further improved by Bondarenko, Prymak, and Radchenko [2013]). We revisit their proof idea that is based on expander graphs, and provide significantly stronger upper bounds by combining it with new techniques. Furthermore, we provide improved lower bounds for this problem. Another question that we address is that of how to learn a linear function $h$ that is close to an approximately linear function $f$, while querying the value of $f$ on only a small number of sets. Joint work with Uriel Feige and Michal Feldman.
Research Areas:
None selected
Impact Areas:
None selected
Created by Rebecca Yadegar at Monday, April 17, 2017 at 4:26 PM.