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.
Abstract: Artificial Intelligence (AI)/ Machine Learning (ML)/ Neural Network (NN) algorithms are being widely used currently for various applications that include self driving cars, virtual assistants on smartphones and other dev
Abstract: We study a new type of separation between quantum and classical communication complexity, a separation which is obtained using quantum protocols where all parties are efficient, in the sense that they can be implemented
