# Ravi Kumar

Affiliations:
• Yahoo! Research
• Cornell University, Department of Computer Science

According to our database1, Ravi Kumar authored at least 281 papers between 1995 and 2022.

Collaborative distances:
• Dijkstra number2 of three.
• Erdős number3 of two.

Book
In proceedings
Article
PhD thesis
Other

## Bibliography

2022
Multiparty Reach and Frequency Histogram: Private, Secure, and Practical.
Proc. Priv. Enhancing Technol., 2022

Differentially Private All-Pairs Shortest Path Distances: Improved Algorithms and Lower Bounds.
CoRR, 2022

Parsimonious Learning-Augmented Caching.
CoRR, 2022

Learning-Augmented Weighted Paging.
Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

2021
Private Rank Aggregation in Central and Local Models.
CoRR, 2021

User-Level Private Learning via Correlated Sampling.
CoRR, 2021

Large-Scale Differentially Private BERT.
CoRR, 2021

Google COVID-19 Vaccination Search Insights: Anonymization Process Description.
CoRR, 2021

Sample-efficient proper PAC learning with approximate differential privacy.
Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Non-Clairvoyant Scheduling with Predictions.
Proceedings of the SPAA '21: 33rd ACM Symposium on Parallelism in Algorithms and Architectures, 2021

Online Knapsack with Frequency Predictions.
Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

User-Level Differentially Private Learning via Correlated Sampling.
Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

Deep Learning with Label Differential Privacy.
Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

Logarithmic Regret from Sublinear Hints.
Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

On Distributed Differential Privacy and Counting Distinct Elements.
Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

Differentially Private Aggregation in the Shuffle Model: Almost Central Accuracy in Almost a Single Message.
Proceedings of the 38th International Conference on Machine Learning, 2021

Light RUMs.
Proceedings of the 38th International Conference on Machine Learning, 2021

Locally Private k-Means in One Round.
Proceedings of the 38th International Conference on Machine Learning, 2021

On the Power of Multiple Anonymous Messages: Frequency Estimation and Selection in the Shuffle Model of Differential Privacy.
Proceedings of the Advances in Cryptology - EUROCRYPT 2021, 2021

On Avoiding the Union Bound When Answering Multiple Differentially Private Queries.
Proceedings of the Conference on Learning Theory, 2021

Near-tight closure b ounds for the Littlestone and threshold dimensions.
Proceedings of the Algorithmic Learning Theory, 2021

Robust and Private Learning of Halfspaces.
Proceedings of the 24th International Conference on Artificial Intelligence and Statistics, 2021

Power of Hints for Online Learning with Movement Costs.
Proceedings of the 24th International Conference on Artificial Intelligence and Statistics, 2021

2020
Scale-Free Allocation, Amortized Convexity, and Myopic Weighted Paging.
CoRR, 2020

CoRR, 2020

Near-tight closure bounds for Littlestone and threshold dimensions.
CoRR, 2020

A Note on Double Pooling Tests.
CoRR, 2020

Asymptotic Behavior of Sequence Models.
Proceedings of the WWW '20: The Web Conference 2020, Taipei, Taiwan, April 20-24, 2020, 2020

On the Learnability of Random Deep Networks.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Interleaved Caching with Access Graphs.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Differentially Private Clustering: Tight Approximation Ratios.
Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Online Linear Optimization with Many Hints.
Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Fair Hierarchical Clustering.
Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Private Counting from Anonymous Messages: Near-Optimal Accuracy with Vanishing Communication Overhead.
Proceedings of the 37th International Conference on Machine Learning, 2020

Online Learning with Imperfect Hints.
Proceedings of the 37th International Conference on Machine Learning, 2020

Pure Differentially Private Summation from Anonymous Messages.
Proceedings of the 1st Conference on Information-Theoretic Cryptography, 2020

Fair Correlation Clustering.
Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, 2020

2019
On the Distortion of Locality Sensitive Hashing.
SIAM J. Comput., 2019

On the Power of Multiple Anonymous Messages.
IACR Cryptol. ePrint Arch., 2019

Preventing Adversarial Use of Datasets through Fair Core-Set Construction.
CoRR, 2019

Private Heavy Hitters and Range Queries in the Shuffled Model.
CoRR, 2019

On the Learnability of Deep Random Networks.
CoRR, 2019

Efficient Rematerialization for Deep Networks.
Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Hard to Park?: Estimating Parking Difficulty at Scale.
Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2019

