Aditya Bhaskara
Assistant Professor


Book Chapter  Journal  Conference  Workshop  Tech Report]

Journal

2016

  • Greedy Column Subset Selection: New Bounds and Distributed Algorithms. (Project Website)
    By Jason Altschuler,   Aditya Bhaskara,   Gang Fu,   Vahab S. Mirrokni,   Afshin Rostamizadeh,   Morteza Zadimoghaddam,   
    Vol.abs/1605.08795, CoRR (CORR 2016),  2016.
    Abstract
  • 2015

  • Sparse Solutions to Nonnegative Linear Systems and Applications. (Project Website)
    By Aditya Bhaskara,   Ananda Theertha Suresh,   Morteza Zadimoghaddam,   
    Vol.abs/1501.01689, CoRR (CORR 2015),  2015.
    Abstract
  • Expanders via Local Edge Flips. (Project Website)
    By Zeyuan Allen Zhu,   Aditya Bhaskara,   Silvio Lattanzi,   Vahab S. Mirrokni,   Lorenzo Orecchia,   
    Vol.abs/1510.07768, CoRR (CORR 2015),  2015.
    Abstract
  • On Binary Embedding using Circulant Matrices. (Project Website)
    By Felix X. Yu,   Aditya Bhaskara,   Sanjiv Kumar,   Yunchao Gong,   Shih-Fu Chang,   
    Vol.abs/1511.06480, CoRR (CORR 2015),  2015.
    Abstract
  • Centrality of trees for capacitated k-center. (Project Website)
    By Hyung-Chan An,   Aditya Bhaskara,   Chandra Chekuri,   Shalmoli Gupta,   Vivek Madan,   Ola Svensson,   
    Vol.154, Pages 29-53, Math. Program. (MP 2015),  2015.
    Abstract
  • 2014

  • More Algorithms for Provable Dictionary Learning. (Project Website)
    By Sanjeev Arora,   Aditya Bhaskara,   Rong Ge ,   Tengyu Ma,   
    Vol.abs/1401.0579, CoRR (CORR 2014),  2014.
    Abstract
  • 2013

  • Smoothed Analysis of Tensor Decompositions. (Project Website)
    By Aditya Bhaskara,   Moses Charikar,   Ankur Moitra,   Aravindan Vijayaraghavan,   
    Vol.abs/1311.3651, CoRR (CORR 2013),  2013.
    Abstract
  • Provable Bounds for Learning Some Deep Representations. (Project Website)
    By Sanjeev Arora,   Aditya Bhaskara,   Rong Ge ,   Tengyu Ma,   
    Vol.abs/1310.6343, CoRR (CORR 2013),  2013.
    Abstract
  • Uniqueness of Tensor Decompositions with Applications to Polynomial Identifiability (Project Website)
    By Aditya Bhaskara,   Moses Charikar,   Aravindan Vijayaraghavan,   
    Vol.abs/1304.8087, CoRR (CORR 2013),  2013.
    Abstract
  • Centrality of Trees for Capacitated k-Center (Project Website)
    By Hyung-Chan An,   Aditya Bhaskara,   Ola Svensson,   
    Vol.abs/1304.2983, CoRR (CORR 2013),  2013.
    Abstract
  • Optimal Hitting Sets for Combinatorial Shapes. (Project Website)
    By Aditya Bhaskara,   Devendra Desai,   Srikanth Srinivasan,   
    Vol.9, Pages 441-470, Theory of Computing (TOC 2013),  2013.
    Abstract
  • 2012

  • Optimal Hitting Sets for Combinatorial Shapes. (Project Website)
    By Aditya Bhaskara,   Devendra Desai,   Srikanth Srinivasan,   
    Vol.19, Pages 158, Electronic Colloquium on Computational Complexity (ECCC) (ECCC 2012),  2012.
    Abstract
  • Optimal Hitting Sets for Combinatorial Shapes (Project Website)
    By Aditya Bhaskara,   Devendra Desai,   Srikanth Srinivasan,   
    Vol.abs/1211.3439, CoRR (CORR 2012),  2012.
    Abstract
  • 2011

  • Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph (Project Website)
    By Aditya Bhaskara,   Moses Charikar,   Venkatesan Guruswami,   Aravindan Vijayaraghavan,   Yuan Zhou,   
    Vol.abs/1110.1360, CoRR (CORR 2011),  2011.
    Abstract
  • On Quadratic Programming with a Ratio Objective (Project Website)
    By Aditya Bhaskara,   Moses Charikar,   Rajsekar Manokaran,   Aravindan Vijayaraghavan,   
    Vol.abs/1101.1710, CoRR (CORR 2011),  2011.
    Abstract
  • 2010

  • Computing the Matrix p-norm (Project Website)
    By Aditya Bhaskara,   Aravindan Vijayaraghavan,   
    Vol.abs/1001.2613, CoRR (CORR 2010),  2010.
    Abstract
  • Detecting High Log-Densities -- an O(n^1/4) Approximation for Densest k-Subgraph (Project Website)
    By Aditya Bhaskara,   Moses Charikar,   Eden Chlamtac,   Uriel Feige,   Aravindan Vijayaraghavan,   
    Vol.abs/1001.2891, CoRR (CORR 2010),  2010.
    Abstract
  • Conference

    2016

  • Expanders via Local Edge Flips. (Project Website)
    By Zeyuan Allen Zhu,   Aditya Bhaskara,   Silvio Lattanzi,   Vahab S. Mirrokni,   Lorenzo Orecchia,   
    In Proceedings of SODA (SODA 2016),  pages 259-269,  2016.
    Abstract
  • Linear Relaxations for Finding Diverse Elements in Metric Spaces. (Project Website)
    By Aditya Bhaskara,   Mehrdad Ghadiri,   Vahab S. Mirrokni,   Ola Svensson,   
    In Proceedings of NIPS (NIPS 2016),  pages 4098-4106,  2016.
    Abstract
  • Greedy Column Subset Selection: New Bounds and Distributed Algorithms. (Project Website)
    By Jason Altschuler,   Aditya Bhaskara,   Gang Fu,   Vahab S. Mirrokni,   Afshin Rostamizadeh,   Morteza Zadimoghaddam,   
    In Proceedings of ICML (ICML 2016),  pages 2539-2548,  2016.
    Abstract
  • 2015

  • Optimizing Display Advertising in Online Social Networks. (Project Website)
    By Zeinab Abbassi,   Aditya Bhaskara,   Vishal Misra,   
    In Proceedings of WWW (WWW 2015),  pages 1-11,  2015.
    Abstract
  • Sparse Solutions to Nonnegative Linear Systems and Applications. (Project Website)
    By Aditya Bhaskara,   Ananda Theertha Suresh,   Morteza Zadimoghaddam,   
    In Proceedings of AISTATS (AISTATS 2015),  pages ??-??,  2015.
    Abstract
  • 2014

  • Smoothed analysis of tensor decompositions. (Project Website)
    By Aditya Bhaskara,   Moses Charikar,   Ankur Moitra,   Aravindan Vijayaraghavan,   
    In Proceedings of STOC (STOC 2014),  pages 594-603,  2014.
    Abstract
  • Distributed Balanced Clustering via Mapping Coresets. (Project Website)
    By MohammadHossein Bateni,   Aditya Bhaskara,   Silvio Lattanzi,   Vahab S. Mirrokni,   
    In Proceedings of NIPS (NIPS 2014),  pages 2591-2599,  2014.
    Abstract
  • Centrality of Trees for Capacitated k-Center. (Project Website)
    By Hyung-Chan An,   Aditya Bhaskara,   Chandra Chekuri,   Shalmoli Gupta,   Vivek Madan,   Ola Svensson,   
    In Proceedings of IPCO (IPCO 2014),  pages 52-63,  2014.
    Abstract
  • Provable Bounds for Learning Some Deep Representations. (Project Website)
    By Sanjeev Arora,   Aditya Bhaskara,   Rong Ge ,   Tengyu Ma,   
    In Proceedings of ICML (ICML 2014),  pages 584-592,  2014.
    Abstract
  • Open Problem: Tensor Decompositions: Algorithms up to the Uniqueness Threshold? (Project Website)
    By Aditya Bhaskara,   Moses Charikar,   Ankur Moitra,   Aravindan Vijayaraghavan,   
    In Proceedings of COLT (COLT 2014),  pages 1280-1282,  2014.
    Abstract
  • Uniqueness of Tensor Decompositions with Applications to Polynomial Identifiability. (Project Website)
    By Aditya Bhaskara,   Moses Charikar,   Aravindan Vijayaraghavan,   
    In Proceedings of COLT (COLT 2014),  pages 742-778,  2014.
    Abstract
  • 2013

  • Minimum Makespan Scheduling with Low Rank Processing Times. (Project Website)
    By Aditya Bhaskara,   Ravishankar Krishnaswamy,   Kunal Talwar,   Udi Wieder,   
    In Proceedings of SODA (SODA 2013),  pages 937-947,  2013.
    Abstract
  • 2012

  • Unconditional differentially private mechanisms for linear queries. (Project Website)
    By Aditya Bhaskara,   Daniel Dadush,   Ravishankar Krishnaswamy,   Kunal Talwar,   
    In Proceedings of STOC (STOC 2012),  pages 1269-1284,  2012.
    Abstract
  • On Quadratic Programming with a Ratio Objective. (Project Website)
    By Aditya Bhaskara,   Moses Charikar,   Rajsekar Manokaran,   Aravindan Vijayaraghavan,   
    In Proceedings of ICALP (1) (ICALP 2012),  pages 109-120,  2012.
    Abstract
  • Polynomial integrality gaps for strong SDP relaxations of Densest -subgraph. (Project Website)
    By Aditya Bhaskara,   Moses Charikar,   Aravindan Vijayaraghavan,   Venkatesan Guruswami,   Yuan Zhou,   
    In Proceedings of SODA (SODA 2012),  pages 388-405,  2012.
    Abstract
  • Optimal Hitting Sets for Combinatorial Shapes. (Project Website)
    By Aditya Bhaskara,   Devendra Desai,   Srikanth Srinivasan,   
    In Proceedings of APPROX-RANDOM (APPROX 2012),  pages 423-434,  2012.
    Abstract
  • 2011

  • Approximating Matrix p-norms. (Project Website)
    By Aditya Bhaskara,   Aravindan Vijayaraghavan,   
    In Proceedings of SODA (SODA 2011),  pages 497-511,  2011.
    Abstract
  • 2010

  • Detecting high log-densities: an () approximation for densest -subgraph. (Project Website)
    By Aditya Bhaskara,   Moses Charikar,   Eden Chlamtac,   Uriel Feige,   Aravindan Vijayaraghavan,   
    In Proceedings of STOC (STOC 2010),  pages 201-210,  2010.
    Abstract