Abstract: The COVID-19 pandemic has strained testing capabilities worldwide. There is an urgent need to find economical and scalable ways to test more people.
We consider the problem of sequentially learning good alternatives from among a pool, but with only relative utility feedback from adaptively chosen subsets.
Classical multi-armed bandit algorithms are tuned to work well for a pre-specified class of reward distributions, defined via their support, or moment/tail bounds.
Abstract: Schaffer and Yannakakis have shown that the max-cut problem with the FLIP neighborhood is polynomial-time local search (PLS) complete, and hence among the most difficult problems in the PLS class.
Abstract: The Skolem - Mahler - Lech Theorem states that given any linear recurrence sequence over any field of characteristic 0, the set of positions where 0 occurs is union of a finite set and finitely many arithmetic progressio
Abstract: PCP Theorem characterizes the class NP and gives hardness of approximation for many optimization problems. Despite this, several tight hardness of approximation results remain elusive via the PCP theorem.
Abstract:*The problem of approximate sampling using Markov Chain Monte Carlo has received considerable attention in the Theoretical Computer Science and Physics communities.
Neha Sangwan, graduate student in the School of Technology and Computer Science, wins the runner-up award for her poster at the Croucher Summer Course in Information Theory (