Balasubramanian Sivan

Balasubramanian Sivan is a Research Scientist at Google Research New York.

He joined Google in August 2015. He got his undergraduate degree in Computer Science from Indian Institute of Technology Madras (2008) and PhD in Computer Science (2013) from the University of Wisconsin-Madison advised by Prof. Shuchi Chawla, and joined Google after spending two years at Microsoft Research Redmond as a postdoctoral researcher. His PhD thesis on Prior Robust Optimization received the ACM SIGecom doctoral dissertation award.

At Google, he has been working on optimization projects in Google's DoubleClick For Publishers (DFP) and Ad Exchange.

His research interests are in Algorithmic Game Theory, Online + Approximation algorithms and Online Learning. Some of his recent publications include:

1) Towards Optimal Algorithms for Prediction with Expert Advice (SODA 2015: with Nick Gravin and Yuval Peres)
-- In this paper, we study the classical problem of prediction with expert advice and develop the precisely optimal algorithm, adversary and regret lower bounds for the case of a small number of experts. We develop upper and lower bounds simultaneously analogous to the primal-dual method. Our analysis of the optimal adversary takes us through delicate asymptotics of the random walk of a particle between multiple walls.

2) Simple Pricing for Consumers with Evolving Values (SODA 2016: with Shuchi Chawla, Nikhil R. Devanur and Anna Karlin)
-- In this paper we develop pricing schemes for a buyer who is interested in purchasing a good repeatedly over time. His value for enjoying the good evolves after he experiences the good each time as a martingale. Without making any assumptions about the buyer's risk profile, we show that simple per-round pricing schemes that initially offer the good for free for a few rounds, and then offers a constant price per round, obtain a revenue which is a constant fraction of the entire surplus. Importantly, the buyer need not know how his value evolves in the future: he just needs to know his current value.

See his personal webpage for more details on his publications.

Previous Publications