Clustering without Over-Representation.
Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2019

Semi-Online Bipartite Matching.
Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

Faster Algorithms for Binary Matrix Factorization.
Proceedings of the 36th International Conference on Machine Learning, 2019

Testing Mixtures of Discrete Distributions.
Proceedings of the Conference on Learning Theory, 2019

Matroids, Matchings, and Fairness.
Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, 2019

2018
Web Page Quality Metrics.
Proceedings of the Encyclopedia of Database Systems, Second Edition, 2018

Motif Counting Beyond Five Nodes.
ACM Trans. Knowl. Discov. Data, 2018

A Discrete Choice Model for Subset Selection.
Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining, 2018

Discrete Choice, Permutations, and Reconstruction.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Improving Online Algorithms via ML Predictions.
Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018

Mallows Models for Top-k Lists.
Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018

Sequences of Sets.
Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2018

Learning a Mixture of Two Multinomial Logits.
Proceedings of the 35th International Conference on Machine Learning, 2018

2017
Local Search Methods for k-Means with Outliers.
Proc. VLDB Endow., 2017

Proceedings of the 26th International Conference on World Wide Web, 2017

Caching with Dual Costs.
Proceedings of the 26th International Conference on World Wide Web Companion, 2017

Counting Graphlets: Space vs Time.
Proceedings of the Tenth ACM International Conference on Web Search and Data Mining, 2017

On the Power Laws of Language: Word Frequency Distributions.
Proceedings of the 40th International ACM SIGIR Conference on Research and Development in Information Retrieval, 2017

Fair Clustering Through Fairlets.
Proceedings of the Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 2017

Algorithms for $\ell_p$ Low-Rank Approximation.
Proceedings of the 34th International Conference on Machine Learning, 2017

Partitioning Orders in Online Shopping Services.
Proceedings of the 2017 ACM on Conference on Information and Knowledge Management, 2017

2016
Current and Future Challenges in Mining Large Networks: Report on the Second SDM Workshop on Mining Networks and Graphs.
SIGKDD Explor., 2016

An Algorithmic View of Voting.
SIAM J. Discret. Math., 2016

Big Data.
Computer, 2016

On Sampling Nodes in a Network.
Proceedings of the 25th International Conference on World Wide Web, 2016

On the Relevance of Irrelevant Alternatives.
Proceedings of the 25th International Conference on World Wide Web, 2016

Modeling User Consumption Sequences.
Proceedings of the 25th International Conference on World Wide Web, 2016

On Mixtures of Markov Chains.
Proceedings of the Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, 2016

Conversational Flow in Oxford-style Debates.
Proceedings of the NAACL HLT 2016, 2016

Sequences, Choices, and their Dynamics.
Proceedings of the 21st International Conference on Management of Data, 2016

Sketching, Embedding and Dimensionality Reduction in Information Theoretic Spaces.
Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, 2016

2015
Fast Greedy Algorithms in MapReduce and Streaming.
ACM Trans. Parallel Comput., 2015

LSH-Preserving Functions and Their Applications.
J. ACM, 2015

Sketching, Embedding, and Dimensionality Reduction for Information Spaces.
CoRR, 2015

Proceedings of the Eighth ACM International Conference on Web Search and Data Mining, 2015

Driven by Food: Modeling Geographic Choice.
Proceedings of the Eighth ACM International Conference on Web Search and Data Mining, 2015

Efficient Algorithms for Public-Private Social Networks.
Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2015

On Learning Mixture Models for Permutations.
Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, 2015

Approximate Modularity.
Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

Refer-to-as Relations as Semantic Knowledge.
Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, 2015

2014
The complexity of LSH feasibility.
Theor. Comput. Sci., 2014

On estimating the average degree.
Proceedings of the 23rd International World Wide Web Conference, 2014

The dynamics of repeat consumption.
Proceedings of the 23rd International World Wide Web Conference, 2014

Learning Entangled Single-Sample Gaussians.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Correlation clustering in MapReduce.
Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2014

Great Question! Question Quality in Community Q&A.
Proceedings of the Eighth International Conference on Weblogs and Social Media, 2014

Event Detection via Communication Pattern Analysis.
Proceedings of the Eighth International Conference on Weblogs and Social Media, 2014

On Reconstructing a Hidden Permutation.
Proceedings of the Approximation, 2014

2013
Models for the Compressible Web.
SIAM J. Comput., 2013

