Algorithms
Planar Graph Perfect Matching is in NC
Is matching in NC, i.e., is there a deterministic fast parallel algorithm for it? This has been an outstanding open question in TCS for over three decades, ever since the discovery of Random NC matching…
Distributive Lattices, Stable Matchings, and Robust Solutions
Our results are: ** Introduce the problem of finding stable matchings that are robust to errors in the input. ** An efficient algorithm for the following class of errors: Permute arbitrarily the preference list of…
Extreme Classification
New perspectives on contextual bandit
What is the common denominator between the following situations: a doctor choosing among different drugs for a sequence of patients; a website selecting ads for its visitors based on the information it has about them;…
Thompson Sampling for Combinatorial Semi-Bandits
Efficient PAC Learning from the Crowd
Deep Learning at Mote Scale
The Internet of Things (IoT) is poised to revolutionize our world. Billions of microcontrollers and sensors have already been deployed for predictive maintenance, connected cars, precision agriculture, personalized fitness and wearables, smart housing, cities, healthcare,…
