Theory of Computation Lab
Ecole Polytechnique Federale de Lausanne (EPFL)

Contact:
EPFL IC IIF THL 1
INJ 130, Station 14
CH-1015 Lausanne
Email. bhaskara@cs.princeton.edu

Here is a copy of my CV [pdf]

I am currently a postdoc in the theory group at EPFL. I recently completed my Ph.D. at the Department of Computer Science, Princeton University, advised by Moses Charikar. Before Princeton, I spent four wonderful years as an undergraduate at the Indian Institute of Technology, Bombay, where I received my B.Tech. degree in Computer Science.

I am broadly interested in theoretical computer science. More specifically, I am interested in approximation algorithms, spectral methods, and applications of probability and convex geometry to computational problems.

Here is a copy of my dissertation, titled "Finding Dense Structures in Graphs and Matrices".

Approximation Algorithms

Detecting High Log-densities -- An O(n^{1/4}) Approximation for Densest k-Subgraph [pdf][arXiv]
(STOC 2010) (with Moses Charikar, Eden Chlamtac, Uriel Feige and Aravindan Vijayaraghavan)

Polynomial Integrality gaps for Strong relaxations of Densest k-subgraph [pdf][arXiv]
(SODA 2012) (with Moses Charikar, Venkatesan Guruswami, Aravindan Vijayaraghavan, and Yuan Zhou)

Approximating Matrix p-norms [pdf][arXiv]
(SODA 2011) (with Aravindan Vijayaraghavan)

On Quadratic Programming with a Ratio Objective [pdf][arXiv]
(ICALP 2012) (with Moses Charikar, Rajsekar Manokaran and Aravindan Vijayaraghavan)

Minimum Makespan Scheduling with Low Rank Processing Times [pdf]
(SODA 2013) (with Ravishankar Krishnaswamy, Kunal Talwar and Udi Wieder)

Unconditional Differentially Private Mechanisms for Linear Queries [pdf]
(STOC 2012) (with Daniel Dadush, Ravishankar Krishnaswamy and Kunal Talwar)

Optimal Hitting Sets for Combinatorial Shapes [pdf] [arXiv]
(RANDOM 2012) (with Devendra Desai and Srikanth Srinivasan)

Eigenvectors of Random Graphs: Delocalization and Nodal Domains [draft]
(In submission) (with Sanjeev Arora)

Moment-based Concentration Bounds for Euclidean Optimization Problems
(Manuscript, 2011) (with Ravi Kannan)

A note on the Lovasz theta number of random graphs [pdf]
(Informal note, 2011) (with Sanjeev Arora)

Packing triangles into a Unit strip
(Undergraduate thesis, 2007) (with Abhiram Ranade)

Intractability
Theory Calendar

Boaz's Course (Spring 08)
Thinking like a Theorist (Fall 07)
Theorist's Toolkit (long ago)