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


Vishnu V. Narayan

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

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

Ongoing Research