518 citations · 948 across the 34 of their papers we have counts for
5 papers · 1 filter
Better Analysis of GREEDY Binary Search Tree on Decomposable Sequences
Navin Goyal, Manoj Gupta
In their seminal paper [Sleator and Tarjan, J.ACM, 1985], the authors conjectured that the splay tree is dynamically optimal binary search tree (BST). In spite of decades of intens…
On Computing Maximal Independent Sets of Hypergraphs in Parallel
Ioana O. Bercea, Navin Goyal, David G. Harris +1
Whether or not the problem of finding maximal independent sets (MIS) in hypergraphs is in (R)NC is one of the fundamental problems in the theory of parallel computing. Unlike the w…
Lower Bounds for the Average and Smoothed Number of Pareto Optima
Navin Goyal, Luis Rademacher
Smoothed analysis of multiobjective 0-1 linear optimization has drawn considerable attention recently. The number of Pareto-optimal solutions (i.e., solutions with the property tha…
On Dynamic Optimality for Binary Search Trees
Navin Goyal, Manoj Gupta
Does there exist O(1)-competitive (self-adjusting) binary search tree (BST) algorithms? This is a well-studied problem. A simple offline BST algorithm GreedyFuture was proposed ind…
Deterministic Algorithms for the Lovasz Local Lemma
Karthekeyan Chandrasekaran, Navin Goyal, Bernhard Haeupler
The Lovasz Local Lemma (LLL) is a powerful result in probability theory that states that the probability that none of a set of bad events happens is nonzero if the probability of e…