Deterministic Algorithms for the Lovasz Local Lemma (2009)
Chandrasekaran, Karthekeyan, Goyal, Navin, Haeupler, Bernhard
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 each event is small...
Navin Goyal, Lower Bounds, Noisy Broadcast Problem
We prove the first non-trivial (superlinear) lower bound in the noisy broadcast model of distributed computation. In this model, there are n +1processors P0,P1,...,Pn. Each Pi, fori ≥ 1, initially...
Learning convex bodies is hard (2009)
Goyal, Navin, Rademacher, Luis
We show that learning a convex body in $\RR^d$, given random samples from the body, requires $2^{\Omega(\sqrt{d/\eps})}$ samples. By learning a convex body we mean finding a set having at most $\eps$...
Navin Goyal, Lower Bounds, Noisy Broadcast Problem
We prove the first non-trivial (superlinear) lower bound in the noisy broadcast model of distributed computation. In this model, there are n +1processors P0,P1,...,Pn. Each Pi, fori ≥ 1, initially...
Disorder inequality: A combinatorial approach to nearest neighbor search (2008)
We say that an algorithm for nearest neighbor search is combinatorial if only direct comparisons between two pairwise similarity values are allowed. Combinatorial algorithms for nearest neighbor...
Optimal Separation of EROW and CROW PRAMs (2008)
Navin Goyal, Michael Saks, S. Venkatesh
Abstract We consider the problem of evaluating a booleanfunction on PRAMs. We exhibit a boolean function f: {0, 1}n! {0, 1} that can be evaluated in time O(log log n) in a deterministic CROW...
Disorder inequality: A combinatorial approach to nearest neighbor search (2008)
We say that an algorithm for nearest neighbor search is combinatorial if only direct comparisons between two pairwise similarity values are allowed. Combinatorial algorithms for nearest neighbor...
We answer in negative a question of Gál and Miltersen [3] about a combinatorial game arising in the study of timespace trade-offs for data structures.
Expanders via Random Spanning Trees (2008)
Goyal, Navin, Rademacher, Luis, Vempala, Santosh
Motivated by the problem of routing reliably and scalably in a graph, we introduce the notion of a splicer, the union of spanning trees of a graph. We prove that for any bounded-degree n-vertex...
An Efficient Approximation Algorithm for Point Pattern Matching Under Noise (2008)
Point pattern matching problems are of fundamental importance in various areas including computer vision and structural bioinformatics. In this paper, we study one of the more general problems, known...
We answer in negative a question of Gál and Miltersen [3] about a combinatorial game arising in the study of timespace trade-offs for data structures.
1 THE GRAHAM-KNOWLTON PROBLEM REVISITED (2008)
Navin Goyal, Sachin Lodha, S. Muthukrishnan
In late ¢ ¡ ’s, Graham and Knowlton introduced the WIP (wire identification problem) that affected electricians: match the wires in the ceiling to those in the basement while making the fewest...
The Graham-Knowlton Problem Revisited ⋆ (2008)
Navin Goyal, Sachin Lodha, S. Muthukrishnan
Abstract. In late 60’s, Graham and Knowlton introduced the WIP (wire identification problem) that affected electricians: match the wires in the ceiling to those in the basement while making the...
Arkadev Chattopadhyay, Pavel Pudlák, Navin Goyal, Denis Thérien
Let CC[m] be the class of circuits in which all gates are MODm gates. In this paper we prove lower bounds for circuits in CC[m] and related classes. • Circuits in which all gates are MODm gates...
An Algorithmic Approach to the Identification of Rigid Domains in Proteins (2006)
Many proteins undergo conformational changes to perform their functions. A simple mechanism of conformational change in proteins is a rigid domain motion, in which two parts of a structure move...
An Algorithmic Approach to the Identification of Rigid Domains in Proteins (2006)
Many proteins undergo conformational changes to perform their functions. A simple mechanism of conformational change in proteins is a rigid domain motion, in which two parts of a structure move...
Rounds vs Queries Trade-off in Noisy Computation (2006)
We show that a noisy parallel decision tree making O(n) queries needs Ω(log ∗ n) rounds to compute OR of n bits. This answers a question of Newman [IEEE Conference on Computational Complexity,...
An Efficient Approximation Algorithm for Point Pattern Matching Under Noise (2005)
Point pattern matching problems are of fundamental importance in various areas including computer vision and structural bioinformatics. In this paper, we study one of the more general problems, known...
Lower bounds for the noisy broadcast problem (2005)
Navin Goyal, Michael Saks, Guy Kindler
We prove the first non-trivial (super linear) lower bound in the noisy broadcast model, defined by El Gamal in [6]. In this model there are n + 1 processors P0, P1,..., Pn, each of which is initially...
Optimal Separation of EROW and CROW PRAMs (2005)
Navin Goyal, Michael Saks, S. Venkatesh
We consider the problem of evaluating a Boolean function on PRAMs. We exhibit a Boolean function f: {0, 1} n → {0, 1} that can be evaluated in time O(log log n) on a deterministic CROW (Concurrent...
Lower bounds for the noisy broadcast problem (2005)
Navin Goyal, Michael Saks, Guy Kindler
We prove the first non-trivial (super linear) lower bound in the noisy broadcast model, defined by El Gamal in [6]. In this model there are n + 1 processors P0, P1,..., Pn, each of which is initially...
A combinatorial shape matching algorithm for rigid protein docking (2004)
Abstract. The protein docking problem is to predict the structure of protein-protein complexes from the structures of individual proteins. It is believed that shape complementarity plays a dominant...
The Graham-Knowlton Problem Revisited (2004)
Navin Goyal, Sachin Lodha, S. Muthukrishnan
In late 60’s, Graham and Knowlton introduced the WIP (wire identification problem) that affected electricians: match the wires in the ceiling to those in the basement while making the fewest trips....