Interests

Broadly, my research interests lie in theoretical computer science. I am particularly interested in machine learning theory, algorithmic statistics, and randomised algorithms. I am also interested in research that uses computer science as a lens on the natural sciences, particularly pertaining to biological evolution and neuroscience.

Publications

• Simplicity Bias in Transformers and their Ability to Learn Sparse Boolean Functions [arxiv] Satwik Bhattamishra, Arkil Patel, Varun Kanade and Phil Blunsom
  In the 61st Annual Meeting of the Association for Computational Linguistics, ACL 2023
  
  
• When are Local Queries Useful for Robust Learning? [arxiv] [conf]
  Pascale Gourdeau, Varun Kanade, Marta Kwiatkowska and James Worrell
  In the 35th Advances in Neural Information Processing Systems, NeurIPS 2022
  
  
• Sample complexity bounds for robustly learning decision lists against evasion attacks [arxiv] [conf]
  Pascale Gourdeau, Varun Kanade, Marta Kwiatkowska and James Worrell
  In the Proceedings of the 31st International Joint Conference on Artificial Intelligence Organization, IJCAI 2022
  
  
• Towards optimally abstaining from prediction with OOD test examples [arxiv]
  Adam Tauman Kalai and Varun Kanade
  In the 34th Advances in Neural Information Processing Systems, NeurIPS 2021
  
  
• Online k-Means Clustering [arxiv]
  Vincent Cohen-Addad, Benjamin Geudj, Varun Kanade and Guy Rom
  In the 24th International Conference on Artificial Intelligence and Statistics AISTATS 2021
  
  
• How benign is benign overfitting? [arxiv] [open review]
  Amartya Sanyal, Puneet Dokania, Varun Kanade and Phil H. S. Torr
  In the ninth International Conference on Learning Representations, ICLR 2021
  
  
• Efficient Learning with Arbitrary Covariate Shift
  Adam Tauman Kalai and Varun Kanade
  In the 32nd International Conference on Algorithmic Learning Theory, ALT 2021
  
  
• The Statistical Complexity of Early Stopped Mirror Descent [arxiv]
  Tomas Vaškevičius, Varun Kanade and Patrick Rebeschini
  In the 33rd Advances in Neural Information Processing Systems, NeurIPS 2020
  
  
• Adaptive Reduced Rank Regression [arxiv]
  Qiong Wu, Felix Ming Fai Wong, Zhenming Liu, Yanhua Li, and Varun Kanade
  In the 33rd Advances in Neural Information Processing Systems, NeurIPS 2020
  
  
• Differentiable Causal Backdoor Discovery [aistats]
  Limor Gultchin, Matt Kusner, Varun Kanade and Ricardo Silva
  In the 23rd International Conference on Artificial Intelligence and Statistics, AISTATS 2020
  
  
• On the Hardness of Robust Classification [arxiv]
  Pascale Gourdeau, Varun Kanade, Marta Kwiatkowska and James Worrell
  In the 32nd Advances in Neural Information Processing Systems, NeurIPS 2019
  
  
• Implicit Regularization for Optimal Sparse Recovery [arxiv]
  Tomas Vaškevičius, Varun Kanade and Patrick Rebeschini
  In the 32nd Advances in Neural Information Processing Systems, NeurIPS 2019
  
  
• Decentralized Cooperative Stochastic Bandits [arxiv]
  David Martínez-Rubio, Varun Kanade and Patrick Rebeschini
  In the 32nd Advances in Neural Information Processing Systems, NeurIPS 2019
  
  
• Statistical Windows in Testing for the Initial Distribution of a Reversible Markov Chain [arxiv]
  Quentin Berthet and Varun Kanade
  In the 22nd International Conference on Artificial Intelligence and Statistics, AISTATS 2019
  
  
