default search action
Moses Charikar
Moses Samson Charikar
Person information
- affiliation: Stanford University, USA
- affiliation (former): Princeton University, USA
- award (2012): Paris Kanellakis Award
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
- [c138]Kexin Rong, Paul Liu, Sarah Ashok Sonje, Moses Charikar:
Dynamic Data Layout Optimization with Worst-Case Guarantees. ICDE 2024: 4288-4301 - [c137]Moses Charikar, Kangning Wang, Prasanna Ramakrishnan, Hongxun Wu:
Breaking the Metric Voting Distortion Barrier. SODA 2024: 1621-1640 - [c136]Moses Charikar, Ruiquan Gao:
Improved Approximations for Ultrametric Violation Distance. SODA 2024: 1704-1737 - [c135]Moses Charikar, Michael Kapralov, Erik Waingarten:
A Quasi-Monte Carlo Data Structure for Smooth Kernel Evaluations. SODA 2024: 5118-5144 - [i69]Moses Charikar, Michael Kapralov, Erik Waingarten:
A Quasi-Monte Carlo Data Structure for Smooth Kernel Evaluations. CoRR abs/2401.02562 (2024) - [i68]Soheil Behnezhad, Moses Charikar, Vincent Cohen-Addad, Alma Ghafari, Weiyun Ma:
Fully Dynamic Correlation Clustering: Breaking 3-Approximation. CoRR abs/2404.06797 (2024) - [i67]Kexin Rong, Paul Liu, Sarah Ashok Sonje, Moses Charikar:
Dynamic Data Layout Optimization with Worst-case Guarantees. CoRR abs/2405.04984 (2024) - [i66]Moses Charikar, Chirag Pabbaraju, Kirankumar Shiragur:
Quantifying the Gain in Weak-to-Strong Generalization. CoRR abs/2405.15116 (2024) - 2023
- [c134]Moses Charikar, Beidi Chen, Christopher Ré, Erik Waingarten:
Fast Algorithms for a New Relaxation of Optimal Transport. COLT 2023: 4831-4862 - [c133]Moses Charikar, Monika Henzinger, Lunjia Hu, Maximilian Vötsch, Erik Waingarten:
Simple, Scalable and Effective Clustering via One-Dimensional Projections. NeurIPS 2023 - [c132]Nima Anari, Moses Charikar, Prasanna Ramakrishnan:
Distortion in metric matching with ordinal preferences. EC 2023: 90-110 - [c131]Soheil Behnezhad, Moses Charikar, Weiyun Ma, Li-Yang Tan:
Single-Pass Streaming Algorithms for Correlation Clustering. SODA 2023: 819-849 - [c130]Moses Charikar, Chirag Pabbaraju:
A Characterization of List Learnability. STOC 2023: 1713-1726 - [i65]Nima Anari, Moses Charikar, Prasanna Ramakrishnan:
Distortion in metric matching with ordinal preferences. CoRR abs/2305.12119 (2023) - [i64]Moses Charikar, Prasanna Ramakrishnan, Kangning Wang, Hongxun Wu:
Breaking the Metric Voting Distortion Barrier. CoRR abs/2306.17838 (2023) - [i63]Moses Charikar, Beidi Chen, Christopher Ré, Erik Waingarten:
Fast Algorithms for a New Relaxation of Optimal Transport. CoRR abs/2307.10042 (2023) - [i62]Moses Charikar, Monika Henzinger, Lunjia Hu, Maximilian Vötsch, Erik Waingarten:
Simple, Scalable and Effective Clustering via One-Dimensional Projections. CoRR abs/2310.16752 (2023) - [i61]Moses Charikar, Ruiquan Gao:
Improved Approximations for Ultrametric Violation Distance. CoRR abs/2311.04533 (2023) - [i60]Moses Charikar, Spencer Compton, Chirag Pabbaraju:
Average-Case Dimensionality Reduction in 𝓁1: Tree Ising Models. CoRR abs/2312.02435 (2023) - 2022
- [j32]Xian Wu, Moses Charikar, Vishnu Natchu:
Local Density Estimation in High Dimensions. Math. Oper. Res. 47(4): 2614-2640 (2022) - [c129]Soheil Behnezhad, Moses Charikar, Weiyun Ma, Li-Yang Tan:
Almost 3-Approximate Correlation Clustering in Constant Rounds. FOCS 2022: 720-731 - [c128]Moses Charikar, Erik Waingarten:
Polylogarithmic Sketches for Clustering. ICALP 2022: 38:1-38:20 - [c127]Moses Charikar, Zhihao Jiang, Kirankumar Shiragur, Aaron Sidford:
On the Efficient Implementation of High Accuracy Optimality of Profile Maximum Likelihood. NeurIPS 2022 - [c126]Moses Charikar, Lunjia Hu:
Near-Optimal Explainable k-Means for All Dimensions. SODA 2022: 2580-2606 - [c125]Moses Charikar, Prasanna Ramakrishnan:
Metric Distortion Bounds for Randomized Social Choice. SODA 2022: 2986-3004 - [i59]Moses Charikar, Erik Waingarten:
Polylogarithmic Sketches for Clustering. CoRR abs/2204.12358 (2022) - [i58]Moses Charikar, Erik Waingarten:
The Johnson-Lindenstrauss Lemma for Clustering and Subspace Approximation: From Coresets to Dimension Reduction. CoRR abs/2205.00371 (2022) - [i57]Soheil Behnezhad, Moses Charikar, Weiyun Ma, Li-Yang Tan:
Almost 3-Approximate Correlation Clustering in Constant Rounds. CoRR abs/2205.03710 (2022) - [i56]Moses Charikar, Paul Liu, Tianyu Liu, Thuy-Duong Vuong:
On the Complexity of Sampling Redistricting Plans. CoRR abs/2206.04883 (2022) - [i55]Moses Charikar, Zhihao Jiang, Kirankumar Shiragur, Aaron Sidford:
On the Efficient Implementation of High Accuracy Optimality of Profile Maximum Likelihood. CoRR abs/2210.06728 (2022) - [i54]Moses Charikar, Chirag Pabbaraju:
A Characterization of List Learnability. CoRR abs/2211.04956 (2022) - 2021
- [c124]Moses Charikar, Lunjia Hu:
Approximation Algorithms for Orthogonal Non-negative Matrix Factorization. AISTATS 2021: 2728-2736 - [c123]Nima Anari, Moses Charikar, Kirankumar Shiragur, Aaron Sidford:
The Bethe and Sinkhorn Permanents of Low Rank Matrices and Implications for Profile Maximum Likelihood. COLT 2021: 93-158 - [c122]Guy Blanc, Moses Charikar:
Multiway Online Correlated Selection. FOCS 2021: 1277-1284 - [c121]Moses Charikar, Shivam Garg, Deborah M. Gordon, Kirankumar Shiragur:
A Model for Ant Trail Formation and its Convergence Properties (Extended Abstract). ITCS 2021: 85:1-85:2 - [c120]Moses Charikar, Weiyun Ma, Li-Yang Tan:
Brief Announcement: A Randomness-efficient Massively Parallel Algorithm for Connectivity. PODC 2021: 431-433 - [c119]Moses Charikar, Paul Liu:
Improved Algorithms for Edge Colouring in the W-Streaming Model. SOSA 2021: 181-183 - [i53]Moses Charikar, Lunjia Hu:
Approximation Algorithms for Orthogonal Non-negative Matrix Factorization. CoRR abs/2103.01398 (2021) - [i52]Guy Blanc, Moses Charikar:
Multiway Online Correlated Selection. CoRR abs/2106.05579 (2021) - [i51]Moses Charikar, Lunjia Hu:
Near-Optimal Explainable k-Means for All Dimensions. CoRR abs/2106.15566 (2021) - [i50]Moses Charikar, Prasanna Ramakrishnan:
Metric Distortion Bounds for Randomized Social Choice. CoRR abs/2111.03694 (2021) - 2020
- [j31]Vladimir Braverman, Moses Charikar, William Kuszmaul, Lin F. Yang:
The one-way communication complexity of dynamic time warping distance. J. Comput. Geom. 11(2): 62-93 (2020) - [j30]Edward Gan, Peter Bailis, Moses Charikar:
CoopStore: Optimizing Precomputed Summaries for Aggregation. Proc. VLDB Endow. 13(11): 2174-2187 (2020) - [c118]Moses Charikar, Michael Kapralov, Navid Nouri, Paris Siminelakis:
Kernel Density Estimation through Density Constrained Near Neighbor Search. FOCS 2020: 172-183 - [c117]Nima Anari, Moses Charikar, Kirankumar Shiragur, Aaron Sidford:
Instance Based Approximations to Profile Maximum Likelihood. NeurIPS 2020 - [c116]Dan Garcia, Moses Charikar, Eboney Hearn, Ed Lazowska, Jonathan Reynolds:
Institutions Share Successes, Failures, and Advice in Moving the Diversity Needle. SIGCSE 2020: 331-332 - [c115]Moses Charikar, Xian Wu, Yinyu Ye:
Adaptive Discrete Phase Retrieval. SOSA 2020: 47-56 - [c114]Moses Charikar, Weiyun Ma, Li-Yang Tan:
Unconditional Lower Bounds for Adaptive Massively Parallel Computation. SPAA 2020: 141-151 - [c113]Raunak Kumar, Paul Liu, Moses Charikar, Austin R. Benson:
Retrieving Top Weighted Triangles in Graphs. WSDM 2020: 295-303 - [i49]Moses Charikar, Weiyun Ma, Li-Yang Tan:
New lower bounds for Massively Parallel Computation from query complexity. CoRR abs/2001.01146 (2020) - [i48]Edward Gan, Peter Bailis, Moses Charikar:
Storyboard: Optimizing Precomputed Summaries for Aggregation. CoRR abs/2002.03063 (2020) - [i47]Moses Charikar, Kirankumar Shiragur, Aaron Sidford:
A General Framework for Symmetric Property Estimation. CoRR abs/2003.00844 (2020) - [i46]Nima Anari, Moses Charikar, Kirankumar Shiragur, Aaron Sidford:
The Bethe and Sinkhorn Permanents of Low Rank Matrices and Implications for Profile Maximum Likelihood. CoRR abs/2004.02425 (2020) - [i45]Joshua Brakensiek, Moses Charikar, Aviad Rubinstein:
A Simple Sublinear Algorithm for Gap Edit Distance. CoRR abs/2007.14368 (2020) - [i44]Xian Wu, Moses Charikar:
Nearest Neighbor Search for Hyperbolic Embeddings. CoRR abs/2009.00836 (2020) - [i43]Moses Charikar, Paul Liu:
Improved Algorithms for Edge Colouring in the W-Streaming Model. CoRR abs/2010.14560 (2020) - [i42]Nima Anari, Moses Charikar, Kirankumar Shiragur, Aaron Sidford:
Instance Based Approximations to Profile Maximum Likelihood. CoRR abs/2011.02761 (2020) - [i41]Moses Charikar, Michael Kapralov, Navid Nouri, Paris Siminelakis:
Kernel Density Estimation through Density Constrained Near Neighbor Search. CoRR abs/2011.06997 (2020) - [i40]Moses Charikar, Shivam Garg, Deborah M. Gordon, Kirankumar Shiragur:
A Model for Ant Trail Formation and its Convergence Properties. CoRR abs/2011.14722 (2020)
2010 – 2019
- 2019
- [c112]Moses Charikar, Vaggos Chatziafratis, Rad Niazadeh, Grigory Yaroslavtsev:
Hierarchical Clustering for Euclidean Data. AISTATS 2019: 2721-2730 - [c111]Hongyang Zhang, Vatsal Sharan, Moses Charikar, Yingyu Liang:
Recovery Guarantees For Quadratic Tensors With Sparse Observations. AISTATS 2019: 3322-3332 - [c110]Vladimir Braverman, Moses Charikar, William Kuszmaul, David P. Woodruff, Lin F. Yang:
The One-Way Communication Complexity of Dynamic Time Warping Distance. SoCG 2019: 16:1-16:15 - [c109]Moses Charikar, Paris Siminelakis:
Multi-resolution Hashing for Fast Pairwise Summations. FOCS 2019: 769-792 - [c108]Paris Siminelakis, Kexin Rong, Peter Bailis, Moses Charikar, Philip Alexander Levis:
Rehashing Kernel Evaluation in High Dimensions. ICML 2019: 5789-5798 - [c107]Moses Charikar, Kirankumar Shiragur, Aaron Sidford:
A General Framework for Symmetric Property Estimation. NeurIPS 2019: 12426-12436 - [c106]Moses Charikar, Vaggos Chatziafratis, Rad Niazadeh:
Hierarchical Clustering better than Average-Linkage. SODA 2019: 2291-2304 - [c105]Moses Charikar, Kirankumar Shiragur, Aaron Sidford:
Efficient profile maximum likelihood for universal symmetric property estimation. STOC 2019: 780-791 - [c104]Paul Liu, Austin R. Benson, Moses Charikar:
Sampling Methods for Counting Temporal Motifs. WSDM 2019: 294-302 - [e3]Moses Charikar, Edith Cohen:
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019. ACM 2019, ISBN 978-1-4503-6705-9 [contents] - [i39]Vladimir Braverman, Moses Charikar, William Kuszmaul, David P. Woodruff, Lin F. Yang:
The One-Way Communication Complexity of Dynamic Time Warping Distance. CoRR abs/1903.03520 (2019) - [i38]Moses Charikar, Kirankumar Shiragur, Aaron Sidford:
Efficient Profile Maximum Likelihood for Universal Symmetric Property Estimation. CoRR abs/1905.08448 (2019) - [i37]Raunak Kumar, Paul Liu, Moses Charikar, Austin R. Benson:
Retrieving Top Weighted Triangles in Graphs. CoRR abs/1910.00692 (2019) - 2018
- [c103]Moses Charikar, Yonatan Naamad, Jennifer Rexford, X. Kelvin Zou:
Multi-commodity Flow with In-Network Processing. ALGOCLOUD 2018: 73-101 - [c102]Arturs Backurs, Moses Charikar, Piotr Indyk, Paris Siminelakis:
Efficient Density Evaluation for Smooth Kernels. FOCS 2018: 615-626 - [c101]Moses Charikar, Shay Solomon:
Fully Dynamic Almost-Maximal Matching: Breaking the Polynomial Worst-Case Time Barrier. ICALP 2018: 33:1-33:14 - [c100]Moses Charikar, Ofir Geri, Michael P. Kim, William Kuszmaul:
On Estimating Edit Distance: Alignment, Dimension Reduction, and Embeddings. ICALP 2018: 34:1-34:14 - [c99]Vaggos Chatziafratis, Rad Niazadeh, Moses Charikar:
Hierarchical Clustering with Structural Constraints. ICML 2018: 773-782 - [c98]Xian Wu, Moses Charikar, Vishnu Natchu:
Local Density Estimation in High Dimensions. ICML 2018: 5293-5301 - [c97]Jacob Steinhardt, Moses Charikar, Gregory Valiant:
Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers. ITCS 2018: 45:1-45:21 - [i36]Moses Charikar, Yonatan Naamad, Jimmy Wu:
On Finding Dense Common Subgraphs. CoRR abs/1802.06361 (2018) - [i35]Moses Charikar, Yonatan Naamad, Jennifer Rexford, X. Kelvin Zou:
Multi-Commodity Flow with In-Network Processing. CoRR abs/1802.09118 (2018) - [i34]Moses Charikar, Ofir Geri, Michael P. Kim, William Kuszmaul:
On Estimating Edit Distance: Alignment, Dimension Reduction, and Embeddings. CoRR abs/1804.09907 (2018) - [i33]Vaggos Chatziafratis, Rad Niazadeh, Moses Charikar:
Hierarchical Clustering with Structural Constraints. CoRR abs/1805.09476 (2018) - [i32]Moses Charikar, Paris Siminelakis:
Multi-Resolution Hashing for Fast Pairwise Summations. CoRR abs/1807.07635 (2018) - [i31]Moses Charikar, Vaggos Chatziafratis, Rad Niazadeh:
Hierarchical Clustering better than Average-Linkage. CoRR abs/1808.02227 (2018) - [i30]Moses Charikar, Paris Siminelakis:
Hashing-Based-Estimators for Kernel Density in High Dimensions. CoRR abs/1808.10530 (2018) - [i29]Xian Wu, Moses Charikar, Vishnu Natchu:
Local Density Estimation in High Dimensions. CoRR abs/1809.07471 (2018) - [i28]Paul Liu, Austin R. Benson, Moses Charikar:
A sampling framework for counting temporal motifs. CoRR abs/1810.00980 (2018) - [i27]Hongyang Zhang, Vatsal Sharan, Moses Charikar, Yingyu Liang:
Recovery Guarantees for Quadratic Tensors with Limited Observations. CoRR abs/1811.00148 (2018) - [i26]Moses Charikar, Vaggos Chatziafratis, Rad Niazadeh, Grigory Yaroslavtsev:
Hierarchical Clustering for Euclidean Data. CoRR abs/1812.10582 (2018) - 2017
- [j29]Qin Lv, William Josephson, Zhe Wang, Moses Charikar, Kai Li:
Intelligent Probing for Locality Sensitive Hashing: Multi-Probe LSH and Beyond. Proc. VLDB Endow. 10(12): 2021-2024 (2017) - [c96]Itai Ashlagi, Yossi Azar, Moses Charikar, Ashish Chiplunkar, Ofir Geri, Haim Kaplan, Rahul Makhijani, Yuyi Wang, Roger Wattenhofer:
Min-Cost Bipartite Perfect Matching with Delays. APPROX-RANDOM 2017: 1:1-1:20 - [c95]Yuchen Zhang, Percy Liang, Moses Charikar:
A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics. COLT 2017: 1980-2022 - [c94]Moses Charikar, Paris Siminelakis:
Hashing-Based-Estimators for Kernel Density in High Dimensions. FOCS 2017: 1032-1043 - [c93]Moses Charikar, Neha Gupta, Roy Schwartz:
Local Guarantees in Graph Cuts and Clustering. IPCO 2017: 136-147 - [c92]Moses Charikar, Vaggos Chatziafratis:
Approximate Hierarchical Clustering via Sparsest Cut and Spreading Metrics. SODA 2017: 841-854 - [c91]Moses Charikar, Jacob Steinhardt, Gregory Valiant:
Learning from untrusted data. STOC 2017: 47-60 - [i25]Yuchen Zhang, Percy Liang, Moses Charikar:
A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics. CoRR abs/1702.05575 (2017) - [i24]Jacob Steinhardt, Moses Charikar, Gregory Valiant:
Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers. CoRR abs/1703.04940 (2017) - [i23]Moses Charikar, Neha Gupta, Roy Schwartz:
Local Guarantees in Graph Cuts and Clustering. CoRR abs/1704.00355 (2017) - [i22]Moses Charikar, Shay Solomon:
Fully Dynamic Almost-Maximal Matching: Breaking the Polynomial Barrier for Worst-Case Time Bounds. CoRR abs/1711.06883 (2017) - 2016
- [c90]Moses Charikar, Yonatan Naamad, Anthony Wirth:
On Approximating Target Set Selection. APPROX-RANDOM 2016: 4:1-4:16 - [c89]Pranjal Awasthi, Moses Charikar, Ravishankar Krishnaswamy, Ali Kemal Sinop:
Spectral Embedding of k-Cliques, Graph Partitioning and k-Means. ITCS 2016: 301-310 - [c88]Jacob Steinhardt, Gregory Valiant, Moses Charikar:
Avoiding Imposters and Delinquents: Adversarial Crowdsourcing and Peer Prediction. NIPS 2016: 4439-4447 - [p1]Moses Charikar:
Top-k Frequent Item Maintenance over Streams. Data Stream Management 2016: 103-119 - [i21]Jacob Steinhardt, Gregory Valiant, Moses Charikar:
Avoiding Imposters and Delinquents: Adversarial Crowdsourcing and Peer Prediction. CoRR abs/1606.05374 (2016) - [i20]Moses Charikar, Vaggos Chatziafratis:
Approximate Hierarchical Clustering via Sparsest Cut and Spreading Metrics. CoRR abs/1609.09548 (2016) - [i19]Moses Charikar, Jacob Steinhardt, Gregory Valiant:
Learning from Untrusted Data. CoRR abs/1611.02315 (2016) - 2015
- [c87]Pranjal Awasthi, Moses Charikar, Kevin A. Lai, Andrej Risteski:
Label optimal regret bounds for online local learning. COLT 2015: 150-166 - [c86]Pranjal Awasthi, Moses Charikar, Ravishankar Krishnaswamy, Ali Kemal Sinop:
The Hardness of Approximation of Euclidean k-Means. SoCG 2015: 754-767 - [c85]Moses Samson Charikar:
Bypassing Worst Case Analysis: Tensor Decomposition and Clustering (Invited Talk). FSTTCS 2015: 1 - [c84]Pranjal Awasthi, Afonso S. Bandeira, Moses Charikar, Ravishankar Krishnaswamy, Soledad Villar, Rachel A. Ward:
Relax, No Need to Round: Integrality of Clustering Formulations. ITCS 2015: 191-200 - [i18]Pranjal Awasthi, Moses Charikar, Ravishankar Krishnaswamy, Ali Kemal Sinop:
The Hardness of Approximation of Euclidean k-means. CoRR abs/1502.03316 (2015) - [i17]Pranjal Awasthi, Moses Charikar, Kevin A. Lai, Andrej Risteski:
Label optimal regret bounds for online local learning. CoRR abs/1503.02193 (2015) - 2014
- [c83]Aditya Bhaskara, Moses Charikar, Aravindan Vijayaraghavan:
Uniqueness of Tensor Decompositions with Applications to Polynomial Identifiability. COLT 2014: 742-778 - [c82]Aditya Bhaskara, Moses Charikar, Ankur Moitra, Aravindan Vijayaraghavan:
Open Problem: Tensor Decompositions: Algorithms up to the Uniqueness Threshold? COLT 2014: 1280-1282 - [c81]Moses Charikar, Monika Henzinger, Huy L. Nguyen:
Online Bipartite Matching with Decomposable Weights. ESA 2014: 260-271 - [c80]Afonso S. Bandeira, Moses Charikar, Amit Singer, Andy Zhu:
Multireference alignment using semidefinite programming. ITCS 2014: 459-470 - [c79]Nikhil Bansal, Moses Charikar, Ravishankar Krishnaswamy, Shi Li:
Better Algorithms and Hardness for Broadcast Scheduling via a Discrepancy Approach. SODA 2014: 55-71 - [c78]Aditya Bhaskara, Moses Charikar, Ankur Moitra, Aravindan Vijayaraghavan:
Smoothed analysis of tensor decompositions. STOC 2014: 594-603 - [i16]Pranjal Awasthi, Afonso S. Bandeira, Moses Charikar, Ravishankar Krishnaswamy, Soledad Villar, Rachel A. Ward:
Relax, no need to round: integrality of clustering formulations. CoRR abs/1408.4045 (2014) - [i15]Moses Charikar, Monika Henzinger, Huy L. Nguyen:
Online Bipartite Matching with Decomposable Weights. CoRR abs/1409.2139 (2014) - 2013
- [i14]Aditya Bhaskara, Moses Charikar, Aravindan Vijayaraghavan:
Uniqueness of Tensor Decompositions with Applications to Polynomial Identifiability. CoRR abs/1304.8087 (2013) - [i13]