From the 1 of 64 linked papers with an AI index.
3 citations · 9 across the 46 of their papers we have counts for
5 papers · 1 filter
Online Edge Coloring via Tree Recurrences and Correlation Decay
Janardhan Kulkarni, Yang P. Liu, Ashwin Sah +2
We give an online algorithm that with high probability computes a edge coloring on a graph with maximum degree under online…
Approximate counting and sampling via local central limit theorems
Vishesh Jain, Will Perkins, Ashwin Sah +1
We give an FPTAS for computing the number of matchings of size in a graph of maximum degree on vertices, for all , where is fixed and $m^*(…
A Gaussian fixed point random walk
Yang P. Liu, Ashwin Sah, Mehtaab Sawhney
In this note, we design a discrete random walk on the real line which takes steps (and one with steps in ) where at least of the signs are i…
Perfectly Sampling -Colorings in Graphs
Vishesh Jain, Ashwin Sah, Mehtaab Sawhney
We present a randomized algorithm which takes as input an undirected graph on vertices with maximum degree , and a number of colors , and returns…
Discrepancy Minimization via a Self-Balancing Walk
Ryan Alweiss, Yang P. Liu, Mehtaab Sawhney
We study discrepancy minimization for vectors in under various settings. The main result is the analysis of a new simple random process in multiple dimensions throug…