# Kedar Dhamdhere

Kedar Dhamdhere is a research scientist at Google. His research interests include model understanding and Q&A systems. In the past, he has worked on search at Google and Facebook. Prior to joining Google he finished his PhD in Computer Science from CMU.

Authored Publications

Google Publications

Other Publications

Sort By

Analyza: Exploring Data with Conversation

Kevin McCurley

Ralfi Nahmias

Intelligent User Interfaces 2017, ACM, Limassol, Cyprus (to appear)

Preview abstract
We describe Analyza, a system that helps lay users explore
data. Analyza has been used within two large real world systems. The
first is a question-and-answer feature in a spreadsheet product. The
second provides convenient access to a revenue/inventory database
for a large sales force. Both user bases consist of users who do not
necessarily have coding skills, demonstrating Analyza's ability to
democratize access to data.
We discuss the key design decisions in implementing this system.
For instance, how to mix structured and natural language modalities,
how to use conversation to disambiguate and simplify querying, how
to rely on the ``semantics'' of the data to compensate for the lack
of syntactic structure, and how to efficiently curate the data.
View details

Metric Embeddings with Relaxed Guarantees

T H Hubert Chan

Anupam Gupta

Jon m Kleinberg

Aleksandrs Slivkins

SIAM Journal on Computing, vol. 38 (2009), pp. 2303-2329

Preview abstract
We consider the problem of embedding finite metrics with slack: We seek to produce embeddings with small dimension and distortion while allowing a (small) constant fraction of all distances to be arbitrarily distorted. This definition is motivated by recent research in the networking community, which achieved striking empirical success at embedding Internet latencies with low distortion into low-dimensional Euclidean space, provided that some small slack is allowed. Answering an open question of Kleinberg, Slivkins, and Wexler [in Proceedings of the 45th IEEE Symposium on Foundations of Computer Science, 2004], we show that provable guarantees of this type can in fact be achieved in general: Any finite metric space can be embedded, with constant slack and constant distortion, into constant-dimensional Euclidean space. We then show that there exist stronger embeddings into $\ell_1$ which exhibit gracefully degrading distortion: There is a single embedding into $\ell_1$ that achieves distortion at most $O(\log\frac{1}{\epsilon})$ on all but at most-1.5pt an $\epsilon$ fraction of distances simultaneously for all $\epsilon>0$. We extend this with distortion1pt $O(\log\frac{1}{\epsilon})^{1/p}$ to maps into general $\ell_p$, $p\geq1$, for several classes of metrics, including those with bounded doubling dimension and those arising from the shortest-path metric of a graph with an excluded minor. Finally, we show that many of our constructions are tight and give a general technique to obtain lower bounds for $\epsilon$-slack embeddings from lower bounds for low-distortion embeddings.
View details

Algorithms for Efficient Near-Perfect Phylogenetic Tree Reconstruction in Theory and Practice

Preview
Srinath Sridhar

Guy E. Blelloch

Eran Halperin

R. Ravi

Russell Schwartz

IEEE/ACM Trans. Comput. Biology Bioinform., vol. 4 (2007), pp. 561-571

Simple Reconstruction of Binary Near-Perfect Phylogenetic Trees

Preview
Srinath Sridhar

Guy E. Blelloch

Eran Halperin

R. Ravi

Russell Schwartz

International Conference on Computational Science (2) (2006), pp. 799-806

Relaxing Haplotype Block Models for Association Testing

Natalie Castellana

Srinath Sridhar

Russell Schwartz

Pacific Symposium on Biocomputing (2006), pp. 454-466

Fixed Parameter Tractability of Binary Near-Perfect Phylogenetic Tree Reconstruction

Guy E. Blelloch

Eran Halperin

R. Ravi

Russell Schwartz

Srinath Sridhar

ICALP (1) (2006), pp. 667-678

Approximation Algorithms for Minimizing Average Distortion

Improved embeddings of graph metrics into random trees

Metric Embeddings with Relaxed Guarantees

Ittai Abraham

Yair Bartal

Hubert T.-H. Chan

Anupam Gupta

Jon M. Kleinberg

Ofer Neiman

Aleksandrs Slivkins

FOCS (2005), pp. 83-100

Finding (Recently) Frequent Items in Distributed Data Streams

On Two-Stage Stochastic Minimum Spanning Trees

Approximation algorithms for low-distortion embeddings into low-dimensional spaces

Mihai Badoiu

Anupam Gupta

Yuri Rabinovich

Harald R"cke

R. Ravi

Anastasios Sidiropoulos

SODA (2005), pp. 119-128

How to Pay, Come What May: Approximation Algorithms for Demand-Robust Covering Problems

Approximating Additive Distortion of Embeddings into Line Metrics

APPROX-RANDOM (2004), pp. 96-104

Non-Clairvoyant Scheduling for Minimizing Mean Slowdown

Nikhil Bansal

Jochen Koenemann

Amitabh Sinha

Algorithmica, vol. 40 (2004), pp. 305-318

Approximation Algorithms for Minimizing Average Distortion

WIC: A General-Purpose Algorithm for Monitoring Web Information Sources

Scheduling for Flow-Time with Admission Control

Non-clairvoyant Scheduling for Minimizing Mean Slowdown

Minimizing weighted flow time