Shyam Narayanan

activity

20162026

most citedLearning-based Support Estimation in Sublinear Time

8 citations · 41 across the 26 of their papers we have counts for

collaborators

Showing 2018Show all

4 papers · 1 filter

cs.DS2018

Optimal terminal dimensionality reduction in Euclidean space

Shyam Narayanan, Jelani Nelson

Let $ε \in (0, 1)$ and $X \subset R^{d}$ be arbitrary with $∣ X ∣$ having size $n > 1$ . The Johnson-Lindenstrauss lemma states there exists $f : X \to R^{m}$ with…

math.PR2018

3-wise Independent Random Walks can be Slightly Unbounded

Shyam Narayanan

Recently, many streaming algorithms have utilized generalizations of the fact that the expected maximum distance of any $4$ -wise independent random walk on a line over $n$ steps is…

cs.DS2018★ 1 cited

Deterministic $O (1)$ -Approximation Algorithms to 1-Center Clustering with Outliers

Shyam Narayanan

The 1-center clustering with outliers problem asks about identifying a prototypical robust statistic that approximates the location of a cluster of points. Given some constant $0 <…

math.CO2018

Resolving Two Conjectures on Staircase Encodings and Boundary Grids of $132$ and $123$ -avoiding permutations

Shyam Narayanan

This paper analyzes relations between pattern avoidance of certain permutations and graphs on staircase grids and boundary grids, and proves two conjectures posed by Bean, Tannock,…

Optimal terminal dimensionality reduction in Euclidean space

3-wise Independent Random Walks can be Slightly Unbounded

Deterministic O(1)-Approximation Algorithms to 1-Center Clustering with Outliers

Resolving Two Conjectures on Staircase Encodings and Boundary Grids of 132 and 123-avoiding permutations

Deterministic $O (1)$ -Approximation Algorithms to 1-Center Clustering with Outliers

Resolving Two Conjectures on Staircase Encodings and Boundary Grids of $132$ and $123$ -avoiding permutations