Moses Charikar

Chirag Pabbaraju

Kirankumar Shiragur

CoRR, 2024

Fully Dynamic Correlation Clustering: Breaking 3-Approximation.

[BibT_eX]

[DOI]

CoRR, 2024

Breaking the Metric Voting Distortion Barrier.

[BibT_eX]

[DOI]

Kangning Wang

Prasanna Ramakrishnan

Hongxun Wu

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

A Quasi-Monte Carlo Data Structure for Smooth Kernel Evaluations.

[BibT_eX]

[DOI]

Michael Kapralov

Erik Waingarten

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Improved Approximations for Ultrametric Violation Distance.

[BibT_eX]

[DOI]

Ruiquan Gao

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Dynamic Data Layout Optimization with Worst-Case Guarantees.

[BibT_eX]

[DOI]

Proceedings of the 40th IEEE International Conference on Data Engineering, 2024

2023

Average-Case Dimensionality Reduction in 𝓁1: Tree Ising Models.

[BibT_eX]

[DOI]

Spencer Compton

Chirag Pabbaraju

CoRR, 2023

A Characterization of List Learnability.

[BibT_eX]

[DOI]

Chirag Pabbaraju

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Single-Pass Streaming Algorithms for Correlation Clustering.

[BibT_eX]

[DOI]

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Distortion in metric matching with ordinal preferences.

[BibT_eX]

[DOI]

Nima Anari

Prasanna Ramakrishnan

Proceedings of the 24th ACM Conference on Economics and Computation, 2023

Simple, Scalable and Effective Clustering via One-Dimensional Projections.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Fast Algorithms for a New Relaxation of Optimal Transport.

[BibT_eX]

[DOI]

Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

2022

Local Density Estimation in High Dimensions.

[BibT_eX]

[DOI]

Xian Wu

Vishnu Natchu

Math. Oper. Res., November, 2022

On the Complexity of Sampling Redistricting Plans.

[BibT_eX]

[DOI]

CoRR, 2022

The Johnson-Lindenstrauss Lemma for Clustering and Subspace Approximation: From Coresets to Dimension Reduction.

[BibT_eX]

[DOI]

Erik Waingarten

CoRR, 2022

Metric Distortion Bounds for Randomized Social Choice.

[BibT_eX]

[DOI]

Prasanna Ramakrishnan

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Near-Optimal Explainable k-Means for All Dimensions.

[BibT_eX]

[DOI]

Lunjia Hu

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

On the Efficient Implementation of High Accuracy Optimality of Profile Maximum Likelihood.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Polylogarithmic Sketches for Clustering.

[BibT_eX]

[DOI]

Erik Waingarten

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Almost 3-Approximate Correlation Clustering in Constant Rounds.

[BibT_eX]

[DOI]

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

2021

Improved Algorithms for Edge Colouring in the W-Streaming Model.

[BibT_eX]

[DOI]

Paul Liu

Proceedings of the 4th Symposium on Simplicity in Algorithms, 2021

Brief Announcement: A Randomness-efficient Massively Parallel Algorithm for Connectivity.

[BibT_eX]

[DOI]

Weiyun Ma

Li-Yang Tan

Proceedings of the PODC '21: ACM Symposium on Principles of Distributed Computing, 2021

