Moses Charikar

According to our database1, Moses Charikar authored at least 127 papers between 1997 and 2019.

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

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2019
Sampling Methods for Counting Temporal Motifs.
Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining, 2019

Efficient profile maximum likelihood for universal symmetric property estimation.
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Hierarchical Clustering better than Average-Linkage.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Rehashing Kernel Evaluation in High Dimensions.
Proceedings of the 36th International Conference on Machine Learning, 2019

The One-Way Communication Complexity of Dynamic Time Warping Distance.
Proceedings of the 35th International Symposium on Computational Geometry, 2019

Hierarchical Clustering for Euclidean Data.
Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, 2019

Recovery Guarantees For Quadratic Tensors With Sparse Observations.
Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, 2019

2018
Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers.
Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

Local Density Estimation in High Dimensions.
Proceedings of the 35th International Conference on Machine Learning, 2018

Hierarchical Clustering with Structural Constraints.
Proceedings of the 35th International Conference on Machine Learning, 2018

Fully Dynamic Almost-Maximal Matching: Breaking the Polynomial Worst-Case Time Barrier.
Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

On Estimating Edit Distance: Alignment, Dimension Reduction, and Embeddings.
Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Efficient Density Evaluation for Smooth Kernels.
Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

Multi-commodity Flow with In-Network Processing.
Proceedings of the Algorithmic Aspects of Cloud Computing - 4th International Symposium, 2018

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

Learning from untrusted data.
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Approximate Hierarchical Clustering via Sparsest Cut and Spreading Metrics.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Local Guarantees in Graph Cuts and Clustering.
Proceedings of the Integer Programming and Combinatorial Optimization, 2017

Hashing-Based-Estimators for Kernel Density in High Dimensions.
Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics.
Proceedings of the 30th Conference on Learning Theory, 2017

Min-Cost Bipartite Perfect Matching with Delays.
Proceedings of the Approximation, 2017

2016
Avoiding Imposters and Delinquents: Adversarial Crowdsourcing and Peer Prediction.
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.
Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, 2016

On Approximating Target Set Selection.
Proceedings of the Approximation, 2016

Top-k Frequent Item Maintenance over Streams.
Proceedings of the Data Stream Management - Processing High-Speed Data Streams, 2016

2015
Relax, No Need to Round: Integrality of Clustering Formulations.
Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, 2015

Bypassing Worst Case Analysis: Tensor Decomposition and Clustering (Invited Talk).
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.
Proceedings of the 31st International Symposium on Computational Geometry, 2015

Label optimal regret bounds for online local learning.
Proceedings of The 28th Conference on Learning Theory, 2015

2014
Smoothed analysis of tensor decompositions.
Proceedings of the Symposium on Theory of Computing, 2014

Better Algorithms and Hardness for Broadcast Scheduling via a Discrepancy Approach.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Multireference alignment using semidefinite programming.
Proceedings of the Innovations in Theoretical Computer Science, 2014

Online Bipartite Matching with Decomposable Weights.
Proceedings of the Algorithms - ESA 2014, 2014

Uniqueness of Tensor Decompositions with Applications to Polynomial Identifiability.
Proceedings of The 27th Conference on Learning Theory, 2014

Open Problem: Tensor Decompositions: Algorithms up to the Uniqueness Threshold?
Proceedings of The 27th Conference on Learning Theory, 2014

2012
Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

High-confidence near-duplicate image detection.
Proceedings of the International Conference on Multimedia Retrieval, 2012

A Dependent LP-Rounding Approach for the k-Median Problem.
Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

On Quadratic Programming with a Ratio Objective.
Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

2011
Beating the Random Ordering Is Hard: Every Ordering CSP Is Approximation Resistant.
SIAM J. Comput., 2011

Beating the Random Ordering is Hard: Every ordering CSP is approximation resistant.
Electronic Colloquium on Computational Complexity (ECCC), 2011

Efficient k-nearest neighbor graph construction for generic similarity measures.
Proceedings of the 20th International Conference on World Wide Web, 2011

Tight Hardness Results for Minimizing Discrepancy.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Near Linear Lower Bound for Dimension Reduction in L1.
Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

2010
l22 Spreading Metrics for Vertex Ordering Problems.
Algorithmica, 2010

Detecting high log-densities: an O(n1/4) approximation for densest k-subgraph.
Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Vertex Sparsifiers and Abstract Rounding Algorithms.
Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

2009
Integrality gaps for Sherali-Adams relaxations.
Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

MaxMin allocation via degree lower-bounded arborescences.
Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

Improved Approximation Algorithms for Label Cover Problems.
Proceedings of the Algorithms, 2009

Every Permutation CSP of arity 3 is Approximation Resistant.
Proceedings of the 24th Annual IEEE Conference on Computational Complexity, 2009

2008
Online multicast with egalitarian cost sharing.
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.
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.
Proceedings of the 16th International Conference on Multimedia 2008, 2008

Modeling LSH for performance tuning.
Proceedings of the 17th ACM Conference on Information and Knowledge Management, 2008

2007
Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search .
Proceedings of the 33rd International Conference on Very Large Data Bases, 2007

Improved approximation for directed cut problems.
Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

A divide and conquer algorithm for d-dimensional arrangement.
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Near-optimal algorithms for maximum constraint satisfaction problems.
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Sizing sketches: a rank-based analysis for similarity search.
Proceedings of the 2007 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, 2007