Aggregating crowdsourced binary ratings.
Proceedings of the 22nd International World Wide Web Conference, 2013

Rank quantization.
Proceedings of the Sixth ACM International Conference on Web Search and Data Mining, 2013

Para 'Normal' Activity: On the Distribution of Average Ratings.
Proceedings of the Seventh International Conference on Weblogs and Social Media, 2013

Near-Optimal Bounds for Cross-Validation via Loss Stability.
Proceedings of the 30th International Conference on Machine Learning, 2013

Summarization Through Submodularity and Dispersion.
Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics, 2013

2012
A Constant-Factor Approximation Algorithm for Co-clustering.
Theory Comput., 2012

Scalable K-Means++.
Proc. VLDB Endow., 2012

Densest Subgraph in Streaming and MapReduce.
Proc. VLDB Endow., 2012

Introduction to the Special Issue on Algorithms and Models for the Web Graph.
Internet Math., 2012

Are web users really Markovian?
Proceedings of the 21st World Wide Web Conference 2012, 2012

Object matching in tweets with spatial models.
Proceedings of the Fifth International Conference on Web Search and Web Data Mining, 2012

Attention and Selection in Online Choice Tasks.
Proceedings of the User Modeling, Adaptation, and Personalization, 2012

Selecting Diverse Features via Spectral Regularization.
Proceedings of the Advances in Neural Information Processing Systems 25: 26th Annual Conference on Neural Information Processing Systems 2012. Proceedings of a meeting held December 3-6, 2012

Social sampling.
Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2012

PageRank on an evolving graph.
Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2012

Algorithms on evolving graphs.
Proceedings of the Innovations in Theoretical Computer Science 2012, 2012

Sparse and Lopsided Set Disjointness via Information Theory.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

2011
Sorting and selection on dynamic data.
Theor. Comput. Sci., 2011

Automatic Wrappers for Large Scale Web Extraction.
Proc. VLDB Endow., 2011

An algorithmic treatment of strong queries.
Proceedings of the Forth International Conference on Web Search and Web Data Mining, 2011

Optimizing two-dimensional search results presentation.
Proceedings of the Forth International Conference on Web Search and Web Data Mining, 2011

On scheduling in map-reduce and flow-shops.
Proceedings of the SPAA 2011: Proceedings of the 23rd Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2011

Hiring a secretary from a poset.
Proceedings of the Proceedings 12th ACM Conference on Electronic Commerce (EC-2011), 2011

Fast locality-sensitive hashing.
Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2011

Sampling hidden objects using nearest-neighbor oracles.
Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2011

Cross-Validation and Mean-Square Stability.
Proceedings of the Innovations in Computer Science, 2011

Markov Layout.
Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

Search in the Lost Sense of "Query": Question Formulation in Web Search Queries and its Temporal Changes.
Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, Proceedings of the Conference, 19-24 June, 2011, Portland, Oregon, USA, 2011

2010
Generalized distances between rankings.
Proceedings of the 19th International Conference on World Wide Web, 2010

A characterization of online browsing behavior.
Proceedings of the 19th International Conference on World Wide Web, 2010

Stochastic models for tabbed browsing.
Proceedings of the 19th International Conference on World Wide Web, 2010

Max-cover in map-reduce.
Proceedings of the 19th International Conference on World Wide Web, 2010

Evolution of two-sided markets.
Proceedings of the Third International Conference on Web Search and Web Data Mining, 2010

A sparse Johnson: Lindenstrauss transform.
Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Finding the Jaccard Median.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Dynamics of conversations.
Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2010

Balanced allocation with succinct representation.
Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2010

Structure and Evolution of Online Social Networks.
Proceedings of the Link Mining: Models, Algorithms, and Applications, 2010

2009
Web Page Quality Metrics.
Proceedings of the Encyclopedia of Database Systems, 2009

Sampling Algorithms and Coresets for \$\ell<sub>p</sub> Regression.
SIAM J. Comput., 2009

The Hiring Problem and Lake Wobegon Strategies.
SIAM J. Comput., 2009

A Characterization of Online Search Behavior.
IEEE Data Eng. Bull., 2009

Nearest-neighbor caching for content-match applications.
Proceedings of the 18th International Conference on World Wide Web, 2009

Compressed web indexes.
Proceedings of the 18th International Conference on World Wide Web, 2009

Proceedings of the 18th International Conference on World Wide Web, 2009