A Model for Ant Trail Formation and its Convergence Properties (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

Multiway Online Correlated Selection.

[BibT_eX]

[DOI]

Guy Blanc

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

The Bethe and Sinkhorn Permanents of Low Rank Matrices and Implications for Profile Maximum Likelihood.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2021

Approximation Algorithms for Orthogonal Non-negative Matrix Factorization.

[BibT_eX]

[DOI]

Lunjia Hu

Proceedings of the 24th International Conference on Artificial Intelligence and Statistics, 2021

2020

CoopStore: Optimizing Precomputed Summaries for Aggregation.

[BibT_eX]

[DOI]

Edward Gan

Peter Bailis

Proc. VLDB Endow., 2020

The one-way communication complexity of dynamic time warping distance.

[BibT_eX]

[DOI]

J. Comput. Geom., 2020

A Model for Ant Trail Formation and its Convergence Properties.

[BibT_eX]

[DOI]

CoRR, 2020

Nearest Neighbor Search for Hyperbolic Embeddings.

[BibT_eX]

[DOI]

Xian Wu

CoRR, 2020

A Simple Sublinear Algorithm for Gap Edit Distance.

[BibT_eX]

[DOI]

Joshua Brakensiek

Aviad Rubinstein

CoRR, 2020

Storyboard: Optimizing Precomputed Summaries for Aggregation.

[BibT_eX]

[DOI]

Edward Gan

Peter Bailis

CoRR, 2020

New lower bounds for Massively Parallel Computation from query complexity.

[BibT_eX]

[DOI]

Weiyun Ma

Li-Yang Tan

CoRR, 2020

Retrieving Top Weighted Triangles in Graphs.

[BibT_eX]

[DOI]

Proceedings of the WSDM '20: The Thirteenth ACM International Conference on Web Search and Data Mining, 2020

Unconditional Lower Bounds for Adaptive Massively Parallel Computation.

[BibT_eX]

[DOI]

Weiyun Ma

Li-Yang Tan

Proceedings of the SPAA '20: 32nd ACM Symposium on Parallelism in Algorithms and Architectures, 2020

Adaptive Discrete Phase Retrieval.

[BibT_eX]

[DOI]

Xian Wu

Yinyu Ye

Proceedings of the 3rd Symposium on Simplicity in Algorithms, 2020

Institutions Share Successes, Failures, and Advice in Moving the Diversity Needle.

[BibT_eX]

[DOI]

Proceedings of the 51st ACM Technical Symposium on Computer Science Education, 2020

Instance Based Approximations to Profile Maximum Likelihood.

[BibT_eX]

[DOI]

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

Kernel Density Estimation through Density Constrained Near Neighbor Search.

[BibT_eX]

[DOI]

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

2019

Sampling Methods for Counting Temporal Motifs.

[BibT_eX]

[DOI]

Paul Liu

Austin R. Benson

Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining, 2019

Efficient profile maximum likelihood for universal symmetric property estimation.

[BibT_eX]

[DOI]

Kirankumar Shiragur

Aaron Sidford

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Hierarchical Clustering better than Average-Linkage.

[BibT_eX]

[DOI]

Vaggos Chatziafratis

Rad Niazadeh

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

A General Framework for Symmetric Property Estimation.

[BibT_eX]

[DOI]

Kirankumar Shiragur

Aaron Sidford

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Rehashing Kernel Evaluation in High Dimensions.

[BibT_eX]

[DOI]

Philip Alexander Levis

Proceedings of the 36th International Conference on Machine Learning, 2019

Multi-resolution Hashing for Fast Pairwise Summations.

[BibT_eX]

[DOI]

Paris Siminelakis

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

The One-Way Communication Complexity of Dynamic Time Warping Distance.

[BibT_eX]

[DOI]

Proceedings of the 35th International Symposium on Computational Geometry, 2019

Hierarchical Clustering for Euclidean Data.

[BibT_eX]

[DOI]

Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, 2019

Recovery Guarantees For Quadratic Tensors With Sparse Observations.

[BibT_eX]

[DOI]

Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, 2019

2018

Recovery Guarantees for Quadratic Tensors with Limited Observations.

[BibT_eX]

[DOI]

CoRR, 2018

A sampling framework for counting temporal motifs.

[BibT_eX]

[DOI]

Paul Liu

Austin R. Benson

CoRR, 2018

On Finding Dense Common Subgraphs.

[BibT_eX]

[DOI]

Yonatan Naamad

Jimmy Wu

CoRR, 2018

Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers.

[BibT_eX]

[DOI]

Jacob Steinhardt

Gregory Valiant

Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

Hierarchical Clustering with Structural Constraints.

[BibT_eX]

[DOI]

Vaggos Chatziafratis

Rad Niazadeh

Proceedings of the 35th International Conference on Machine Learning, 2018

Fully Dynamic Almost-Maximal Matching: Breaking the Polynomial Worst-Case Time Barrier.

[BibT_eX]

[DOI]

Shay Solomon

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

On Estimating Edit Distance: Alignment, Dimension Reduction, and Embeddings.

[BibT_eX]

[DOI]

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Efficient Density Evaluation for Smooth Kernels.

[BibT_eX]

[DOI]

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

Multi-commodity Flow with In-Network Processing.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Aspects of Cloud Computing - 4th International Symposium, 2018

2017

Intelligent Probing for Locality Sensitive Hashing: Multi-Probe LSH and Beyond.

[BibT_eX]

[DOI]

Proc. VLDB Endow., 2017

Fully Dynamic Almost-Maximal Matching: Breaking the Polynomial Barrier for Worst-Case Time Bounds.

[BibT_eX]

[DOI]

Shay Solomon

CoRR, 2017

Learning from untrusted data.

[BibT_eX]

[DOI]

Jacob Steinhardt

Gregory Valiant

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Approximate Hierarchical Clustering via Sparsest Cut and Spreading Metrics.

[BibT_eX]

[DOI]

Vaggos Chatziafratis

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Local Guarantees in Graph Cuts and Clustering.

[BibT_eX]

[DOI]

Neha Gupta

Roy Schwartz

Proceedings of the Integer Programming and Combinatorial Optimization, 2017

Hashing-Based-Estimators for Kernel Density in High Dimensions.

[BibT_eX]

[DOI]

Paris Siminelakis

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics.

[BibT_eX]

[DOI]

Yuchen Zhang

Percy Liang

Proceedings of the 30th Conference on Learning Theory, 2017

Min-Cost Bipartite Perfect Matching with Delays.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2017

2016

Avoiding Imposters and Delinquents: Adversarial Crowdsourcing and Peer Prediction.

[BibT_eX]

[DOI]

Jacob Steinhardt

Gregory Valiant

Proceedings of the Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, 2016

Spectral Embedding of k-Cliques, Graph Partitioning and k-Means.

[BibT_eX]

[DOI]

Pranjal Awasthi

Ali Kemal Sinop

Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, 2016

On Approximating Target Set Selection.

[BibT_eX]

[DOI]

Yonatan Naamad

Anthony Wirth

Proceedings of the Approximation, 2016

Top-k Frequent Item Maintenance over Streams.

[BibT_eX]

[DOI]

Proceedings of the Data Stream Management - Processing High-Speed Data Streams, 2016

2015

Relax, No Need to Round: Integrality of Clustering Formulations.

[BibT_eX]

[DOI]

Pranjal Awasthi

Afonso S. Bandeira

Soledad Villar

Rachel A. Ward

Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, 2015

Bypassing Worst Case Analysis: Tensor Decomposition and Clustering (Invited Talk).

[BibT_eX]

[DOI]

Moses Samson Charikar

Proceedings of the 35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science, 2015

The Hardness of Approximation of Euclidean k-Means.

[BibT_eX]

[DOI]

Pranjal Awasthi

Ali Kemal Sinop

Proceedings of the 31st International Symposium on Computational Geometry, 2015

Label optimal regret bounds for online local learning.

[BibT_eX]

[DOI]

Proceedings of The 28th Conference on Learning Theory, 2015

2014

Smoothed analysis of tensor decompositions.

[BibT_eX]

[DOI]

Ankur Moitra

Proceedings of the Symposium on Theory of Computing, 2014

Better Algorithms and Hardness for Broadcast Scheduling via a Discrepancy Approach.

[BibT_eX]

[DOI]

Nikhil Bansal

Shi Li

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Multireference alignment using semidefinite programming.

[BibT_eX]

[DOI]

Proceedings of the Innovations in Theoretical Computer Science, 2014

Online Bipartite Matching with Decomposable Weights.

[BibT_eX]

[DOI]

Monika Henzinger

Huy L. Nguyen

Proceedings of the Algorithms - ESA 2014, 2014

Uniqueness of Tensor Decompositions with Applications to Polynomial Identifiability.

[BibT_eX]

[DOI]

Proceedings of The 27th Conference on Learning Theory, 2014

Open Problem: Tensor Decompositions: Algorithms up to the Uniqueness Threshold?

[BibT_eX]

[DOI]

Ankur Moitra

Proceedings of The 27th Conference on Learning Theory, 2014

2012

Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph.

[BibT_eX]

[DOI]

Yuan Zhou

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

High-confidence near-duplicate image detection.

[BibT_eX]

[DOI]

Proceedings of the International Conference on Multimedia Retrieval, 2012

A Dependent LP-Rounding Approach for the k-Median Problem.

[BibT_eX]

[DOI]

Shi Li

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

On Quadratic Programming with a Ratio Objective.

[BibT_eX]

[DOI]

Rajsekar Manokaran

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

2011

Beating the Random Ordering Is Hard: Every Ordering CSP Is Approximation Resistant.

[BibT_eX]

[DOI]

SIAM J. Comput., 2011

Fitting Tree Metrics: Hierarchical Clustering and Phylogeny.

[BibT_eX]

[DOI]

Nir Ailon

SIAM J. Comput., 2011

Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph

[BibT_eX]

[DOI]

Yuan Zhou

CoRR, 2011

Improved Approximation Algorithms for Label Cover Problems.

[BibT_eX]

[DOI]

MohammadTaghi Hajiaghayi

Algorithmica, 2011

Efficient k-nearest neighbor graph construction for generic similarity measures.

[BibT_eX]

[DOI]

Wei Dong

Kai Li

Proceedings of the 20th International Conference on World Wide Web, 2011

Tight Hardness Results for Minimizing Discrepancy.

[BibT_eX]

[DOI]

Alantha Newman

Aleksandar Nikolov

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Near Linear Lower Bound for Dimension Reduction in L1.

[BibT_eX]

[DOI]

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

2010

Local Global Tradeoffs in Metric Embeddings.

[BibT_eX]

[DOI]

SIAM J. Comput., 2010

Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes)

