Li-Yang Tan

activity

20092023

most citedConvergence, unanimity and disagreement in majority dynamics on unimodular graphs and random graphs

37 citations · 101 across the 43 of their papers we have counts for

collaborators

Showing 2019Show all

2 papers · 1 filter

cs.CC2019

Constructive derandomization of query algorithms

Guy Blanc, Jane Lange, Li-Yang Tan

We give efficient deterministic algorithms for converting randomized query algorithms into deterministic ones. We first give an algorithm that takes as input a randomized $q$ -query…

cs.DS2019★ 5 cited

Top-down induction of decision trees: rigorous guarantees and inherent limitations

Guy Blanc, Jane Lange, Li-Yang Tan

Consider the following heuristic for building a decision tree for a function $f : {0, 1}^{n} \to {\pm 1}$ . Place the most influential variable $x_{i}$ of $f$ at the root, and recurs…