Varun Kanade

According to our database, Varun Kanade authored at least 60 papers between 2007 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2024

Separations in the Representational Capabilities of Transformers and Recurrent Architectures.

Satwik Bhattamishra, Michael Hahn, Phil Blunsom, Varun Kanade

CoRR, 2024

Understanding In-Context Learning in Transformers and LLMs by Learning to Learn Discrete Functions.

Satwik Bhattamishra, Arkil Patel, Phil Blunsom, Varun Kanade

Proceedings of the Twelfth International Conference on Learning Representations, 2024

2023

On Coalescence Time in Graphs: When Is Coalescing as Fast as Meeting?

Varun Kanade, Frederik Mallmann-Trenn, Thomas Sauerwald

ACM Trans. Algorithms, April, 2023

Partial Matrix Completion.

Elad Hazan, Adam Tauman Kalai, Varun Kanade, Clara Mohri, Y. Jennifer Sun

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Simplicity Bias in Transformers and their Ability to Learn Sparse Boolean Functions.

Satwik Bhattamishra, Arkil Patel, Varun Kanade, Phil Blunsom

Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), 2023

2022

Partial Matrix Completion.

Varun Kanade, Elad Hazan, Adam Tauman Kalai

CoRR, 2022

Beyond Impossibility: Balancing Sufficiency, Separation and Accuracy.

Limor Gultchin, Vincent Cohen-Addad, Sophie Giffard-Roisin, Varun Kanade, Frederik Mallmann-Trenn

CoRR, 2022

Exponential Tail Local Rademacher Complexity Risk Bounds Without the Bernstein Condition.

Varun Kanade, Patrick Rebeschini, Tomas Vaskevicius

CoRR, 2022

When are Local Queries Useful for Robust Learning?

Pascale Gourdeau, Varun Kanade, Marta Kwiatkowska, James Worrell

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Sample Complexity Bounds for Robustly Learning Decision Lists against Evasion Attacks.

Pascale Gourdeau, Varun Kanade, Marta Kwiatkowska, James Worrell

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, 2022

2021

Towards optimally abstaining from prediction.

Adam Tauman Kalai, Varun Kanade

CoRR, 2021

Towards optimally abstaining from prediction with OOD test examples.

Adam Kalai, Varun Kanade

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

How Benign is Benign Overfitting ?

Amartya Sanyal, Puneet K. Dokania, Varun Kanade, Philip H. S. Torr

Proceedings of the 9th International Conference on Learning Representations, 2021

Efficient Learning with Arbitrary Covariate Shift.

Adam Tauman Kalai, Varun Kanade

Proceedings of the Algorithmic Learning Theory, 2021

Online k-means Clustering.

Vincent Cohen-Addad, Benjamin Guedj, Varun Kanade, Guy Rom

Proceedings of the 24th International Conference on Artificial Intelligence and Statistics, 2021

2020

Lottery Tickets in Linear Models: An Analysis of Iterative Magnitude Pruning.

Bryn Elesedy, Varun Kanade, Yee Whye Teh

CoRR, 2020

The Statistical Complexity of Early-Stopped Mirror Descent.

Tomas Vaskevicius, Varun Kanade, Patrick Rebeschini

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Adaptive Reduced Rank Regression.

Qiong Wu, Felix Ming Fai Wong, Yanhua Li, Zhenming Liu, Varun Kanade

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Differentiable Causal Backdoor Discovery.

Limor Gultchin, Matt J. Kusner, Varun Kanade, Ricardo Silva

Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, 2020

2019

mu - biased quantum Fourier sampling.

Varun Kanade, Andrea Rocchetto, Simone Severini

Quantum Inf. Comput., 2019

Hierarchical Clustering: Objective Functions and Algorithms.

Vincent Cohen-Addad, Varun Kanade, Frederik Mallmann-Trenn, Claire Mathieu

J. ACM, 2019

On the Hardness of Robust Classification.

Pascale Gourdeau, Varun Kanade, Marta Kwiatkowska, James Worrell

Electron. Colloquium Comput. Complex., 2019

On coalescence time in graphs: When is coalescing as fast as meeting?: Extended Abstract.

Varun Kanade, Frederik Mallmann-Trenn, Thomas Sauerwald

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Implicit Regularization for Optimal Sparse Recovery.

Tomas Vaskevicius, Varun Kanade, Patrick Rebeschini

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Decentralized Cooperative Stochastic Bandits.

David Martínez-Rubio, Varun Kanade, Patrick Rebeschini

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Statistical Windows in Testing for the Initial Distribution of a Reversible Markov Chain.

Quentin Berthet, Varun Kanade

Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, 2019

2018

Decentralized Cooperative Stochastic Multi-armed Bandits.

David Martínez-Rubio, Varun Kanade, Patrick Rebeschini

CoRR, 2018

Low Rank Structure of Learned Representations.

Amartya Sanyal, Varun Kanade, Philip H. S. Torr

CoRR, 2018

Learning DNFs under product distributions via μ-biased quantum Fourier sampling.

Varun Kanade, Andrea Rocchetto, Simone Severini

CoRR, 2018

Clustering Redemption-Beyond the Impossibility of Kleinberg's Axioms.

Vincent Cohen-Addad, Varun Kanade, Frederik Mallmann-Trenn

Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018

TAPAS: Tricks to Accelerate (encrypted) Prediction As a Service.