[BibT_eX]

[DOI]

CoRR, 2010

Detecting High Log-Densities -- an O(n^1/4) Approximation for Densest k-Subgraph

[BibT_eX]

[DOI]

CoRR, 2010

l22 Spreading Metrics for Vertex Ordering Problems.

[BibT_eX]

[DOI]

Mohammad Taghi Hajiaghayi

Satish Rao

Algorithmica, 2010

Detecting high log-densities: an O(n1/4) approximation for densest k-subgraph.

[BibT_eX]

[DOI]

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Vertex Sparsifiers and Abstract Rounding Algorithms.

[BibT_eX]

[DOI]

Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

2009

Near-optimal algorithms for maximum constraint satisfaction problems.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2009

Integrality gaps for Sherali-Adams relaxations.

[BibT_eX]

[DOI]

Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

MaxMin allocation via degree lower-bounded arborescences.

[BibT_eX]

[DOI]

MohammadHossein Bateni

Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

Every Permutation CSP of arity 3 is Approximation Resistant.

[BibT_eX]

[DOI]

Rajsekar Manokaran

Proceedings of the 24th Annual IEEE Conference on Computational Complexity, 2009

2008

Aggregating inconsistent information: Ranking and clustering.

[BibT_eX]

[DOI]

Nir Ailon

Alantha Newman

