The Northwestern CS Theory group had three papers at the 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2020), which was recently held virtually.
Northwestern Economics PhD student Modibo Camara, CS PhD student Aleck Johnsen, and Prof. Jason Hartline co-authored a paper “Mechanisms for a No-Regret Agent: Beyond the Common Prior“. The paper analyzes a broad class of Principal-Agent games in economics that normally depend on common knowledge of a precise distribution over an unknown, payoff-relevant input, using instead online learning in repeated game play. A key idea of the paper which describes (possibly externally-informed) Agents behaviorally with only a no-regret property is to extend previous definitions for “regret” to consider counterfactual sequences of the repeated play. Link to the talk.
Northwestern CS PhD students Yingkai Li and Aleck Johnsen, and Prof. Jason Hartline co-authored a paper “Benchmark Design and Prior Independent Optimization“. The paper introduces a formal approach to the study of benchmark design, as a parameter of worst case algorithm design to be optimized. Incorporating first economic properties to justify and measure benchmarks, the main result of the paper shows that benchmark design is equivalent to algorithm design when inputs are drawn independently from a common-but-unknown distribution. Another main result solves a longstanding open question in 2-agent revenue auction design, which further serves as application for the benchmark design result. Link to the talk.
Prof. Aravindan Vijayaraghavan co-authored a paper “Scheduling Precedence-Constrained Jobs on Related Machines with Communication Delay” with Biswaroop Maiti (Northeastern), Rajmohan Rajaraman (Northeastern), David Stalfa (Northeastern), and Zoya Svitkina (Google). The paper studies the problem of scheduling n precedence-constrained jobs on m uniformly-related machines in the challenging setting where we have to account for communication delays. Communication delay is the amount of time that must pass between the completion of a job on one machine and the start of any successor of that job on a different machine. The paper shows both algorithmic results and lower bounds. This includes the first polylogarithmic factor approximation algorithm for this problem, superconstant integrality gaps, and bounding the advantage of duplication in these settings. Link to the talk.
Hedyeh Beyhaghi.
Shravas Rao.
Sumedha Uniyal.
Pattara Sukprasert. Pattara is a third-year Ph.D. student advised by Prof. Samir Khuller. He transferred from the University of Maryland College Park, where he spent his first two Ph.D. years and received a Master’s degree. Before that, he lived mostly in Thailand and got another Master’s degree from Kasetsart University advised by Prof. Jittat Fakcharoenphol. He is interested in approximation algorithms and graph theory, and has worked on network design problems, network flow problems, and some structural graph theory problems. Recently, he has also developed some interests in fast (up to sub-cubic) approximation algorithms.
Saba Ahmadi. Saba is a fifth year PhD student at the University of Maryland College Park visiting Northwestern, and she is advised by Prof. Samir Khuller. She is mainly interested in designing approximation algorithms. She is also interested in the topic of fairness and its relevance to combinatorial optimization. She finds problems at the intersection of AI and combinatorial optimization very interesting, one example is how to have diversity in the matching markets.
Sheng Yang.
Recent Comments