Computer Science Design

Balasubramanian Sivan

Contact Office Address

Information 4395, Computer Sciences Department Home-page: www.cs.wisc.edu/ balu2901

~

University of

Wisconsin-Madison Official

E-mail: ********@**.****.edu1210 W.Dayton Street, Madison Personal E-mail: ********@*****.***

WI -53706, USA Telephone: 608-***-****

Education University of Wisconsin-Madison (August 2008 - present)

PhD in Computer Science (expected by May 2013)

Advisor: Prof. Shuchi Chawla

GPA: 3.8/4, Major: 3.94/4

Indian Institute of Technology Madras (August 2004 - July 2008)

B.Tech in Computer Science and Engineering

GPA: 9.39/10, Major: 9.60/10

Research Algorithmic Game Theory, Approximation Algorithms.

Interests

Publications

1. Asymptotically Optimal Algorithm for Stochastic Adwords

with N. Devanur and Y. Azar,

ACM-EC 2012.

2. Single-Call Mechanisms

with C. Wilkens,

ACM-EC 2012.

3. Optimal Crowdsourcing Contests

with S. Chawla and J. Hartline,

ACM-SIAM SODA 2012,

Invited to the special issue of Games and Economic Behavior (GEB) from STOC/

FOCS/ SODA 2012

4. Near Optimal Online Algorithms and Fast Approximation Algorithms for Re-

source Allocation Problems

with N. Devanur, K. Jain and C. Wilkens,

ACM EC 2011.

5. Multi-parameter Mechanism Design and Sequential Posted Pricing

with S. Chawla, J. Hartline and D. Malec,

ACM STOC 2010.

6. The Power of Randomness in Bayesian Optimal Mechanism Design

with S. Chawla and D. Malec,

ACM EC 2010,

Accepted to the special invited issue of Games and Economic Behavior (GEB)

from EC 2010 and EC 2011.

7. On Conditional Covering Problem

with S.Harini and C. Pandurangan,

Mathematics in Computer Science, Special Issue on Advances in Combinatorial

Algorithms, Birkh"auser Basel, 2009.

8. Core and Conditional Core Path of Specified Length in Special Classes of Graphs

with S. Harini and C. Pandurangan,

WALCOM 2009 (Workshop on Algorithms and Computation).

9. On Conditional Covering Problem

with S.Harini and C. Pandurangan,

IWOCA 2008 (International Workshop on Combinatorial Algorithms).

Working Papers

1. Bayesian Mechanisms for Scheduling

with S. Chawla, J. Hartline and D. Malec.

2. Ordinal Approximate Nash Equilibrium

with K. Jain and C. Wilkens.

Patents

1. Online Resource Allocation Algorithms

Patent pending (Microsoft Corporation, September 2011)

2. Offline Algorithms for Resource Allocation Problems

Patent pending (Microsoft Corporation, January 2012)

Research Microsoft Research, Redmond

Experience Visitor August 2011

Worked with Nikhil Devanur and Yossi Azar on the stochastic adwords problem and

improved the best known results for adwords in terms of the dependence on the bid to

budget ratio.

Northwestern UniversityVisitorSeptember 2011

Worked with Jason Hartline and obtained improved approximation algorithms for vari-

ants of secretary problems.

Microsoft Research, Redmond

Summer InternshipMay - July 2010

Worked with Nikhil Devanur, Kamal Jain and Chris Wilkens on a class of resource

allocation problems. Work involved designing and analyzing algorithms for this class

of problems in both the online and offline setting, and applying its proof technique for

other problems, including the adwords problem. On a different problem, along with

Kamal Jain and Chris Wilkens, I came up with a new notion of equilibrium called the

ordinal Nash equilibrium, which is relevant in many settings, and often exists even in

settings where Nash equilibrium fails to exist. I also worked with Chris Wilkens on

mechanism design with just a single call to the allocation function.

Computer Science Department, University of Wisconsin Madison

Graduate Work August 2008 - present

RA Work under the guidance of Prof. Shuchi Chawla. I have been working on various

mechanism design problems, including posted price mechanisms, randomized mecha-

nisms in Bayesian settings, scheduling algorithms in Bayesian setting, and more recently

crowd sourcing problems.

Department of Computer Science and Engineering, IIT Madras

B.Tech Project August 2007 - May 2008

Worked with Prof. C. Pandurangan on computing the core path in three special

classes of graphs. We designed algorithms for determining the core path in bipartite

permutation graphs, threshold graphs and proper interval graphs. The thesis is avail-

able at pages.cs.wisc.edu/ balu2901/papers/2008/btech_thesis.pdf. In another

~

project that I worked on, we gave an algorithm for the conditional covering problem

on paths and interval graphs. (This work corrects an earlier incorrect algorithm in

literature.)

College of Computer and Info. Science, Northeastern University, Boston

Summer Internship May-July 2007

Worked with Prof. Ravi Sundaram on a graph layout optimization problem (Cyclic

Antibandwidth), established the NP-Completeness of the problem and the hardness of

approximation, gave approximate solutions for special graphs.

Relevant Advanced Algorithms, Mathematical Techniques for Analysis of Algorithms,

Microeco-

Coursework nomic Theory Sequence (I and II), Algorithmic Game Theory, Randomized

Algorithms,

Complexity Theory, Cryptography, Quantum Information Processing.

Workshop and

1. Stanford University, Theory lunch, Optimal crowdsourcing contests, January

Seminar

2012.

Presentations

2. Microsoft Research, Silicon Valley, Bayesian multi-parameter scheduling, Jan-

uary 2012.

3. Northwestern University, Theory seminar, Near optimal online algorithms and

fast approximation algorithms for resource allocation problems, September 2011.

4. University of Washington, Theory seminar, Near optimal online algorithms and

fast approximation algorithms for resource allocation problems, September 2011.

5. Microsoft Research, Redmond, Near optimal online algorithms and fast approx-

imation algorithms for resource allocation problems, August 2011.

6. Greece Economics and Algorithmic Theory (GREAT) workshop, Optimal Crowd-

sourcing Contests, July 2011.

7. Midwest Theory Day, Toyota Technological Institute, Chicago, Single-call mech-

anisms, December 2010.

8. Northwestern University, Theory of Computing seminar, The power of random-

ness in Bayesian optimal mechanism design, May 2010.

9. Bertinoro workshop on frontiers in mechanism design, Italy, The power of ran-

domness in Bayesian optimal mechanism design, March 2010.

10. University of Wisconsin-Madison, Theory of Computing seminar, Multi-parameter

mechanism design and sequential posted pricing, Feb 2010.

Computer Sciences alumni scholarship 2008, University of Wisconsin Madison.

Awards and

Honors

Summer research fellowship, University of Wisconsin Madison - Summer 2009

Secured Rank one in my School in my Higher Secondary Board Examination

Related Referee of research contributions in various conferences and journals:

STOC(2011),

activities FOCS(2011), SODA (2011, 2012), SICOMP(2012), ICALP(2012), WINE(2009, 2010,

2011), EC(2011), ESA(2011), AAAI(2010), Information and Computation(2011)

A

Languages and Tools - C, C++, Matlab, Maple, LT X

Computer Skills

E

Contact this candidate