J. ACM, 2008

Online multicast with egalitarian cost sharing.

[BibT_eX]

[DOI]

Proceedings of the SPAA 2008: Proceedings of the 20th Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2008

Asymmetric distance estimation with sketches for similarity search in high-dimensional spaces.

[BibT_eX]

[DOI]

Wei Dong

Kai Li

Proceedings of the 31st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, 2008

Efficiently matching sets of features with random histograms.

[BibT_eX]

[DOI]

Proceedings of the 16th International Conference on Multimedia 2008, 2008

Modeling LSH for performance tuning.

[BibT_eX]

[DOI]

Proceedings of the 17th ACM Conference on Information and Knowledge Management, 2008

2007

On the Advantage over Random for Maximum Acyclic Subgraph.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2007

Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search .

[BibT_eX]

[DOI]

Proceedings of the 33rd International Conference on Very Large Data Bases, 2007

Improved approximation for directed cut problems.

[BibT_eX]

[DOI]

Amit Agarwal

Noga Alon

Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

A divide and conquer algorithm for d-dimensional arrangement.

[BibT_eX]

[DOI]

Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Sizing sketches: a rank-based analysis for similarity search.

[BibT_eX]

[DOI]

Proceedings of the 2007 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, 2007

Filtering Image Spam with Near-Duplicate Detection.

