Moses Charikar

259 papers A* 109A 17B 8Journal 108Unranked 14

Year	Rank	Type	Title / Venue / Authors
2026	A*	`conf`	Approximately Dominating Sets in Elections. SODA Moses Charikar, Prasanna Ramakrishnan, Kangning Wang
2025	J	`jnl`	A Characterization of List Language Identification in the Limit. CoRR Moses Charikar, Chirag Pabbaraju, Ambuj Tewari
2025	A*	`conf`	An Improved Greedy Approximation for (Metric) k-Means. FOCS Moses Charikar, Vincent Cohen-Addad, Ruiquan Gao, Fabrizio Grandoni, Euiwoong Lee, Ernest van Wijland
2025	J	`jnl`	Approximately Dominating Sets in Elections. CoRR Moses Charikar, Prasanna Ramakrishnan, Kangning Wang
2025	A*	`conf`	Correlation Clustering Beyond the Pivot Algorithm. ICML Soheil Behnezhad, Moses Charikar, Vincent Cohen-Addad, Alma Ghafari, Weiyun Ma
2025	A*	`conf`	Embedding Probability Distributions into Low Dimensional ℓ SODA Moses Charikar, Spencer Compton, Chirag Pabbaraju
2025	A*	`conf`	Exploring Facets of Language Generation in the Limit. COLT Moses Charikar, Chirag Pabbaraju
2025	A*	`conf`	Metric Distortion for Tournament Voting and Beyond. EC Moses Charikar, Prasanna Ramakrishnan, Zihan Tan, Kangning Wang
2025	J	`jnl`	Metric Distortion for Tournament Voting and Beyond. CoRR Moses Charikar, Prasanna Ramakrishnan, Zihan Tan, Kangning Wang
2025	J	`jnl`	Pareto-optimal Non-uniform Language Generation. CoRR Moses Charikar, Chirag Pabbaraju
2025	A*	`conf`	Six Candidates Suffice to Win a Voter Majority. STOC Moses Charikar, Alexandra Lassota, Prasanna Ramakrishnan, Adrian Vetta, Kangning Wang
2025	A*	`conf`	The Johnson-Lindenstrauss Lemma for Clustering and Subspace Approximation: From Coresets to Dimension Reduction. SODA Moses Charikar, Erik Waingarten
2025	B	`conf`	Towards SMT Solver Stability via Input Normalization. FMCAD Daneshvar Amrollahi, Mathias Preiner, Aina Niemetz, Andrew Reynolds, Moses Charikar, Cesare Tinelli, Clark W. Barrett
2024	A*	`conf`	A Quasi-Monte Carlo Data Structure for Smooth Kernel Evaluations. SODA Moses Charikar, Michael Kapralov, Erik Waingarten
2024	J	`jnl`	A Quasi-Monte Carlo Data Structure for Smooth Kernel Evaluations. CoRR Moses Charikar, Michael Kapralov, Erik Waingarten
2024	A*	`conf`	Breaking the Metric Voting Distortion Barrier. SODA Moses Charikar, Kangning Wang, Prasanna Ramakrishnan, Hongxun Wu
2024	J	`jnl`	Breaking the Metric Voting Distortion Barrier. J. ACM Moses Charikar, Prasanna Ramakrishnan, Kangning Wang, Hongxun Wu
2024	A*	`conf`	Dynamic Data Layout Optimization with Worst-Case Guarantees. ICDE Kexin Rong, Paul Liu, Sarah Ashok Sonje, Moses Charikar
2024	J	`jnl`	Dynamic Data Layout Optimization with Worst-case Guarantees. CoRR Kexin Rong, Paul Liu, Sarah Ashok Sonje, Moses Charikar
2024	J	`jnl`	Exploring Facets of Language Generation in the Limit. CoRR Moses Charikar, Chirag Pabbaraju
2024	J	`jnl`	Fully Dynamic Correlation Clustering: Breaking 3-Approximation. CoRR Soheil Behnezhad, Moses Charikar, Vincent Cohen-Addad, Alma Ghafari, Weiyun Ma
2024	A*	`conf`	Improved Approximations for Ultrametric Violation Distance. SODA Moses Charikar, Ruiquan Gao
2024	A*	`conf`	Quantifying the Gain in Weak-to-Strong Generalization. NeurIPS Moses Charikar, Chirag Pabbaraju, Kirankumar Shiragur
2024	J	`jnl`	Quantifying the Gain in Weak-to-Strong Generalization. CoRR Moses Charikar, Chirag Pabbaraju, Kirankumar Shiragur
2024	J	`jnl`	Six Candidates Suffice to Win a Voter Majority. CoRR Moses Charikar, Alexandra Lassota, Prasanna Ramakrishnan, Adrian Vetta, Kangning Wang
2024	J	`jnl`	Using Normalization to Improve SMT Solver Stability. CoRR Daneshvar Amrollahi, Mathias Preiner, Aina Niemetz, Andrew Reynolds, Moses Charikar, Cesare Tinelli, Clark W. Barrett
2023	A*	`conf`	A Characterization of List Learnability. STOC Moses Charikar, Chirag Pabbaraju
2023	J	`jnl`	Average-Case Dimensionality Reduction in 𝓁 CoRR Moses Charikar, Spencer Compton, Chirag Pabbaraju
2023	J	`jnl`	Breaking the Metric Voting Distortion Barrier. CoRR Moses Charikar, Prasanna Ramakrishnan, Kangning Wang, Hongxun Wu
2023	A*	`conf`	Distortion in metric matching with ordinal preferences. EC Nima Anari, Moses Charikar, Prasanna Ramakrishnan
2023	J	`jnl`	Distortion in metric matching with ordinal preferences. CoRR Nima Anari, Moses Charikar, Prasanna Ramakrishnan
2023	A*	`conf`	Fast Algorithms for a New Relaxation of Optimal Transport. COLT Moses Charikar, Beidi Chen, Christopher Ré, Erik Waingarten
2023	J	`jnl`	Fast Algorithms for a New Relaxation of Optimal Transport. CoRR Moses Charikar, Beidi Chen, Christopher Ré, Erik Waingarten
2023	J	`jnl`	Improved Approximations for Ultrametric Violation Distance. CoRR Moses Charikar, Ruiquan Gao
2023	A*	`conf`	Simple, Scalable and Effective Clustering via One-Dimensional Projections. NeurIPS Moses Charikar, Monika Henzinger, Lunjia Hu, Maximilian Vötsch, Erik Waingarten
2023	J	`jnl`	Simple, Scalable and Effective Clustering via One-Dimensional Projections. CoRR Moses Charikar, Monika Henzinger, Lunjia Hu, Maximilian Vötsch, Erik Waingarten
2023	A*	`conf`	Single-Pass Streaming Algorithms for Correlation Clustering. SODA Soheil Behnezhad, Moses Charikar, Weiyun Ma, Li-Yang Tan
2022	J	`jnl`	A Characterization of List Learnability. CoRR Moses Charikar, Chirag Pabbaraju
2022	A*	`conf`	Almost 3-Approximate Correlation Clustering in Constant Rounds. FOCS Soheil Behnezhad, Moses Charikar, Weiyun Ma, Li-Yang Tan
2022	J	`jnl`	Almost 3-Approximate Correlation Clustering in Constant Rounds. CoRR Soheil Behnezhad, Moses Charikar, Weiyun Ma, Li-Yang Tan
2022	J	`jnl`	Local Density Estimation in High Dimensions. Math. Oper. Res. Xian Wu, Moses Charikar, Vishnu Natchu
2022	A*	`conf`	Metric Distortion Bounds for Randomized Social Choice. SODA Moses Charikar, Prasanna Ramakrishnan
2022	A*	`conf`	Near-Optimal Explainable k-Means for All Dimensions. SODA Moses Charikar, Lunjia Hu
2022	J	`jnl`	On the Complexity of Sampling Redistricting Plans. CoRR Moses Charikar, Paul Liu, Tianyu Liu, Thuy-Duong Vuong
2022	A*	`conf`	On the Efficient Implementation of High Accuracy Optimality of Profile Maximum Likelihood. NeurIPS Moses Charikar, Zhihao Jiang, Kirankumar Shiragur, Aaron Sidford
2022	J	`jnl`	On the Efficient Implementation of High Accuracy Optimality of Profile Maximum Likelihood. CoRR Moses Charikar, Zhihao Jiang, Kirankumar Shiragur, Aaron Sidford
2022	A*	`conf`	Polylogarithmic Sketches for Clustering. ICALP Moses Charikar, Erik Waingarten
2022	J	`jnl`	Polylogarithmic Sketches for Clustering. CoRR Moses Charikar, Erik Waingarten
2022	J	`jnl`	The Johnson-Lindenstrauss Lemma for Clustering and Subspace Approximation: From Coresets to Dimension Reduction. CoRR Moses Charikar, Erik Waingarten
2021	A	`conf`	A Model for Ant Trail Formation and its Convergence Properties (Extended Abstract). ITCS Moses Charikar, Shivam Garg, Deborah M. Gordon, Kirankumar Shiragur
2021	A	`conf`	Approximation Algorithms for Orthogonal Non-negative Matrix Factorization. AISTATS Moses Charikar, Lunjia Hu
2021	J	`jnl`	Approximation Algorithms for Orthogonal Non-negative Matrix Factorization. CoRR Moses Charikar, Lunjia Hu
2021	A*	`conf`	Brief Announcement: A Randomness-efficient Massively Parallel Algorithm for Connectivity. PODC Moses Charikar, Weiyun Ma, Li-Yang Tan
2021	—	`conf`	Improved Algorithms for Edge Colouring in the W-Streaming Model. SOSA Moses Charikar, Paul Liu
2021	J	`jnl`	Metric Distortion Bounds for Randomized Social Choice. CoRR Moses Charikar, Prasanna Ramakrishnan
2021	A*	`conf`	Multiway Online Correlated Selection. FOCS Guy Blanc, Moses Charikar
2021	J	`jnl`	Multiway Online Correlated Selection. CoRR Guy Blanc, Moses Charikar
2021	J	`jnl`	Near-Optimal Explainable k-Means for All Dimensions. CoRR Moses Charikar, Lunjia Hu
2021	A*	`conf`	The Bethe and Sinkhorn Permanents of Low Rank Matrices and Implications for Profile Maximum Likelihood. COLT Nima Anari, Moses Charikar, Kirankumar Shiragur, Aaron Sidford
2020	J	`jnl`	A General Framework for Symmetric Property Estimation. CoRR Moses Charikar, Kirankumar Shiragur, Aaron Sidford
2020	J	`jnl`	A Model for Ant Trail Formation and its Convergence Properties. CoRR Moses Charikar, Shivam Garg, Deborah M. Gordon, Kirankumar Shiragur
2020	J	`jnl`	A Simple Sublinear Algorithm for Gap Edit Distance. CoRR Joshua Brakensiek, Moses Charikar, Aviad Rubinstein
2020	—	`conf`	Adaptive Discrete Phase Retrieval. SOSA Moses Charikar, Xian Wu, Yinyu Ye
2020	J	`jnl`	CoopStore: Optimizing Precomputed Summaries for Aggregation. Proc. VLDB Endow. Edward Gan, Peter Bailis, Moses Charikar
2020	J	`jnl`	Improved Algorithms for Edge Colouring in the W-Streaming Model. CoRR Moses Charikar, Paul Liu
2020	A*	`conf`	Instance Based Approximations to Profile Maximum Likelihood. NeurIPS Nima Anari, Moses Charikar, Kirankumar Shiragur, Aaron Sidford
2020	J	`jnl`	Instance Based Approximations to Profile Maximum Likelihood. CoRR Nima Anari, Moses Charikar, Kirankumar Shiragur, Aaron Sidford
2020	A	`conf`	Institutions Share Successes, Failures, and Advice in Moving the Diversity Needle. SIGCSE Dan Garcia, Moses Charikar, Eboney Hearn, Ed Lazowska, Jonathan Reynolds
2020	A*	`conf`	Kernel Density Estimation through Density Constrained Near Neighbor Search. FOCS Moses Charikar, Michael Kapralov, Navid Nouri, Paris Siminelakis
2020	J	`jnl`	Kernel Density Estimation through Density Constrained Near Neighbor Search. CoRR Moses Charikar, Michael Kapralov, Navid Nouri, Paris Siminelakis
2020	J	`jnl`	Nearest Neighbor Search for Hyperbolic Embeddings. CoRR Xian Wu, Moses Charikar
2020	J	`jnl`	New lower bounds for Massively Parallel Computation from query complexity. CoRR Moses Charikar, Weiyun Ma, Li-Yang Tan
2020	A	`conf`	Retrieving Top Weighted Triangles in Graphs. WSDM Raunak Kumar, Paul Liu, Moses Charikar, Austin R. Benson
2020	J	`jnl`	Storyboard: Optimizing Precomputed Summaries for Aggregation. CoRR Edward Gan, Peter Bailis, Moses Charikar
2020	J	`jnl`	The Bethe and Sinkhorn Permanents of Low Rank Matrices and Implications for Profile Maximum Likelihood. CoRR Nima Anari, Moses Charikar, Kirankumar Shiragur, Aaron Sidford
2020	J	`jnl`	The one-way communication complexity of dynamic time warping distance. J. Comput. Geom. Vladimir Braverman, Moses Charikar, William Kuszmaul, Lin F. Yang
2020	B	`conf`	Unconditional Lower Bounds for Adaptive Massively Parallel Computation. SPAA Moses Charikar, Weiyun Ma, Li-Yang Tan
2019	A*	`conf`	A General Framework for Symmetric Property Estimation. NeurIPS Moses Charikar, Kirankumar Shiragur, Aaron Sidford
2019	J	`jnl`	Efficient Profile Maximum Likelihood for Universal Symmetric Property Estimation. CoRR Moses Charikar, Kirankumar Shiragur, Aaron Sidford
2019	A*	`conf`	Efficient profile maximum likelihood for universal symmetric property estimation. STOC Moses Charikar, Kirankumar Shiragur, Aaron Sidford
2019	A*	`conf`	Hierarchical Clustering better than Average-Linkage. SODA Moses Charikar, Vaggos Chatziafratis, Rad Niazadeh
2019	A	`conf`	Hierarchical Clustering for Euclidean Data. AISTATS Moses Charikar, Vaggos Chatziafratis, Rad Niazadeh, Grigory Yaroslavtsev
2019	A*	`conf`	Multi-resolution Hashing for Fast Pairwise Summations. FOCS Moses Charikar, Paris Siminelakis
2019	A*	`ed.`	Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019. STOC Moses Charikar, Edith Cohen
2019	A	`conf`	Recovery Guarantees For Quadratic Tensors With Sparse Observations. AISTATS Hongyang Zhang, Vatsal Sharan, Moses Charikar, Yingyu Liang
2019	A*	`conf`	Rehashing Kernel Evaluation in High Dimensions. ICML Paris Siminelakis, Kexin Rong, Peter Bailis, Moses Charikar, Philip Alexander Levis
2019	J	`jnl`	Retrieving Top Weighted Triangles in Graphs. CoRR Raunak Kumar, Paul Liu, Moses Charikar, Austin R. Benson
2019	A	`conf`	Sampling Methods for Counting Temporal Motifs. WSDM Paul Liu, Austin R. Benson, Moses Charikar
2019	A*	`conf`	The One-Way Communication Complexity of Dynamic Time Warping Distance. SoCG Vladimir Braverman, Moses Charikar, William Kuszmaul, David P. Woodruff, Lin F. Yang
2019	J	`jnl`	The One-Way Communication Complexity of Dynamic Time Warping Distance. CoRR Vladimir Braverman, Moses Charikar, William Kuszmaul, David P. Woodruff, Lin F. Yang
2018	J	`jnl`	A sampling framework for counting temporal motifs. CoRR Paul Liu, Austin R. Benson, Moses Charikar
2018	A*	`conf`	Efficient Density Evaluation for Smooth Kernels. FOCS Arturs Backurs, Moses Charikar, Piotr Indyk, Paris Siminelakis
2018	A*	`conf`	Fully Dynamic Almost-Maximal Matching: Breaking the Polynomial Worst-Case Time Barrier. ICALP Moses Charikar, Shay Solomon
2018	J	`jnl`	Hashing-Based-Estimators for Kernel Density in High Dimensions. CoRR Moses Charikar, Paris Siminelakis
2018	J	`jnl`	Hierarchical Clustering better than Average-Linkage. CoRR Moses Charikar, Vaggos Chatziafratis, Rad Niazadeh
2018	J	`jnl`	Hierarchical Clustering for Euclidean Data. CoRR Moses Charikar, Vaggos Chatziafratis, Rad Niazadeh, Grigory Yaroslavtsev
2018	A*	`conf`	Hierarchical Clustering with Structural Constraints. ICML Vaggos Chatziafratis, Rad Niazadeh, Moses Charikar
2018	J	`jnl`	Hierarchical Clustering with Structural Constraints. CoRR Vaggos Chatziafratis, Rad Niazadeh, Moses Charikar
2018	A*	`conf`	Local Density Estimation in High Dimensions. ICML Xian Wu, Moses Charikar, Vishnu Natchu
2018	J	`jnl`	Local Density Estimation in High Dimensions. CoRR Xian Wu, Moses Charikar, Vishnu Natchu
2018	J	`jnl`	Multi-Commodity Flow with In-Network Processing. CoRR Moses Charikar, Yonatan Naamad, Jennifer Rexford, X. Kelvin Zou
2018	J	`jnl`	Multi-Resolution Hashing for Fast Pairwise Summations. CoRR Moses Charikar, Paris Siminelakis
2018	—	`conf`	Multi-commodity Flow with In-Network Processing. ALGOCLOUD Moses Charikar, Yonatan Naamad, Jennifer Rexford, X. Kelvin Zou
2018	A*	`conf`	On Estimating Edit Distance: Alignment, Dimension Reduction, and Embeddings. ICALP Moses Charikar, Ofir Geri, Michael P. Kim, William Kuszmaul
2018	J	`jnl`	On Estimating Edit Distance: Alignment, Dimension Reduction, and Embeddings. CoRR Moses Charikar, Ofir Geri, Michael P. Kim, William Kuszmaul
2018	J	`jnl`	On Finding Dense Common Subgraphs. CoRR Moses Charikar, Yonatan Naamad, Jimmy Wu
2018	J	`jnl`	Recovery Guarantees for Quadratic Tensors with Limited Observations. CoRR Hongyang Zhang, Vatsal Sharan, Moses Charikar, Yingyu Liang
2018	A	`conf`	Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers. ITCS Jacob Steinhardt, Moses Charikar, Gregory Valiant
2017	A*	`conf`	A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics. COLT Yuchen Zhang, Percy Liang, Moses Charikar
2017	J	`jnl`	A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics. CoRR Yuchen Zhang, Percy Liang, Moses Charikar
2017	A*	`conf`	Approximate Hierarchical Clustering via Sparsest Cut and Spreading Metrics. SODA Moses Charikar, Vaggos Chatziafratis
2017	J	`jnl`	Fully Dynamic Almost-Maximal Matching: Breaking the Polynomial Barrier for Worst-Case Time Bounds. CoRR Moses Charikar, Shay Solomon
2017	A*	`conf`	Hashing-Based-Estimators for Kernel Density in High Dimensions. FOCS Moses Charikar, Paris Siminelakis
2017	J	`jnl`	Intelligent Probing for Locality Sensitive Hashing: Multi-Probe LSH and Beyond. Proc. VLDB Endow. Qin Lv, William Josephson, Zhe Wang, Moses Charikar, Kai Li
2017	A*	`conf`	Learning from untrusted data. STOC Moses Charikar, Jacob Steinhardt, Gregory Valiant
2017	B	`conf`	Local Guarantees in Graph Cuts and Clustering. IPCO Moses Charikar, Neha Gupta, Roy Schwartz
2017	J	`jnl`	Local Guarantees in Graph Cuts and Clustering. CoRR Moses Charikar, Neha Gupta, Roy Schwartz
2017	—	`conf`	Min-Cost Bipartite Perfect Matching with Delays. APPROX-RANDOM Itai Ashlagi, Yossi Azar, Moses Charikar, Ashish Chiplunkar, Ofir Geri, Haim Kaplan, Rahul Makhijani, Yuyi Wang, Roger Wattenhofer
2017	J	`jnl`	Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers. CoRR Jacob Steinhardt, Moses Charikar, Gregory Valiant
2016	J	`jnl`	Approximate Hierarchical Clustering via Sparsest Cut and Spreading Metrics. CoRR Moses Charikar, Vaggos Chatziafratis
2016	—	`conf`	Avoiding Imposters and Delinquents: Adversarial Crowdsourcing and Peer Prediction. NIPS Jacob Steinhardt, Gregory Valiant, Moses Charikar
2016	J	`jnl`	Avoiding Imposters and Delinquents: Adversarial Crowdsourcing and Peer Prediction. CoRR Jacob Steinhardt, Gregory Valiant, Moses Charikar
2016	J	`jnl`	Learning from Untrusted Data. CoRR Moses Charikar, Jacob Steinhardt, Gregory Valiant
2016	—	`conf`	On Approximating Target Set Selection. APPROX-RANDOM Moses Charikar, Yonatan Naamad, Anthony Wirth
2016	A	`conf`	Spectral Embedding of k-Cliques, Graph Partitioning and k-Means. ITCS Pranjal Awasthi, Moses Charikar, Ravishankar Krishnaswamy, Ali Kemal Sinop
2016	—	`ch.`	Top-k Frequent Item Maintenance over Streams. Data Stream Management Moses Charikar
2015	A*	`conf`	Label optimal regret bounds for online local learning. COLT Pranjal Awasthi, Moses Charikar, Kevin A. Lai, Andrej Risteski
2015	J	`jnl`	Label optimal regret bounds for online local learning. CoRR Pranjal Awasthi, Moses Charikar, Kevin A. Lai, Andrej Risteski
2015	A	`conf`	Relax, No Need to Round: Integrality of Clustering Formulations. ITCS Pranjal Awasthi, Afonso S. Bandeira, Moses Charikar, Ravishankar Krishnaswamy, Soledad Villar, Rachel A. Ward
2015	A*	`conf`	The Hardness of Approximation of Euclidean k-Means. SoCG Pranjal Awasthi, Moses Charikar, Ravishankar Krishnaswamy, Ali Kemal Sinop
2015	J	`jnl`	The Hardness of Approximation of Euclidean k-means. CoRR Pranjal Awasthi, Moses Charikar, Ravishankar Krishnaswamy, Ali Kemal Sinop
2014	A*	`conf`	Better Algorithms and Hardness for Broadcast Scheduling via a Discrepancy Approach. SODA Nikhil Bansal, Moses Charikar, Ravishankar Krishnaswamy, Shi Li
2014	A	`conf`	Multireference alignment using semidefinite programming. ITCS Afonso S. Bandeira, Moses Charikar, Amit Singer, Andy Zhu
2014	A	`conf`	Online Bipartite Matching with Decomposable Weights. ESA Moses Charikar, Monika Henzinger, Huy L. Nguyen
2014	J	`jnl`	Online Bipartite Matching with Decomposable Weights. CoRR Moses Charikar, Monika Henzinger, Huy L. Nguyen
2014	A*	`conf`	Open Problem: Tensor Decompositions: Algorithms up to the Uniqueness Threshold? COLT Aditya Bhaskara, Moses Charikar, Ankur Moitra, Aravindan Vijayaraghavan
2014	J	`jnl`	Relax, no need to round: integrality of clustering formulations. CoRR Pranjal Awasthi, Afonso S. Bandeira, Moses Charikar, Ravishankar Krishnaswamy, Soledad Villar, Rachel A. Ward
2014	A*	`conf`	Smoothed analysis of tensor decompositions. STOC Aditya Bhaskara, Moses Charikar, Ankur Moitra, Aravindan Vijayaraghavan
2014	A*	`conf`	Uniqueness of Tensor Decompositions with Applications to Polynomial Identifiability. COLT Aditya Bhaskara, Moses Charikar, Aravindan Vijayaraghavan
2013	J	`jnl`	Multireference Alignment using Semidefinite Programming. CoRR Afonso S. Bandeira, Moses Charikar, Amit Singer, Andy Zhu
2013	J	`jnl`	Smoothed Analysis of Tensor Decompositions. CoRR Aditya Bhaskara, Moses Charikar, Ankur Moitra, Aravindan Vijayaraghavan
2013	J	`jnl`	Uniqueness of Tensor Decompositions with Applications to Polynomial Identifiability CoRR Aditya Bhaskara, Moses Charikar, Aravindan Vijayaraghavan
2012	—	`conf`	A Dependent LP-Rounding Approach for the k-Median Problem. ICALP (1) Moses Charikar, Shi Li
2012	B	`conf`	High-confidence near-duplicate image detection. ICMR Wei Dong, Zhe Wang, Moses Charikar, Kai Li
2012	—	`conf`	On Quadratic Programming with a Ratio Objective. ICALP (1) Aditya Bhaskara, Moses Charikar, Rajsekar Manokaran, Aravindan Vijayaraghavan
2012	A*	`conf`	Polynomial integrality gaps for strong SDP relaxations of Densest SODA Aditya Bhaskara, Moses Charikar, Aravindan Vijayaraghavan, Venkatesan Guruswami, Yuan Zhou
2011	J	`jnl`	Beating the Random Ordering Is Hard: Every Ordering CSP Is Approximation Resistant. SIAM J. Comput. Venkatesan Guruswami, Johan Håstad, Rajsekar Manokaran, Prasad Raghavendra, Moses Charikar
2011	J	`jnl`	Beating the Random Ordering is Hard: Every ordering CSP is approximation resistant. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Johan Håstad, Rajsekar Manokaran, Prasad Raghavendra, Moses Charikar
2011	A*	`conf`	Efficient k-nearest neighbor graph construction for generic similarity measures. WWW Wei Dong, Moses Charikar, Kai Li
2011	J	`jnl`	Fitting Tree Metrics: Hierarchical Clustering and Phylogeny. SIAM J. Comput. Nir Ailon, Moses Charikar
2011	J	`jnl`	Improved Approximation Algorithms for Label Cover Problems. Algorithmica Moses Charikar, MohammadTaghi Hajiaghayi, Howard J. Karloff
2011	A*	`conf`	Near Linear Lower Bound for Dimension Reduction in L1. FOCS Alexandr Andoni, Moses Charikar, Ofer Neiman, Huy L. Nguyen
2011	J	`jnl`	On Quadratic Programming with a Ratio Objective CoRR Aditya Bhaskara, Moses Charikar, Rajsekar Manokaran, Aravindan Vijayaraghavan
2011	J	`jnl`	Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph CoRR Aditya Bhaskara, Moses Charikar, Venkatesan Guruswami, Aravindan Vijayaraghavan, Yuan Zhou
2011	A*	`conf`	Tight Hardness Results for Minimizing Discrepancy. SODA Moses Charikar, Alantha Newman, Aleksandar Nikolov
2010	J	`jnl`	Detecting High Log-Densities -- an O(n^1/4) Approximation for Densest k-Subgraph CoRR Aditya Bhaskara, Moses Charikar, Eden Chlamtac, Uriel Feige, Aravindan Vijayaraghavan
2010	A*	`conf`	Detecting high log-densities: an STOC Aditya Bhaskara, Moses Charikar, Eden Chlamtac, Uriel Feige, Aravindan Vijayaraghavan
2010	J	`jnl`	Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes) CoRR Prahladh Harsha, Moses Charikar, Matthew Andrews, Sanjeev Arora, Subhash Khot, Dana Moshkovitz, Lisa Zhang, Ashkan Aazami, Dev Desai, Igor Gorodezky, Geetha Jagannathan, Alexander S. Kulikov, Darakhshan J. Mir, Alantha Newman, Aleksandar Nikolov, David Pritchard, Gwen Spencer
2010	J	`jnl`	Local Global Tradeoffs in Metric Embeddings. SIAM J. Comput. Moses Charikar, Konstantin Makarychev, Yury Makarychev
2010	A*	`ed.`	Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010 SODA Moses Charikar
2010	J	`jnl`	Vertex Sparsifiers and Abstract Rounding Algorithms CoRR Moses Charikar, Tom Leighton, Shi Li, Ankur Moitra
2010	A*	`conf`	Vertex Sparsifiers and Abstract Rounding Algorithms. FOCS Moses Charikar, Tom Leighton, Shi Li, Ankur Moitra
2009	A	`conf`	Every Permutation CSP of arity 3 is Approximation Resistant. CCC Moses Charikar, Venkatesan Guruswami, Rajsekar Manokaran
2009	A	`conf`	Improved Approximation Algorithms for Label Cover Problems. ESA Moses Charikar, MohammadTaghi Hajiaghayi, Howard J. Karloff
2009	A*	`conf`	Integrality gaps for Sherali-Adams relaxations. STOC Moses Charikar, Konstantin Makarychev, Yury Makarychev
2009	A*	`conf`	MaxMin allocation via degree lower-bounded arborescences. STOC MohammadHossein Bateni, Moses Charikar, Venkatesan Guruswami
2009	J	`jnl`	Near-optimal algorithms for maximum constraint satisfaction problems. ACM Trans. Algorithms Moses Charikar, Konstantin Makarychev, Yury Makarychev
2008	J	`jnl`	Aggregating inconsistent information: Ranking and clustering. J. ACM Nir Ailon, Moses Charikar, Alantha Newman
2008	A*	`conf`	Asymmetric distance estimation with sketches for similarity search in high-dimensional spaces. SIGIR Wei Dong, Moses Charikar, Kai Li
2008	A*	`conf`	Efficiently matching sets of features with random histograms. ACM Multimedia Wei Dong, Zhe Wang, Moses Charikar, Kai Li
2008	A	`conf`	Modeling LSH for performance tuning. CIKM Wei Dong, Zhe Wang, William Josephson, Moses Charikar, Kai Li
2008	B	`conf`	Online multicast with egalitarian cost sharing. SPAA Moses Charikar, Howard J. Karloff, Claire Mathieu, Joseph Naor, Michael E. Saks
2007	A*	`conf`	A divide and conquer algorithm for SODA Moses Charikar, Konstantin Makarychev, Yury Makarychev
2007	—	`ed.`	Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 10th International Workshop, APPROX 2007, and 11th International Workshop, RANDOM 2007, Princeton, NJ, USA, August 20-22, 2007, Proceedings APPROX-RANDOM Moses Charikar, Klaus Jansen, Omer Reingold, José D. P. Rolim
2007	—	`conf`	Filtering Image Spam with Near-Duplicate Detection. CEAS Zhe Wang, William K. Josephson, Qin Lv, Moses Charikar, Kai Li
2007	A*	`conf`	Improved approximation for directed cut problems. STOC Amit Agarwal, Noga Alon, Moses Charikar
2007	A*	`conf`	Local Global Tradeoffs in Metric Embeddings. FOCS Moses Charikar, Konstantin Makarychev, Yury Makarychev
2007	J	`jnl`	Local Global Tradeoffs in Metric Embeddings. Electron. Colloquium Comput. Complex. Moses Charikar, Konstantin Makarychev, Yury Makarychev
2007	A*	`conf`	Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search . VLDB Qin Lv, William Josephson, Zhe Wang, Moses Charikar, Kai Li
2007	A*	`conf`	Near-optimal algorithms for maximum constraint satisfaction problems. SODA Moses Charikar, Konstantin Makarychev, Yury Makarychev
2007	A*	`conf`	On the Advantage over Random for Maximum Acyclic Subgraph. FOCS Moses Charikar, Konstantin Makarychev, Yury Makarychev
2007	J	`jnl`	On the Advantage over Random for Maximum Acyclic Subgraph. Electron. Colloquium Comput. Complex. Moses Charikar, Konstantin Makarychev, Yury Makarychev
2007	A*	`conf`	Sizing sketches: a rank-based analysis for similarity search. SIGMETRICS Zhe Wang, Wei Dong, William Josephson, Qin Lv, Moses Charikar, Kai Li
2006	A*	`conf`	A robust maximum completion time measure for scheduling. SODA Moses Charikar, Samir Khuller
2006	J	`jnl`	Approximation Algorithm for the Max k-CSP Problem. Electron. Colloquium Comput. Complex. Moses Charikar, Konstantin Makarychev, Yury Makarychev
2006	A*	`conf`	Directed metrics and directed graph partitioning problems. SODA Moses Charikar, Konstantin Makarychev, Yury Makarychev
2006	—	`conf`	Efficient filtering with sketches in the ferret toolkit. Multimedia Information Retrieval Qin Lv, William Josephson, Zhe Wang, Moses Charikar, Kai Li
2006	J	`jnl`	Embedding the Ulam metric into Theory Comput. Moses Charikar, Robert Krauthgamer
2006	A	`conf`	Ferret: a toolkit for content-based similarity search of feature-rich data. EuroSys Qin Lv, William Josephson, Zhe Wang, Moses Charikar, Kai Li
2006	J	`jnl`	Guest editor's foreword. J. Comput. Syst. Sci. Moses Charikar
2006	A*	`conf`	Near-optimal algorithms for unique games. STOC Moses Charikar, Konstantin Makarychev, Yury Makarychev
2006	J	`jnl`	Note on MAX 2SAT. Electron. Colloquium Comput. Complex. Moses Charikar, Konstantin Makarychev, Yury Makarychev
2006	J	`jnl`	On the Integrality Ratio for the Asymmetric Traveling Salesman Problem. Math. Oper. Res. Moses Charikar, Michel X. Goemans, Howard J. Karloff
2005	A*	`conf`	A tight threshold for metric Ramsey phenomena. SODA Moses Charikar, Adriana Karagiozova
2005	A*	`conf`	Aggregating inconsistent information: ranking and clustering. STOC Nir Ailon, Moses Charikar, Alantha Newman
2005	A*	`conf`	Approximating the average response time in broadcast scheduling. SODA Nikhil Bansal, Moses Charikar, Sanjeev Khanna, Joseph Naor
2005	J	`jnl`	Clustering with qualitative information. J. Comput. Syst. Sci. Moses Charikar, Venkatesan Guruswami, Anthony Wirth
2005	A*	`conf`	Fitting tree metrics: Hierarchical clustering and Phylogeny. FOCS Nir Ailon, Moses Charikar
2005	J	`jnl`	Improved Combinatorial Algorithms for Facility Location Problems. SIAM J. Comput. Moses Charikar, Sudipto Guha
2005	A*	`conf`	O(sqrt(log n)) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems. STOC Amit Agarwal, Moses Charikar, Konstantin Makarychev, Yury Makarychev
2005	A*	`conf`	On non-uniform multicommodity buy-at-bulk network design. STOC Moses Charikar, Adriana Karagiozova
2005	J	`jnl`	On the impossibility of dimension reduction in l J. ACM Bo Brinkman, Moses Charikar
2005	—	`conf`	Sampling Bounds for Stochastic Optimization. APPROX-RANDOM Moses Charikar, Chandra Chekuri, Martin Pál
2005	J	`jnl`	The smallest grammar problem. IEEE Trans. Inf. Theory Moses Charikar, Eric Lehman, Ding Liu, Rina Panigrahy, Manoj Prabhakaran, Amit Sahai, Abhi Shelat
2004	J	`jnl`	Clustering to minimize the sum of cluster diameters. J. Comput. Syst. Sci. Moses Charikar, Rina Panigrahy
2004	J	`jnl`	Finding frequent items in data streams. Theor. Comput. Sci. Moses Charikar, Kevin C. Chen, Martin Farach-Colton
2004	A	`conf`	Image similarity search with compact data structures. CIKM Qin Lv, Moses Charikar, Kai Li
2004	J	`jnl`	Incremental Clustering and Dynamic Information Retrieval. SIAM J. Comput. Moses Charikar, Chandra Chekuri, Tomás Feder, Rajeev Motwani
2004	A*	`conf`	Maximizing Quadratic Programs: Extending Grothendieck's Inequality. FOCS Moses Charikar, Anthony Wirth
2004	J	`jnl`	Minimizing Wirelength in Zero and Bounded Skew Clock Trees. SIAM J. Discret. Math. Moses Charikar, Jon M. Kleinberg, Ravi Kumar, Sridhar Rajagopalan, Amit Sahai, Andrew Tomkins
2004	A*	`conf`	On the Integrality Ratio for Asymmetric TSP. FOCS Moses Charikar, Michel X. Goemans, Howard J. Karloff
2004	B	`conf`	On the advantage of network coding for improving network throughput. ITW Amit Agarwal, Moses Charikar
2004	J	`jnl`	Resource optimization in QoS multicast routing of real-time multimedia. IEEE/ACM Trans. Netw. Moses Charikar, Joseph Naor, Baruch Schieber
2003	J	`jnl`	A derandomization using min-wise independent permutations. J. Discrete Algorithms Andrei Z. Broder, Moses Charikar, Michael Mitzenmacher
2003	A*	`conf`	Better streaming algorithms for clustering problems. STOC Moses Charikar, Liadan O'Callaghan, Rina Panigrahy
2003	A*	`conf`	Clustering with Qualitative Information. FOCS Moses Charikar, Venkatesan Guruswami, Anthony Wirth
2003	A*	`conf`	On the Impossibility of Dimension Reduction in l FOCS Bo Brinkman, Moses Charikar
2002	J	`jnl`	A Constant-Factor Approximation Algorithm for the k-Median Problem. J. Comput. Syst. Sci. Moses Charikar, Sudipto Guha, Éva Tardos, David B. Shmoys
2002	A*	`conf`	Approximating the smallest grammar: Kolmogorov complexity in natural models. STOC Moses Charikar, Eric Lehman, Ding Liu, Rina Panigrahy, Manoj Prabhakaran, April Rasala, Amit Sahai, Abhi Shelat
2002	A*	`conf`	Dimension Reduction in the \ell _1 Norm. FOCS Moses Charikar, Amit Sahai
2002	A*	`conf`	Finding Frequent Items in Data Streams. ICALP Moses Charikar, Kevin C. Chen, Martin Farach-Colton
2002	A*	`conf`	New Algorithms for Subset Query, Partial Match, Orthogonal Range Searching, and Related Problems. ICALP Moses Charikar, Piotr Indyk, Rina Panigrahy
2002	A*	`conf`	On semidefinite programming relaxations for graph coloring and vertex cover. SODA Moses Charikar
2002	J	`jnl`	Query Strategies for Priced Information. J. Comput. Syst. Sci. Moses Charikar, Ronald Fagin, Venkatesan Guruswami, Jon M. Kleinberg, Prabhakar Raghavan, Amit Sahai
2002	A*	`conf`	Similarity estimation techniques from rounding algorithms. STOC Moses Charikar
2001	J	`jnl`	Algorithms for Capacitated Vehicle Routing. SIAM J. Comput. Moses Charikar, Samir Khuller, Balaji Raghavachari
2001	A*	`conf`	Algorithms for facility location problems with outliers. SODA Moses Charikar, Samir Khuller, David M. Mount, Giri Narasimhan
2001	A*	`conf`	Approximating min-sum STOC Yair Bartal, Moses Charikar, Danny Raz
2001	A*	`conf`	Clustering to minimize the sum of cluster diameters. STOC Moses Charikar, Rina Panigrahy
2001	J	`jnl`	Delayed Information and Action in On-Line Algorithms. Inf. Comput. Susanne Albers, Moses Charikar, Michael Mitzenmacher
2001	J	`jnl`	On page migration and other relaxed task systems. Theor. Comput. Sci. Yair Bartal, Moses Charikar, Piotr Indyk
2000	—	`—`	Algorithms for clustering problems. Moses Charikar
2000	A*	`conf`	Combinatorial feature selection problems. FOCS Moses Charikar, Venkatesan Guruswami, Ravi Kumar, Sridhar Rajagopalan, Amit Sahai
2000	—	`conf`	Greedy approximation algorithms for finding dense components in a graph. APPROX Moses Charikar
2000	J	`jnl`	Min-Wise Independent Permutations. J. Comput. Syst. Sci. Andrei Z. Broder, Moses Charikar, Alan M. Frieze, Michael Mitzenmacher
2000	—	`conf`	Minimum Outage Transmission over Fading Channels with Delay Constraint. ICC (1) Rohit Negi, Moses Charikar, John M. Cioffi
2000	J	`jnl`	On-Line Load Balancing for Related Machines Electron. Colloquium Comput. Complex. Piotr Berman, Moses Charikar, Marek Karpinski
2000	J	`jnl`	On-Line Load Balancing for Related Machines. J. Algorithms Piotr Berman, Moses Charikar, Marek Karpinski
2000	A*	`conf`	Query strategies for priced information (extended abstract). STOC Moses Charikar, Ronald Fagin, Venkatesan Guruswami, Jon M. Kleinberg, Prabhakar Raghavan, Amit Sahai
2000	A*	`conf`	Resource Optimization in QoS Multicast Routing of Real-Time Multimedia. INFOCOM Moses Charikar, Joseph Naor, Baruch Schieber
2000	A*	`conf`	Towards Estimation Error Guarantees for Distinct Values. PODS Moses Charikar, Surajit Chaudhuri, Rajeev Motwani, Vivek R. Narasayya
1999	A*	`conf`	A Constant-Factor Approximation Algorithm for the STOC Moses Charikar, Sudipto Guha, Éva Tardos, David B. Shmoys
1999	J	`jnl`	Approximation Algorithms for Directed Steiner Problems. J. Algorithms Moses Charikar, Chandra Chekuri, To-Yat Cheung, Zuo Dai, Ashish Goel, Sudipto Guha, Ming Li
1999	A*	`conf`	Improved Combinatorial Algorithms for the Facility Location and k-Median Problems. FOCS Moses Charikar, Sudipto Guha
1999	A*	`conf`	Minimizing Wirelength in Zero and Bounded Skew Clock Trees. SODA Moses Charikar, Jon M. Kleinberg, Ravi Kumar, Sridhar Rajagopalan, Amit Sahai, Andrew Tomkins
1999	A*	`conf`	On targeting Markov segments. STOC Moses Charikar, Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, Andrew Tomkins
1998	—	`conf`	A Derandomization Using Min-Wise Independent Permutations. RANDOM Andrei Z. Broder, Moses Charikar, Michael Mitzenmacher
1998	A*	`conf`	Algorithms for Capacitated Vehicle Routing. STOC Moses Charikar, Samir Khuller, Balaji Raghavachari
1998	A*	`conf`	Approximating a Finite Metric by a Small Number of Tree Metrics. FOCS Moses Charikar, Chandra Chekuri, Ashish Goel, Sudipto Guha, Serge A. Plotkin
1998	A*	`conf`	Approximation Algorithms for Directed Steiner Problems. SODA Moses Charikar, Chandra Chekuri, To-Yat Cheung, Zuo Dai, Ashish Goel, Sudipto Guha, Ming Li
1998	A*	`conf`	Delayed Information and Action in On-line Algorithms. FOCS Susanne Albers, Moses Charikar, Michael Mitzenmacher
1998	A*	`conf`	Min-Wise Independent Permutations (Extended Abstract). STOC Andrei Z. Broder, Moses Charikar, Alan M. Frieze, Michael Mitzenmacher
1998	A*	`conf`	Rounding via Trees: Deterministic Approximation Algorithms for Group Steiner Trees and STOC Moses Charikar, Chandra Chekuri, Ashish Goel, Sudipto Guha
1998	A*	`conf`	The Dynamic Servers Problem. SODA Moses Charikar, Dan Halperin, Rajeev Motwani
1998	A*	`conf`	The Finite Capacity Dial-A-Ride Problem. FOCS Moses Charikar, Balaji Raghavachari
1997	B	`conf`	Constrained TSP and Low-Power Computing. WADS Moses Charikar, Rajeev Motwani, Prabhakar Raghavan, Craig Silverstein
1997	A*	`conf`	Incremental Clustering and Dynamic Information Retrieval. STOC Moses Charikar, Chandra Chekuri, Tomás Feder, Rajeev Motwani
1997	A*	`conf`	On Page Migration and Other Relaxed Task Systems. SODA Yair Bartal, Moses Charikar, Piotr Indyk
1997	B	`conf`	On-line Load Balancing for Related Machines. WADS Piotr Berman, Moses Charikar, Marek Karpinski