• On coalescence time in graphs--when is coalescing as fast as mixing? [arxiv]
  Varun Kanade, Frederik Mallmann-Trenn and Thomas Sauerwald
  In the 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019
  In the ACM Transcations on Algorithms 19 (2), 1-46 [journal version]
  
  
• Clustering Redemption--Beyond the Impossibility of Kleinberg's Axioms [pdf]
  Vincent Cohen-Addad, Varun Kanade and Frederik Mallmann-Trenn
  In the 31st Advances in Neural Information Processing Systems, NIPS 2018
  
  
• TAPAS: Tricks to Accelerate (encrypted) Prediction As a Service
  Amartya Sanyal, Matt Kusner, Adrià Gascón and Varun Kanade
  In the 35th International Conference on Machine Learning, ICML 2018
  
  
• Hierarchical Clustering: Objective Functions and Algorithms [arxiv]
  Vincent Cohen-Addad, Varun Kanade, Frederik Mallmann-Trenn and Claire Mathieu
  In the 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018
  
  
• Hierarchical Clustering Beyond the Worst-Case
  Vincent Cohen-Addad, Varun Kanade and Frederik Mallmann-Trenn
  In the 30th Advances in Neural Information Processing Systems, NIPS 2017
  
  
• From which world is your graph?
  Cheng Li, Felix Wong, Zhenming Liu and Varun Kanade.
  In the 30th Advances in Neural Information Processing Systems, NIPS 2017
  
  
• Reliably Learning the ReLU in Polynomial Time [arxiv]
  Surbhi Goel, Varun Kanade, Adam Klivans and Justin Thaler
  In the 30th Annual Conference on Learning Theory, COLT 2017
  
  
• How large is your graph?
  Varun Kanade, Frederik Mallmann-Trenn and Víctor Verdugo
  In the 31st International Symposium on Distributed Computing, DISC 2017
  Brief Announcement in the 36th ACM Symposium on Principles of Distributed Computing, PODC 2017
  
  
• Online Optimization of Smoothed Piecewise Constant Functions [arxiv]
  Vincent Cohen-Addad and Varun Kanade
  In the 20th International Conference on Artificial Intelligence and Statistics, AISTATS 2017
  
  
• Stable Matching with Evolving Preferences [arxiv]
  Varun Kanade, Nikos Leonardos and Frédéric Magniez
  In the 20th International Workshop on Randomization and Computation, RANDOM 2016
  
  
• Distance in the Forest Fire Model: How far are you from Eve? [pdf]
  Varun Kanade, Reut Levi, Zvi Lotker, Frederik Mallmann-Trenn and Claire Mathieu
  In the 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016
  
  
• Learning with a Drifting Target Concept [arxiv]
  Steve Hanneke, Varun Kanade and Liu Yang
  In the 26th Annual International Conference on Algorithmic Learning Theory, ALT 2015
  
  
• MCMC Learning [arxiv]
  Varun Kanade and Elchanan Mossel
  In the 28th Annual Conference on Learning Theory, COLT 2015
  
  
• Global and Local Information in Clustering Labeled Block Models [arxiv]
  Varun Kanade, Elchanan Mossel and Tselil Schramm
  In the 18th International Workshop on Randomization and Computation, RANDOM 2014
  
  
• Distribution-Independent Reliable Learning [arxiv]
  Varun Kanade and Justin Thaler
  In the 27th Annual Conference on Learning Theory, COLT 2014
  
  
• Tracking Adversarial Targets [link]
  Yasin Abbasi-Yadkori, Peter Bartlett, and Varun Kanade
  In the 31st International Conference on Machine Learning, ICML 2014
  
  
• Attribute-Efficient Evolvability of Linear Functions [pdf] [arxiv]
  Elaine Angelino and Varun Kanade
  In the 5th Annual Innovations in (Theoretical) Computer Science Conference, ITCS 2014
  
  