[BibT_eX]

[DOI]

Proceedings of the CEAS 2007, 2007

2006

Embedding the Ulam metric into l1.

[BibT_eX]

[DOI]

Robert Krauthgamer

Theory Comput., 2006

On the Integrality Ratio for the Asymmetric Traveling Salesman Problem.

[BibT_eX]

[DOI]

Michel X. Goemans

Math. Oper. Res., 2006

Guest editor's foreword.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2006

Note on MAX 2SAT.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2006

Approximation Algorithm for the Max k-CSP Problem.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2006

Near-optimal algorithms for unique games.

[BibT_eX]

[DOI]

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Directed metrics and directed graph partitioning problems.

[BibT_eX]

[DOI]

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

A robust maximum completion time measure for scheduling.

[BibT_eX]

[DOI]

Samir Khuller

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

l22 spreading metrics for vertex ordering problems.

[BibT_eX]

[DOI]

Mohammad Taghi Hajiaghayi

Satish Rao

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Efficient filtering with sketches in the ferret toolkit.

[BibT_eX]

[DOI]

Proceedings of the 8th ACM SIGMM International Workshop on Multimedia Information Retrieval, 2006

Ferret: a toolkit for content-based similarity search of feature-rich data.

[BibT_eX]

[DOI]

Proceedings of the 2006 EuroSys Conference, Leuven, Belgium, April 18-21, 2006, 2006

2005

The smallest grammar problem.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2005

Improved Combinatorial Algorithms for Facility Location Problems.

[BibT_eX]

[DOI]

Sudipto Guha

SIAM J. Comput., 2005

Clustering with qualitative information.

[BibT_eX]

[DOI]

Anthony Wirth

J. Comput. Syst. Sci., 2005

On the impossibility of dimension reduction in l1.

[BibT_eX]

[DOI]

Bo Brinkman

J. ACM, 2005

On non-uniform multicommodity buy-at-bulk network design.

[BibT_eX]

[DOI]

Adriana Karagiozova

Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

O(sqrt(log n)) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems.

[BibT_eX]

[DOI]

Amit Agarwal

Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

A tight threshold for metric Ramsey phenomena.

[BibT_eX]

[DOI]

Adriana Karagiozova

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Approximating the average response time in broadcast scheduling.

[BibT_eX]

[DOI]

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Sampling Bounds for Stochastic Optimization.

[BibT_eX]

[DOI]

Chandra Chekuri

Martin Pál

Proceedings of the Approximation, 2005

2004

Resource optimization in QoS multicast routing of real-time multimedia.

[BibT_eX]

[DOI]

Joseph Naor

Baruch Schieber

IEEE/ACM Trans. Netw., 2004

Finding frequent items in data streams.

[BibT_eX]

[DOI]

Kevin C. Chen

Martin Farach-Colton

Theor. Comput. Sci., 2004

Minimizing Wirelength in Zero and Bounded Skew Clock Trees.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2004

Incremental Clustering and Dynamic Information Retrieval.

[BibT_eX]

[DOI]

SIAM J. Comput., 2004

Clustering to minimize the sum of cluster diameters.

[BibT_eX]

[DOI]

Rina Panigrahy

J. Comput. Syst. Sci., 2004

On the advantage of network coding for improving network throughput.

[BibT_eX]

[DOI]

Amit Agarwal

Proceedings of the 2004 IEEE Information Theory Workshop, 2004

Maximizing Quadratic Programs: Extending Grothendieck's Inequality.

[BibT_eX]

[DOI]

Anthony Wirth

Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

On the Integrality Ratio for Asymmetric TSP.

