Ashwin Sah

activity

20182022

most citedDiagonal Ramsey via effective quasirandomness

6 citations · 9 across the 13 of their papers we have counts for

collaborators

Showing cs.DSShow all

4 papers · 1 filter

cs.DS2021

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 $(\frac{e}{e - 1} + o (1)) Δ$ edge coloring on a graph $G$ with maximum degree $Δ = ω (lo g n)$ under online…

cs.DS2021

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 $k$ in a graph $G$ of maximum degree $Δ$ on $n$ vertices, for all $k \leq (1 - δ) m^{*} (G)$ , where $δ > 0$ is fixed and $m^*(…

cs.DS2021

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 $0, \pm 1$ (and one with steps in ${\pm 1, 2}$ ) where at least $96%$ of the signs are $\pm 1$ i…

cs.DS2020

Perfectly Sampling $k \geq (8/3 + o (1)) Δ$ -Colorings in Graphs

Vishesh Jain, Ashwin Sah, Mehtaab Sawhney

We present a randomized algorithm which takes as input an undirected graph $G$ on $n$ vertices with maximum degree $Δ$ , and a number of colors $k \geq (8/3 + o_{Δ} (1)) Δ$ , and returns…

Online Edge Coloring via Tree Recurrences and Correlation Decay

Approximate counting and sampling via local central limit theorems

A Gaussian fixed point random walk

Perfectly Sampling k≥(8/3+o(1))Δ-Colorings in Graphs

Perfectly Sampling $k \geq (8/3 + o (1)) Δ$ -Colorings in Graphs