• Online Learning in Markov Decision Processes with Adversarially Chosen Transition Probability Distributions [pdf] (arxiv version in preparation)
  Yasin Abbasi-Yadkori, Peter Bartlett, Varun Kanade, Yevgeny Seldin, and Csaba Szepsvári
  In the 26th Advances in Neural Informatin Processing Systems, NIPS 2013
  
  
• Learning using Local Membership Queries under Smooth Distributions [pdf] [arxiv]
  Pranjal Awasthi, Vitaly Feldman and Varun Kanade
  In the 26th Annual Conference on Learning Theory, COLT 2013
  Winner of Best Student Paper Award
  
  
• Distributed Non-Stochastic Experts [pdf] [link] [arxiv](full version)
  Varun Kanade, Zhenming Liu and Bozidar Radunovic
  In the 25th Advances in Neural Information Processing Systems, NIPS 2012
  
  
• Computational Bounds on Statistical Query Learning [pdf] [link]
  Vitaly Feldman and Varun Kanade
  In the 25th Annual Conference on Learning Theory, COLT 2012
  
  
• Learning Hurdles for Sleeping Experts [pdf] [link]
  Varun Kanade and Thomas Steinke
  In the 3rd Innovations in (Theoretical) Computer Science Conference, ITCS 2012
  Invited to a special issue of ACM Transactions on Computation Theory [submitted version]
  Also presented at ICML 2012 Workshop on Exploration and Exploitation [short video]
  
  
• Reliable Agnostic Learning [pdf] [link]
  Adam Tauman Kalai, Varun Kanade and Yishay Mansour
  Journal of Computer and System Sciences Vol 8 Issue 5 2012
  An earlier version appeared in the 22nd Annual Conference on Learning Theory, COLT 2009
  
  
• Efficient learning of generalized linear and single index models with high dimensional isotonic regression [pdf] [link]
  Sham M. Kakade, Adam Tauman Kalai, Varun Kanade and Ohad Shamir
  In the 24th Advances in Neural Information Processing Systems, NIPS 2011
  
  
• Evolution with Recombination. [pdf] [link] [short video]
  Varun Kanade
  In the 52nd Annual Symposium on the Foundations of Computer Science, FOCS 2011
  
  
• Evolution with Drifting Targets [pdf] [link] [arxiv](full version)
  Varun Kanade, Leslie G. Valiant and Jennifer Wortman Vaughan
  In the 23rd Annual Conference on Learning Theory, COLT 2010
  
  
• Potential-based Agnostic Boosting [pdf] [link]
  Adam Tauman Kalai and Varun Kanade
  In the 22nd Advances in Neural Information Processing Systems, NIPS 2009
  
  
• Sleeping Experts and Bandits with Stochastic Action Availability and Adversarial Rewards [pdf] [link]
  Brendan McMahan, Brent Bryan and Varun Kanade
  In the 12th International Conference on Artificial Intelligence and Statistics, AISTATS 2009
  
  
• Life (and Routing) on a Wireless Manifold [pdf] [link]
  Varun Kanade and Santosh Vempala
  In 6th Workshop on Hot Topics in Networks, HOTNETS 2007
  
  
• SWARM: A Parallel Programming Framework for Multi-core Processors [pdf] [link]
  David A. Bader, Varun Kanade and Kamesh Madduri
  In Workshop on Multi-threaded Architectures and Applications (at IPDPS), MTAAP 2007
  
  
• Approximate Symbolic Reachability of Networks of Transition Systems [pdf] [link]
  Sudeep Juvekar, Ankur Taly, Varun Kanade and Supratik Chakraborty
  Book chapter in Next Generation Design and Verification Methodologies for Distributed Embedded Control Systems Springer. (Invited Paper)

Thesis

• Computational Questions in Evolution
  Harvard University, 2012
  Adviser: Leslie G. Valiant
  [pdf] [harvard repository]

Short Descriptions of Research Projects

• Attribute-Efficient Evolvability of Sparse Linear Functions. (with E. Angelino) [pdf]
  This short document describes our paper (see below) in a language that is accessible to general scientists.