Amartya Sanyal, Matt J. Kusner, Adrià Gascón, Varun Kanade

Proceedings of the 35th International Conference on Machine Learning, 2018

2017

How Large Is Your Graph?.

Varun Kanade, Frederik Mallmann-Trenn, Victor Verdugo

Proceedings of the 31st International Symposium on Distributed Computing, 2017

Brief Announcement: How Large is your Graph?

Varun Kanade, Frederik Mallmann-Trenn, Victor Verdugo

Proceedings of the ACM Symposium on Principles of Distributed Computing, 2017

From which world is your graph.

Cheng Li, Felix Ming Fai Wong, Zhenming Liu, Varun Kanade

Proceedings of the Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 2017

Hierarchical Clustering Beyond the Worst-Case.

Vincent Cohen-Addad, Varun Kanade, Frederik Mallmann-Trenn

Proceedings of the Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 2017

Reliably Learning the ReLU in Polynomial Time.

Surbhi Goel, Varun Kanade, Adam R. Klivans, Justin Thaler

Proceedings of the 30th Conference on Learning Theory, 2017

Online Optimization of Smoothed Piecewise Constant Functions.

Vincent Cohen-Addad, Varun Kanade

Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, 2017

2016

Global and Local Information in Clustering Labeled Block Models.

Varun Kanade, Elchanan Mossel, Tselil Schramm

IEEE Trans. Inf. Theory, 2016

Distance in the Forest Fire Model How far are you from Eve?

Varun Kanade, Reut Levi, Zvi Lotker, Frederik Mallmann-Trenn, Claire Mathieu

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Stable Matching with Evolving Preferences.

Varun Kanade, Nikos Leonardos, Frédéric Magniez

Proceedings of the Approximation, 2016

2015

MCMC Learning.

Varun Kanade, Elchanan Mossel

Proceedings of The 28th Conference on Learning Theory, 2015

Learning with a Drifting Target Concept.

Steve Hanneke, Varun Kanade, Liu Yang

Proceedings of the Algorithmic Learning Theory - 26th International Conference, 2015

2014

Attribute-efficient evolvability of linear functions.

Elaine Angelino, Varun Kanade

Proceedings of the Innovations in Theoretical Computer Science, 2014

Tracking Adversarial Targets.

Yasin Abbasi-Yadkori, Peter L. Bartlett, Varun Kanade

Proceedings of the 31th International Conference on Machine Learning, 2014

Distribution-independent Reliable Learning.

Varun Kanade, Justin Thaler

Proceedings of The 27th Conference on Learning Theory, 2014

2013

Online Learning in Markov Decision Processes with Adversarially Chosen Transition Probability Distributions.

Yasin Abbasi-Yadkori, Peter L. Bartlett, Varun Kanade, Yevgeny Seldin, Csaba Szepesvári

Proceedings of the Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of a meeting held December 5-8, 2013

Learning Using Local Membership Queries.

Pranjal Awasthi, Vitaly Feldman, Varun Kanade

Proceedings of the COLT 2013, 2013

2012

Computational Bounds on Statistical Query Learning.

Vitaly Feldman, Varun Kanade

Proceedings of the COLT 2012, 2012

Reliable agnostic learning.

Adam Tauman Kalai, Varun Kanade, Yishay Mansour

J. Comput. Syst. Sci., 2012

Learning using Local Membership Queries under Smooth Distributions

Pranjal Awasthi, Varun Kanade

CoRR, 2012

Distributed Non-Stochastic Experts.

Varun Kanade, Zhenming Liu, Bozidar Radunovic

Proceedings of the Advances in Neural Information Processing Systems 25: 26th Annual Conference on Neural Information Processing Systems 2012. Proceedings of a meeting held December 3-6, 2012

2011

Learning Hurdles for Sleeping Experts.

Varun Kanade, Thomas Steinke

Electron. Colloquium Comput. Complex., 2011

Computational Bottlenecks for Evolvability.

Varun Kanade

Electron. Colloquium Comput. Complex., 2011

Efficient Learning of Generalized Linear and Single Index Models with Isotonic Regression.

Sham M. Kakade, Adam Kalai, Varun Kanade, Ohad Shamir

Proceedings of the Advances in Neural Information Processing Systems 24: 25th Annual Conference on Neural Information Processing Systems 2011. Proceedings of a meeting held 12-14 December 2011, 2011

Evolution with Recombination.

Varun Kanade

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

2010

Evolution with Drifting Targets.

Varun Kanade, Leslie G. Valiant, Jennifer Wortman Vaughan

Proceedings of the COLT 2010, 2010

2009

Sleeping Experts and Bandits with Stochastic Action Availability and Adversarial Rewards.

Varun Kanade, H. Brendan McMahan, Brent Bryan

Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics, 2009

Potential-Based Agnostic Boosting.

Adam Kalai, Varun Kanade

Proceedings of the Advances in Neural Information Processing Systems 22: 23rd Annual Conference on Neural Information Processing Systems 2009. Proceedings of a meeting held 7-10 December 2009, 2009

2007

SWARM: A Parallel Programming Framework for Multicore Processors.

David A. Bader, Varun Kanade, Kamesh Madduri

Proceedings of the 21th International Parallel and Distributed Processing Symposium (IPDPS 2007), 2007

Life (and routing) on the Wireless Manifold.

Varun Kanade, Santosh S. Vempala

Proceedings of the 6th ACM Workshop on Hot Topics in Networks, 2007