Top-<i>k</i> aggregation using intersections of ranked inputs.
Proceedings of the Second International Conference on Web Search and Web Data Mining, 2009

Online social networks: modeling and mining: invited talk.
Proceedings of the Second International Conference on Web Search and Web Data Mining, 2009

Mechanism Design for Complexity-Constrained Bidders.
Proceedings of the Internet and Network Economics, 5th International Workshop, 2009

ShatterPlots: Fast Tools for Mining Large Graphs.
Proceedings of the SIAM International Conference on Data Mining, 2009

A web of concepts.
Proceedings of the Twenty-Eigth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2009

Similarity caching.
Proceedings of the Twenty-Eigth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2009

For a few dollars less: Identifying review pages sans human labels.
Proceedings of the Human Language Technologies: Conference of the North American Chapter of the Association of Computational Linguistics, Proceedings, May 31, 2009

Mining web logs: applications and challenges.
Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Paris, France, June 28, 2009

On compressing social networks.
Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Paris, France, June 28, 2009

Optimizing web traffic via the media scheduling problem.
Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Paris, France, June 28, 2009

Sort Me If You Can: How to Sort Dynamic Data.
Proceedings of the Automata, Languages and Programming, 36th Internatilonal Colloquium, 2009

Matching Reviews to Objects using a Language Model.
Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing, 2009

Modeling and Algorithmic Challenges in Online Social Networks.
Proceedings of the Combinatorial Pattern Matching, 20th Annual Symposium, 2009

An analysis framework for search sequences.
Proceedings of the 18th ACM Conference on Information and Knowledge Management, 2009

A translation model for matching reviews to objects.
Proceedings of the 18th ACM Conference on Information and Knowledge Management, 2009

2008
The One-Way Communication Complexity of Hamming Distance.
Theory Comput., 2008

Relaxation in text search using taxonomies.
Proc. VLDB Endow., 2008

Deterministic Decentralized Search in Random Graphs.
Internet Math., 2008

A graph-theoretic approach to webpage segmentation.
Proceedings of the 17th International Conference on World Wide Web, 2008

Spatial variation in search engine queries.
Proceedings of the 17th International Conference on World Wide Web, 2008

Connectivity structure of bipartite graphs via the KNC-plot.
Proceedings of the International Conference on Web Search and Web Data Mining, 2008

Preferential behavior in online groups.
Proceedings of the International Conference on Web Search and Web Data Mining, 2008

Sampling algorithms and coresets for ℓ<sub><i>p</i></sub> regression.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Pig latin: a not-so-foreign language for data processing.
Proceedings of the ACM SIGMOD International Conference on Management of Data, 2008

