Vishnu V. Narayan
Ph.D. Student in Computer ScienceMcGill 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.