Local Global Tradeoffs in Metric Embeddings.
Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 2007

On the Advantage over Random for Maximum Acyclic Subgraph.
Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 2007

Filtering Image Spam with Near-Duplicate Detection.
Proceedings of the CEAS 2007, 2007

2006
Embedding the Ulam metric into l1.
Theory of Computing, 2006

On the Integrality Ratio for the Asymmetric Traveling Salesman Problem.
Math. Oper. Res., 2006

Guest editor's foreword.
J. Comput. Syst. Sci., 2006

Note on MAX 2SAT.
Electronic Colloquium on Computational Complexity (ECCC), 2006

Approximation Algorithm for the Max k-CSP Problem.
Electronic Colloquium on Computational Complexity (ECCC), 2006

Near-optimal algorithms for unique games.
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Directed metrics and directed graph partitioning problems.
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

A robust maximum completion time measure for scheduling.
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

l22 spreading metrics for vertex ordering problems.
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Efficient filtering with sketches in the ferret toolkit.
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.
Proceedings of the 2006 EuroSys Conference, Leuven, Belgium, April 18-21, 2006, 2006

2005
The smallest grammar problem.
IEEE Trans. Information Theory, 2005

Improved Combinatorial Algorithms for Facility Location Problems.
SIAM J. Comput., 2005

On non-uniform multicommodity buy-at-bulk network design.
Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

Aggregating inconsistent information: ranking and clustering.
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.
Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

A tight threshold for metric Ramsey phenomena.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Approximating the average response time in broadcast scheduling.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Fitting tree metrics: Hierarchical clustering and Phylogeny.
Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

Sampling Bounds for Stochastic Optimization.
Proceedings of the Approximation, 2005

2004
On the advantage of network coding for improving network throughput.
Proceedings of the 2004 IEEE Information Theory Workshop, 2004

Maximizing Quadratic Programs: Extending Grothendieck's Inequality.
Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

On the Integrality Ratio for Asymmetric TSP.
Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

Image similarity search with compact data structures.
Proceedings of the 2004 ACM CIKM International Conference on Information and Knowledge Management, 2004

2003
Better streaming algorithms for clustering problems.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Clustering with Qualitative Information.
Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

On the Impossibility of Dimension Reduction in l1.
Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

2002
A Constant-Factor Approximation Algorithm for the k-Median Problem.
J. Comput. Syst. Sci., 2002

Query Strategies for Priced Information.
J. Comput. Syst. Sci., 2002

Approximating the smallest grammar: Kolmogorov complexity in natural models.
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

Similarity estimation techniques from rounding algorithms.
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

On semidefinite programming relaxations for graph coloring and vertex cover.
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.
Proceedings of the Automata, Languages and Programming, 29th International Colloquium, 2002

Finding Frequent Items in Data Streams.
Proceedings of the Automata, Languages and Programming, 29th International Colloquium, 2002

Dimension Reduction in the \ell _1 Norm.
Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002

2001
On page migration and other relaxed task systems.
Theor. Comput. Sci., 2001

Clustering to minimize the sum of cluster diameters.
Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

Approximating min-sum k-clustering in metric spaces.
Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

Algorithms for facility location problems with outliers.
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

2000
Min-Wise Independent Permutations.
J. Comput. Syst. Sci., 2000

On-Line Load Balancing for Related Machines
Electronic Colloquium on Computational Complexity (ECCC), 2000

Query strategies for priced information (extended abstract).
Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Towards Estimation Error Guarantees for Distinct Values.
Proceedings of the Nineteenth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2000

Resource Optimization in QoS Multicast Routing of Real-Time Multimedia.
Proceedings of the Proceedings IEEE INFOCOM 2000, 2000

Minimum Outage Transmission over Fading Channels with Delay Constraint.
Proceedings of the 2000 IEEE International Conference on Communications: Global Convergence Through Communications, 2000

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

Greedy approximation algorithms for finding dense components in a graph.
Proceedings of the Approximation Algorithms for Combinatorial Optimization, 2000

1999
On targeting Markov segments.
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).
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Minimizing Wirelength in Zero and Bounded Skew Clock Trees.
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

Improved Combinatorial Algorithms for the Facility Location and k-Median Problems.
Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

1998
Algorithms for Capacitated Vehicle Routing.
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

Rounding via Trees: Deterministic Approximation Algorithms for Group Steiner Trees and k-Median.
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

Min-Wise Independent Permutations (Extended Abstract).
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

The Dynamic Servers Problem.
Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998

Approximation Algorithms for Directed Steiner Problems.
Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998

A Derandomization Using Min-Wise Independent Permutations.
Proceedings of the Randomization and Approximation Techniques in Computer Science, 1998

The Finite Capacity Dial-A-Ride Problem.
Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

Approximating a Finite Metric by a Small Number of Tree Metrics.
Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

Delayed Information and Action in On-line Algorithms.
Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

1997
Constrained TSP and Low-Power Computing.
Proceedings of the Algorithms and Data Structures, 5th International Workshop, 1997

On-line Load Balancing for Related Machines.
Proceedings of the Algorithms and Data Structures, 5th International Workshop, 1997

Incremental Clustering and Dynamic Information Retrieval.
Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

On Page Migration and Other Related Task Systems.
Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997


  Loading...