Corrigendum to "efficient similarity search and classification via rank aggregation" by Ronald Fagin, Ravi Kumar and D. Sivakumar (proc. SIGMOD'03).
Proceedings of the ACM SIGMOD International Conference on Management of Data, 2008

Optimizing query rewrites for keyword-based advertising.
Proceedings of the Proceedings 9th ACM Conference on Electronic Commerce (EC-2008), 2008

Approximation algorithms for co-clustering.
Proceedings of the Twenty-Seventh ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2008

Mortal Multi-Armed Bandits.
Proceedings of the Advances in Neural Information Processing Systems 21, 2008

Microscopic evolution of social networks.
Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2008

Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2008

De-duping URLs via rewrite rules.
Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2008

Generating succinct titles for web URLs.
Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2008

Influence and correlation in social networks.
Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2008

Efficient Discovery of Authoritative Resources.
Proceedings of the 24th International Conference on Data Engineering, 2008

Vanity fair: privacy in querylog bundles.
Proceedings of the 17th ACM Conference on Information and Knowledge Management, 2008

2007
Visualizing tags over time.
ACM Trans. Web, 2007

Finding (Short) Paths in Social Networks.
Internet Math., 2007

Sampling Algorithms and Coresets for Lp Regression
CoRR, 2007

On anonymizing query logs via token-based hashing.
Proceedings of the 16th International Conference on World Wide Web, 2007

Anchor-based proximity measures.
Proceedings of the 16th International Conference on World Wide Web, 2007

The discoverability of the web.
Proceedings of the 16th International Conference on World Wide Web, 2007

Page-level template detection via isotonic smoothing.
Proceedings of the 16th International Conference on World Wide Web, 2007

On Completing Latin Squares.
Proceedings of the STACS 2007, 2007

Estimating the sortedness of a data stream.
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

On the robustness of relevance measures with incomplete judgments.
Proceedings of the SIGIR 2007: Proceedings of the 30th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, 2007

On threshold behavior in query incentive networks.
Proceedings of the Proceedings 8th ACM Conference on Electronic Commerce (EC-2007), 2007

Communication Lower Bounds Via the Chromatic Number.
Proceedings of the FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science, 2007

"I know what you did last summer": query logs and user privacy.
Proceedings of the Sixteenth ACM Conference on Information and Knowledge Management, 2007

On Finding Frequent Elements in a Data Stream.
Proceedings of the Approximation, 2007

2006
Core algorithms in the CLEVER system.
ACM Trans. Internet Techn., 2006

Preface.
Theor. Comput. Sci., 2006

Comparing Partial Rankings.
SIAM J. Discret. Math., 2006

Content, Metadata, and Behavioral Information: Directions for Yahoo! Research.
IEEE Data Eng. Bull., 2006

On the Hardness of Approximating Multicut and Sparsest-Cut.
Comput. Complex., 2006

Searching with context.
Proceedings of the 15th international conference on World Wide Web, 2006

Programmable clustering.
Proceedings of the Twenty-Fifth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2006

Hierarchical topic segmentation of websites.
Proceedings of the Twelfth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2006

Structure and evolution of online social networks.
Proceedings of the Twelfth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2006

Evolutionary clustering.
Proceedings of the Twelfth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2006

Navigating Low-Dimensional and Hierarchical Population Networks.
Proceedings of the Algorithms, 2006

Estimating corpus size via queries.
Proceedings of the 2006 ACM CIKM International Conference on Information and Knowledge Management, 2006

2005
On the Bursty Evolution of Blogspace.
World Wide Web, 2005

The Complexity of Approximating the Entropy.
SIAM J. Comput., 2005

Geographic routing in social networks.
Proc. Natl. Acad. Sci. USA, 2005

Discovering Large Dense Subgraphs in Massive Graphs.
Proceedings of the 31st International Conference on Very Large Data Bases, Trondheim, Norway, August 30, 2005

Efficient Implementation of Large-Scale Multi-Structural Databases.
Proceedings of the 31st International Conference on Very Large Data Bases, Trondheim, Norway, August 30, 2005

Multi-structural databases.
Proceedings of the Twenty-fourth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2005

Unweaving a web of documents.
Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2005

The predictive power of online chatter.
Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2005

Variable latent semantic indexing.
Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2005

2004
Minimizing Wirelength in Zero and Bounded Skew Clock Trees.
SIAM J. Discret. Math., 2004

Cell-probe lower bounds for the partial match problem.
J. Comput. Syst. Sci., 2004

An information statistics approach to data stream and communication complexity.
J. Comput. Syst. Sci., 2004

Fast approximate probabilistically checkable proofs.
Inf. Comput., 2004

Structure and evolution of blogspace.
Commun. ACM, 2004

Propagation of trust and distrust.
Proceedings of the 13th international conference on World Wide Web, 2004

Sic transit gloria telae: towards an understanding of the web's decay.
Proceedings of the 13th international conference on World Wide Web, 2004

Sublinear algorithms for testing monotone and unimodal distributions.
Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

An improved data stream algorithm for frequency moments.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Comparing and Aggregating Rankings with Ties.
Proceedings of the Twenty-third ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2004

A graph-theoretic approach to extract storylines from search results.
Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2004

Approximating Edit Distance Efficiently.
Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

The Sketching Complexity of Pattern Matching.
Proceedings of the Approximation, 2004

2003
Algorithms column: sublinear time algorithms.
SIGACT News, 2003

On Polynomial-Factor Approximations to the Shortest Lattice Vector Length.
SIAM J. Discret. Math., 2003

Comparing Top k Lists.
SIAM J. Discret. Math., 2003

Internet Math., 2003

Automatic Hierarchical Color Image Classification.
EURASIP J. Adv. Signal Process., 2003

Searching the workplace web.
Proceedings of the Twelfth International World Wide Web Conference, 2003

Two applications of information complexity.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

A note on the set systems used for broadcast encryption.
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Efficient similarity search and classification via rank aggregation.
Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data, 2003

2002
Self-similarity in the web.
ACM Trans. Internet Techn., 2002

The Web and Social Networks.
Computer, 2002

Approximate counting of inversions in a data stream.
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

Reductions in streaming algorithms, with an application to counting triangles in graphs.
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

Counting Distinct Elements in a Data Stream.
Proceedings of the Randomization and Approximation Techniques, 6th International Workshop, 2002

Information Theory Methods in Communication Complexity.
Proceedings of the 17th Annual IEEE Conference on Computational Complexity, 2002

Sampling Short Lattice Vectors and the Closest Lattice Vector Problem.
Proceedings of the 17th Annual IEEE Conference on Computational Complexity, 2002

2001
On the unique shortest lattice vector problem.
Theor. Comput. Sci., 2001

Checking Approximate Computations of Polynomials and Functional Equations.
SIAM J. Comput., 2001

Recommendation Systems: A Probabilistic Analysis.
J. Comput. Syst. Sci., 2001

Rank aggregation methods for the Web.
Proceedings of the Tenth International World Wide Web Conference, 2001

On Semi-Automated Web Taxonomy Construction.
Proceedings of the Fourth International Workshop on the Web and Databases, 2001

Sampling algorithms: lower bounds and applications.
Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

A sieve algorithm for the shortest lattice vector problem.
Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

On polynomial approximation to the shortest lattice vector length.
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

Selective private function evaluation with applications to private statistics.
Proceedings of the Twentieth Annual ACM Symposium on Principles of Distributed Computing, 2001

Testing Random Variables for Independence and Identity.
Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

An Overview of the Sieve Algorithm for the Shortest Lattice Vector Problem.
Proceedings of the Cryptography and Lattices, International Conference, 2001

2000
Self-Testing without the Generator Bottleneck.
SIAM J. Comput., 2000

Spot-Checkers.
J. Comput. Syst. Sci., 2000

Graph structure in the Web.
Comput. Networks, 2000

The Web as a Graph.
Proceedings of the Nineteenth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2000

Random graph models for the web graph.
Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

Combinatorial feature selection problems.
Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

1999
Spatial Color Indexing and Applications.
Int. J. Comput. Vis., 1999

Computer, 1999

Trawling the Web for Emerging Cyber-Communities.
Comput. Networks, 1999

Approximating Latin Square Extensions.
Algorithmica, 1999

Topic Distillation and Spectral Filtering.
Artif. Intell. Rev., 1999

Extracting Large-Scale Knowledge Bases from the Web.
Proceedings of the VLDB'99, 1999

Fast Approximate PCPs.
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

On targeting Markov segments.
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Roundness Estimation via Random Sampling.
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

A Note on the Limits of Collusion-Resistant Watermarks.
Proceedings of the Advances in Cryptology, 1999

Coding Constructions for Blacklisting Problems without Computational Assumptions.
Proceedings of the Advances in Cryptology, 1999

The Web as a Graph: Measurements, Models, and Methods.
Proceedings of the Computing and Combinatorics, 5th Annual International Conference, 1999

A Note on the Shortest Lattice Vector Problem.
Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 1999

Proofs, Codes, and Polynomial-Time Reducibilities.
Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 1999

1998
An Automatic Hierarchical Image Classification Scheme.
Proceedings of the 6th ACM International Conference on Multimedia '98, 1998

Spatial Color Indexing and Applications.
Proceedings of the Sixth International Conference on Computer Vision (ICCV-98), 1998

1997
A Note on Optical Routing on Trees.
Inf. Process. Lett., 1997

Combining Supervised Learning with Color Correlograms for Content-Based Image Retrieval.
Proceedings of the Fifth ACM International Conference on Multimedia '97, 1997

Faster Algorithms for Optical Switch Configuration.
Proceedings of the 1997 IEEE International Conference on Communications: Towards the Knowledge Millennium, 1997

Checking Properties of Polynomials (Extended Abstract).
Proceedings of the Automata, Languages and Programming, 24th International Colloquium, 1997

Image Indexing Using Color Correlograms.
Proceedings of the 1997 Conference on Computer Vision and Pattern Recognition (CVPR '97), 1997

Learning Distributions from Random Walks.
Proceedings of the Tenth Annual Conference on Computational Learning Theory, 1997

1996
Scalability Study of the KSR-1.
Parallel Comput., 1996

Efficient Self-Testing/Self-Correction of Linear Recurrences.
Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

Approximate Checking of Polynomials and Functional Equations (extended abstract).
Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

1995
On Self-Testing without the Generator Bottleneck.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1995

On Learning Bounded-Width Branching Programs.
Proceedings of the Eigth Annual Conference on Computational Learning Theory, 1995