Stop the war!Остановите войну!
for scientists:
default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDMoses Charikar
Moses Samson Charikar
Person information
- affiliation: Princeton University
- 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
- 2022
[c128]Soheil Behnezhad, Moses Charikar, Weiyun Ma, Li-Yang Tan:
Almost 3-Approximate Correlation Clustering in Constant Rounds. FOCS 2022: 720-731- [c127]Moses Charikar, Erik Waingarten:
Polylogarithmic Sketches for Clustering. ICALP 2022: 38:1-38:20 - [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 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 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]Afonso S. Bandeira, Moses Charikar, Amit Singer, Andy Zhu:
Multireference Alignment using Semidefinite Programming. CoRR abs/1308.5256 (2013) - [i12]Aditya Bhaskara, Moses Charikar, Ankur Moitra, Aravindan Vijayaraghavan:
Smoothed Analysis of Tensor Decompositions. CoRR abs/1311.3651 (2013) - 2012
- [c77]Aditya Bhaskara, Moses Charikar, Rajsekar Manokaran, Aravindan Vijayaraghavan:
On Quadratic Programming with a Ratio Objective. ICALP (1) 2012: 109-120 - [c76]Moses Charikar, Shi Li:
A Dependent LP-Rounding Approach for the k-Median Problem. ICALP (1) 2012: 194-205 - [c75]Wei Dong, Zhe Wang, Moses Charikar, Kai Li:
High-confidence near-duplicate image detection. ICMR 2012: 1 - [c74]Aditya Bhaskara, Moses Charikar, Aravindan Vijayaraghavan, Venkatesan Guruswami, Yuan Zhou:
Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph. SODA 2012: 388-405 - 2011
- [j28]Moses Charikar, MohammadTaghi Hajiaghayi, Howard J. Karloff:
Improved Approximation Algorithms for Label Cover Problems. Algorithmica 61(1): 190-206 (2011) - [j27]Venkatesan Guruswami, Johan Håstad, Rajsekar Manokaran, Prasad Raghavendra, Moses Charikar:
Beating the Random Ordering Is Hard: Every Ordering CSP Is Approximation Resistant. SIAM J. Comput. 40(3): 878-914 (2011) - [j26]Nir Ailon, Moses Charikar:
Fitting Tree Metrics: Hierarchical Clustering and Phylogeny. SIAM J. Comput. 40(5): 1275-1291 (2011) - [c73]Alexandr Andoni, Moses Charikar, Ofer Neiman, Huy L. Nguyen:
Near Linear Lower Bound for Dimension Reduction in L1. FOCS 2011: 315-323 - [c72]Moses Charikar, Alantha Newman, Aleksandar Nikolov:
Tight Hardness Results for Minimizing Discrepancy. SODA 2011: 1607-1614 - [c71]Wei Dong, Moses Charikar, Kai Li:
Efficient k-nearest neighbor graph construction for generic similarity measures. WWW 2011: 577-586 - [i11]Aditya Bhaskara, Moses Charikar, Rajsekar Manokaran, Aravindan Vijayaraghavan:
On Quadratic Programming with a Ratio Objective. CoRR abs/1101.1710 (2011) - [i10]Aditya Bhaskara, Moses Charikar, Venkatesan Guruswami, Aravindan Vijayaraghavan, Yuan Zhou:
Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph. CoRR abs/1110.1360 (2011) - [i9]Venkatesan Guruswami, Johan Håstad, Rajsekar Manokaran, Prasad Raghavendra, Moses Charikar:
Beating the Random Ordering is Hard: Every ordering CSP is approximation resistant. Electron. Colloquium Comput. Complex. TR11 (2011) - 2010
- [j25]Moses Charikar, Mohammad Taghi Hajiaghayi, Howard J. Karloff, Satish Rao:
l22 Spreading Metrics for Vertex Ordering Problems. Algorithmica 56(4): 577-604 (2010) - [j24]Moses Charikar, Konstantin Makarychev, Yury Makarychev:
Local Global Tradeoffs in Metric Embeddings. SIAM J. Comput. 39(6): 2487-2512 (2010) - [c70]Moses Charikar, Tom Leighton, Shi Li, Ankur Moitra:
Vertex Sparsifiers and Abstract Rounding Algorithms. FOCS 2010: 265-274 - [c69]Aditya Bhaskara, Moses Charikar, Eden Chlamtac, Uriel Feige, Aravindan Vijayaraghavan:
Detecting high log-densities: an O(n1/4) approximation for densest k-subgraph. STOC 2010: 201-210 - [e2]Moses Charikar:
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010. SIAM 2010, ISBN 978-0-89871-701-3 [contents] - [i8]Aditya Bhaskara, Moses Charikar, Eden Chlamtac, Uriel Feige, Aravindan Vijayaraghavan:
Detecting High Log-Densities -- an O(n^1/4) Approximation for Densest k-Subgraph. CoRR abs/1001.2891 (2010) - [i7]