In this talk, we will consider algorithmic problems which follow the following template: given a real-valued multivariate polynomial f(x) of degree d, is it approximately equal to a sum of a few "simple" polynomials, i
Many graph problems that are NP-hard for general graphs can be solved in polynomial time for planar graphs. We explore the domain of "almost" planar graphs. These are graphs that can be made planar by removing one or two vertices from them.
This paper concerns designing distributed algorithms that are singularly optimal, i.e., algorithms that are simultaneously time and message optimal, for the fundamental leader election problem in networks.
Motivated by the increasing adoption of models which facilitate greater automation in risk management and decision-making, this talk presents a novel Importance Sampling (IS) scheme for estimating distribution tails for a rich class of objectives
Mathematical proofs when written in conventional ways often contain imprecise definitions, unstated background assumptions, and inferential gaps in reasoning.
In Reinforcement Learning, one often needs to evaluate a given policy using rewards observed by following another policy. This is called off-policy evaluation in Learning Theory parlance.
We construct a succinct non-interactive publicly-verifiable delegation scheme for any logspace uniform circuit under the sub-exponential Learning With Errors (LWE) assumption.