[BibT_eX]

[DOI]

Michel X. Goemans

Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

Image similarity search with compact data structures.

[BibT_eX]

[DOI]

Qin Lv

Kai Li

Proceedings of the 2004 ACM CIKM International Conference on Information and Knowledge Management, 2004

2003

A derandomization using min-wise independent permutations.

[BibT_eX]

[DOI]

Andrei Z. Broder

Michael Mitzenmacher

J. Discrete Algorithms, 2003

Better streaming algorithms for clustering problems.

[BibT_eX]

[DOI]

Liadan O'Callaghan

Rina Panigrahy

Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

2002

A Constant-Factor Approximation Algorithm for the k-Median Problem.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2002

Query Strategies for Priced Information.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2002

Approximating the smallest grammar: Kolmogorov complexity in natural models.

[BibT_eX]

[DOI]

Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

Similarity estimation techniques from rounding algorithms.

[BibT_eX]

[DOI]

Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

On semidefinite programming relaxations for graph coloring and vertex cover.

[BibT_eX]

[DOI]

Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

New Algorithms for Subset Query, Partial Match, Orthogonal Range Searching, and Related Problems.

[BibT_eX]

[DOI]

Piotr Indyk

Rina Panigrahy

Proceedings of the Automata, Languages and Programming, 29th International Colloquium, 2002

Dimension Reduction in the \ell _1 Norm.

[BibT_eX]

[DOI]

Amit Sahai

Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002

2001

On page migration and other relaxed task systems.

[BibT_eX]

[DOI]

Yair Bartal

Piotr Indyk

Theor. Comput. Sci., 2001

Algorithms for Capacitated Vehicle Routing.

[BibT_eX]

[DOI]

Samir Khuller

Balaji Raghavachari

SIAM J. Comput., 2001

Delayed Information and Action in On-Line Algorithms.

[BibT_eX]

[DOI]

Susanne Albers

Michael Mitzenmacher

Inf. Comput., 2001

Approximating min-sum k-clustering in metric spaces.

[BibT_eX]

[DOI]

Yair Bartal

Danny Raz

Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

Algorithms for facility location problems with outliers.

[BibT_eX]

[DOI]

Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

2000

Algorithms for clustering problems.

[BibT_eX]

[DOI]

PhD thesis, 2000

Min-Wise Independent Permutations.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2000

On-Line Load Balancing for Related Machines

[BibT_eX]

[DOI]

Piotr Berman

Marek Karpinski

Electron. Colloquium Comput. Complex., 2000

Query strategies for priced information (extended abstract).

[BibT_eX]

[DOI]

Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Towards Estimation Error Guarantees for Distinct Values.

[BibT_eX]

[DOI]

Proceedings of the Nineteenth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2000

Minimum Outage Transmission over Fading Channels with Delay Constraint.

[BibT_eX]

[DOI]

Rohit Negi

John M. Cioffi

Proceedings of the 2000 IEEE International Conference on Communications: Global Convergence Through Communications, 2000

Combinatorial feature selection problems.

[BibT_eX]

[DOI]

Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

Greedy approximation algorithms for finding dense components in a graph.

[BibT_eX]

[DOI]

Proceedings of the Approximation Algorithms for Combinatorial Optimization, 2000

1999

Approximation Algorithms for Directed Steiner Problems.

[BibT_eX]

[DOI]

J. Algorithms, 1999

On targeting Markov segments.

[BibT_eX]

[DOI]

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

A Constant-Factor Approximation Algorithm for the k-Median Problem (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Improved Combinatorial Algorithms for the Facility Location and k-Median Problems.

[BibT_eX]

[DOI]

Sudipto Guha

Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

1998

Rounding via Trees: Deterministic Approximation Algorithms for Group Steiner Trees and k-Median.

[BibT_eX]

[DOI]

Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

Min-Wise Independent Permutations (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

The Dynamic Servers Problem.

[BibT_eX]

[DOI]

Dan Halperin

Rajeev Motwani

Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998

The Finite Capacity Dial-A-Ride Problem.

[BibT_eX]

[DOI]