Vishnu V. Narayan

Ph.D. Student in Computer Science
McGill University

McConnell Engineering Building, Room 306
3380 University
Montreal QC H3A 0E9

first.last at mail.mcgill.ca

I am working towards a Ph.D. in Computer Science at McGill University under the excellent supervision of Adrian Vetta. My interests include algorithms, combinatorics, optimization, and game theory, and my current focus is on the structure, efficiency and fairness of combinatorial auctions and allocations. Right now I'm also working on online coloring and positional games. My CV.

I have an M.Math. degree in Combinatorics and Optimization (2017) from the University of Waterloo, where I was advised by Joseph Cheriyan and worked on approximating graph connectivity. I have a B.Eng. in Information Science (2015) from R.V. College of Engineering (India) where I received my department's Best Outgoing Student Award. I also have a Harold H. Helm Fellowship and Murata Family Fellowship from McGill and a Teaching Assistant Award from the McGill School of Computer Science. Outside of academia, I enjoy competitive programming and video games (particularly RTSes).

Preprints and Working Papers

Who Wins Hex When One Player Plays Randomly?
With J. Barrett, N. Brustle, S. Clusiau, R. Hayward, N. Ndiaye, and B. Reed

Publications

Journal

J4.	Online Coloring and a New Type of Adversary for Online Graph Problems With Y. Li and D. Pankratov Algorithmica (2022) Extended journal version of C4
J3.	The Declining Price Anomaly is not Universal in Multi-Buyer Sequential Auctions (but almost is) With E. Prebet and A. Vetta Theory of Computing Systems: SAGT 2019 Special Issue (2022) Extended journal version of C2
J2.	Risk-Free Bidding in Complement-Free Combinatorial Auctions With G. Rayaprolu and A. Vetta Theory of Computing Systems: SAGT 2019 Special Issue (2022) Extended journal version of C1
J1.	The Matching Augmentation Problem: A 7/4-Approximation Algorithm With J. Cheriyan, J. Dippel, F. Grandoni and A. Khan Mathematical Programming (2020)

Conference

C7.	Two Birds With One Stone: Fairness and Welfare via Transfers With M. Suzuki and A. Vetta SAGT 2021
C6.	The Speed and Threshold of the Biased Hamilton Cycle Game With N. Brustle, S. Clusiau, N. Ndiaye, B. Reed and B. Seamone LAGOS 2021
C5.	The Speed and Threshold of the Biased Perfect Matching Game With N. Brustle, S. Clusiau, N. Ndiaye, B. Reed and B. Seamone LAGOS 2021
C4.	Online Coloring and a New Type of Adversary for Online Graph Problems With Y. Li and D. Pankratov WAOA 2020 [WAOA'20 talk]
C3.	One Dollar Each Eliminates Envy With J. Brustle, J. Dippel, M. Suzuki and A. Vetta EC 2020 [EC'20 talk]
C2.	The Declining Price Anomaly is not Universal in Multi-Buyer Sequential Auctions (but almost is) With E. Prebet and A. Vetta SAGT 2019 [Best Paper]
C1.	Risk-Free Bidding in Complement-Free Combinatorial Auctions With G. Rayaprolu and A. Vetta SAGT 2019

Theses

Approximating Minimum-Size 2-Edge-Connected and 2-Vertex-Connected Spanning Subgraphs (M.Math. 2017)

Ongoing Research

with A. Procaccia. Fair Division, Computational Social Choice.
with A. Vetta. Fair Division, Auctions.
with Y. Li and D. Pankratov. Online Coloring.
with N. Brustle, N. Ndiaye and B. Reed. Positional Games.
with T. Elbaz, S. Grosser, L. Hambardzumyan and N. Ndiaye. Communication Complexity.