Moses Charikar

Donald E. Knuth Professor and Professor, by courtesy, of Mathematics

Computer Science

Bio

Moses Charikar is the Donald E. Knuth professor of Computer Science at Stanford University. He obtained his PhD from Stanford in 2000, spent a year in the research group at Google, and was on the faculty at Princeton from 2001-2015.

His research interests include: efficient algorithmic techniques for processing, searching and indexing massive high-dimensional data sets; efficient algorithms for computational problems in high-dimensional statistics and optimization problems in machine learning; approximation algorithms for discrete optimization problems with provable guarantees; convex optimization approaches for non-convex combinatorial optimization problems; low-distortion embeddings of finite metric spaces.

His work won best paper awards at FOCS 2003, COLT 2017 and SODA 2024, the 10 year best paper award at VLDB 2017 and the 20 year test of time award at STOC 2022. He was jointly awarded the 2012 Paris Kanellakis Theory and Practice Award for his work on locality sensitive hashing, was named a Simons Investigator in theoretical computer science in 2014, and an ACM Fellow in 2021.

Academic Appointments

Professor, Computer Science
Professor (By courtesy), Mathematics
Member, Bio-X
Member, Wu Tsai Human Performance Alliance

Honors & Awards

ACM Fellow, ACM (2021)
Paris Kanellakis Theory and Practice Award, ACM (2012)
Simons Investigator in Theoretical Computer Science, Simons Foundation (2014)
Alfred P. Sloan Fellowship, Sloan Foundation (2003)
Distinguished Alumnus Award, IIT Bombay (2016)
20 year test of time award, STOC (2022)
10 year best paper award, VLDB (2017)
Best paper award, COLT (2017)
Best paper award, FOCS (2003)

Boards, Advisory Committees, Professional Organizations

Sloan Research Fellowships Selection Committee Member, Alfred P. Sloan Foundation (2022 - Present)
Godel Prize Committee, ACM SIGACT (2015 - 2018)
Scientific Advisory Board Member, Simons Institute for the Theory of Computing (2015 - 2018)
Director, Center for Computational Intractability (2012 - 2014)
Member, SIGACT Committee for the Advancement of Theoretical Computer Science (2011 - 2017)
Member, ACM-SIAM SODA steering committee (2010 - 2012)

Professional Education

B.Tech., Indian Institute of Technology, Bombay, Computer Science and Engineering (1995)
Ph.D., Stanford University, Computer Science (2000)

Patents

Moses Charikar, Deepa Ramakrishna. "United States Patent 10,282,863 Lossless Compression of Fragmented Image Data", EMC Corporation, May 7, 2019
Moses Charikar, Deepa Ramakrishna. "United States Patent 10,249,059 Lossless Compression of Fragmented Image Data", EMC Corporation, Apr 2, 2019
Moses Charikar, Deepa Ramakrishna. "United States Patent 10,114,839 Format Identification for Fragmented Data", EMC Corporation, Oct 30, 2018
Moses Charikar, Deepa Ramakrishna. "United States Patent 9,684,974 Lossless compression of fragmented image data", EMC Corporation, Jun 20, 2017
Moses Charikar, Deepa Ramakrishna. "United States Patent 9,558,566 Lossless compression of fragmented image data", EMC Corporation, Jan 31, 2017
Moses Charikar, Deepa Ramakrishna. "United States Patent 9,495,390 Format identification for fragmented image data", EMC Corporation, Nov 15, 2016
Moses Charikar, Deepa Ramakrishna. "United States Patent 9,384,218 Format identification for fragmented image data", EMC Corporation, Jul 5, 2016
Kai Li, Qin, Lv, Moses Charikar. "United States Patent 7966327B2 Similarity search system with compact data structures", The Trustees Of Princeton University, Jun 21, 2011
Ran Canetti, Moses Charikar, Sridhar Rajagopalan, S. Ravikumar, Amit Sahai, Andrew Tomkins. "United States Patent US7222362B1 Non-transferable anonymous credentials", IBM, May 22, 2007
Moses Charikar. "United States Patent US7158961 B1 Methods and apparatus for estimating similarity", Google, Inc, Dec 31, 2001

Contact

Academic
charikar@stanford.edu

University - Faculty Department: Computer Science Position: Professor

Additional Info

Mail Code: 9045
ORCID:
https://orcid.org/0000-0003-0807-3389

Current Research and Scholarly Interests

Efficient algorithmic techniques for processing, searching and indexing massive high-dimensional data sets; efficient algorithms for computational problems in high-dimensional statistics and optimization problems in machine learning; approximation algorithms for discrete optimization problems with provable guarantees; convex optimization approaches for non-convex combinatorial optimization problems; low-distortion embeddings of finite metric spaces.

2024-25 Courses

Artificial Intelligence: Principles and Techniques
CS 221 (Spr)
Design and Analysis of Algorithms
CS 161 (Win)
Machine Learning
CS 229, STATS 229 (Aut)
Independent Studies (15)
- Advanced Reading and Research
  CS 499 (Aut, Win, Spr, Sum)
- Advanced Reading and Research
  CS 499P (Aut, Win, Spr, Sum)
- Curricular Practical Training
  CS 390A (Aut, Win, Spr, Sum)
- Curricular Practical Training
  CS 390B (Aut, Win, Spr, Sum)
- Curricular Practical Training
  CS 390C (Aut, Win, Spr, Sum)
- Independent Project
  CS 399 (Aut, Win, Spr, Sum)
- Independent Project
  CS 399P (Aut, Win, Spr, Sum)
- Independent Work
  CS 199 (Aut, Win, Spr, Sum)
- Independent Work
  CS 199P (Aut, Win, Spr, Sum)
- Part-time Curricular Practical Training
  CS 390D (Aut, Win, Spr, Sum)
- Ph.D. Research Rotation
  CME 391 (Aut, Win, Spr, Sum)
- Senior Honors Thesis
  MATH 197 (Spr)
- Senior Project
  CS 191 (Aut, Win, Spr, Sum)
- Supervised Undergraduate Research
  CS 195 (Aut, Win, Spr, Sum)
- Writing Intensive Senior Research Project
  CS 191W (Aut, Win, Spr)
Prior Year Courses
2023-24 Courses
- Artificial Intelligence: Principles and Techniques
  CS 221 (Spr)
- Design and Analysis of Algorithms
  CS 161 (Win)
- Machine Learning
  CS 229, STATS 229 (Aut)
2022-23 Courses
- Artificial Intelligence: Principles and Techniques
  CS 221 (Spr)
- Design and Analysis of Algorithms
  CS 161 (Win)
- Machine Learning
  CS 229, STATS 229 (Aut)
2021-22 Courses
- Algorithmic Techniques for Big Data
  CS 368 (Spr)
- Design and Analysis of Algorithms
  CS 161 (Win)
- Dynamic Data Structures for Graphs
  CS 369Z (Aut)
- Machine Learning
  CS 229, STATS 229 (Aut)

Stanford Advisees

Doctoral Dissertation Reader (AC)
Mohammad Roghani
Doctoral Dissertation Advisor (AC)
Prasanna Ramakrishnan
Doctoral Dissertation Co-Advisor (AC)
Ruiquan Gao, Alireza Haqi, Anna Thomas
Master's Program Advisor
Anthony Maltsev, Maggie Sun, Ramgopal Venkateswaran, Anthony Zhan
Doctoral (Program)
Chirag Pabbaraju, Aidan Perreault, Prasanna Ramakrishnan

All Publications

Improved Approximations for Ultrametric Violation Distance Charikar, M., Gao, R., Woodruff, D. P. SIAM. 2024: 1704-1737

View details for Web of Science ID 001267398704013
A Quasi-Monte Carlo Data Structure for Smooth Kernel Evaluations Charikar, M., Kapralov, M., Waingarten, E., Woodruff, D. P. SIAM. 2024: 5118-5144

View details for Web of Science ID 001267398702033
Distributed algorithms from arboreal ants for the shortest path problem. Proceedings of the National Academy of Sciences of the United States of America Garg, S., Shiragur, K., Gordon, D. M., Charikar, M. 2023; 120 (6): e2207959120

Abstract

Colonies of the arboreal turtle ant create networks of trails that link nests and food sources on the graph formed by branches and vines in the canopy of the tropical forest. Ants put down a volatile pheromone on the edges as they traverse them. At each vertex, the next edge to traverse is chosen using a decision rule based on the current pheromone level. There is a bidirectional flow of ants around the network. In a previous field study, it was observed that the trail networks approximately minimize the number of vertices, thus solving a variant of the popular shortest path problem without any central control and with minimal computational resources. We propose a biologically plausible model, based on a variant of the reinforced random walk on a graph, which explains this observation and suggests surprising algorithms for the shortest path problem and its variants. Through simulations and analysis, we show that when the rate of flow of ants does not change, the dynamics converges to the path with the minimum number of vertices, as observed in the field. The dynamics converges to the shortest path when the rate of flow increases with time, so the colony can solve the shortest path problem merely by increasing the flow rate. We also show that to guarantee convergence to the shortest path, bidirectional flow and a decision rule dividing the flow in proportion to the pheromone level are necessary, but convergence to approximately short paths is possible with other decision rules.

View details for DOI 10.1073/pnas.2207959120

View details for PubMedID 36716366
Fast Algorithms for a New Relaxation of Optimal Transport Charikar, M., Chen, B., Re, C., Waingarten, E., Neu, G., Rosasco, L. JMLR-JOURNAL MACHINE LEARNING RESEARCH. 2023

View details for Web of Science ID 001222719105002
Single-Pass Streaming Algorithms for Correlation Clustering Behnezhad, S., Charikar, M., Ma, W., Tan, L., Bansal, N., Nagarajan SIAM. 2023: 819-849

View details for Web of Science ID 001288501200118
Simple, Scalable and Effective Clustering via One-Dimensional Projections Charikar, M., Henzinger, M., Hu, L., Voetsch, M., Waingarten, E., Oh, A., Neumann, T., Globerson, A., Saenko, K., Hardt, M., Levine, S. NEURAL INFORMATION PROCESSING SYSTEMS (NIPS). 2023

View details for Web of Science ID 001228825108037
A Characterization of List Learnability Charikar, M., Pabbaraju, C., Servedio, R. A., Saha, B. ASSOC COMPUTING MACHINERY. 2023: 1713-1726

View details for DOI 10.1145/3564246.3585190

View details for Web of Science ID 001064640700139
p Local Density Estimation in High Dimensions MATHEMATICS OF OPERATIONS RESEARCH Wu, X., Charikar, M., Natchu, V. 2022

View details for DOI 10.1287/moor.2021.1221

View details for Web of Science ID 000745538900001
Multiway Online Correlated Selection Blanc, G., Charikar, M., IEEE COMP SOC IEEE COMPUTER SOC. 2022: 1277-1284

View details for DOI 10.1109/FOCS52979.2021.00124

View details for Web of Science ID 000802209600114
Metric Distortion Bounds for Randomized Social Choice Charikar, M., Ramakrishnan, P., Naor, J., Buchbinder, N. SIAM. 2022: 2986-3004

View details for Web of Science ID 001278367000020
Near-Optimal Explainable <i>k</i>-Means for All Dimensions Charikar, M., Hu, L., Naor, J., Buchbinder, N. SIAM. 2022: 2580-2606

View details for Web of Science ID 001278367000004
On the Efficient Implementation of High Accuracy Optimality of Profile Maximum Likelihood Charikar, M., Jiang, Z., Shiragur, K., Sidford, A., Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., Oh, A. NEURAL INFORMATION PROCESSING SYSTEMS (NIPS). 2022

View details for Web of Science ID 001202259106035
Almost 3-Approximate Correlation Clustering in Constant Rounds Behnezhad, S., Charikar, M., Ma, W., Tan, L., IEEE Comp Soc IEEE COMPUTER SOC. 2022: 720-731

View details for DOI 10.1109/FOCS54457.2022.00074

View details for Web of Science ID 000909382900066
Approximation Algorithms for Orthogonal Non-negative Matrix Factorization Charikar, M., Hu, L., Banerjee, A., Fukumizu, K. MICROTOME PUBLISHING. 2021

View details for Web of Science ID 000659893803030
The Bethe and Sinkhorn Permanents of Low Rank Matrices and Implications for Profile Maximum Likelihood Anari, N., Charikar, M., Shiragur, K., Sidford, A., Belkin, M., Kpotufe, S. JMLR-JOURNAL MACHINE LEARNING RESEARCH. 2021: 93-158

View details for Web of Science ID 001230209300004
Improved Algorithms for Edge Colouring in the W-Streaming Model Charikar, M., Liu, P., King, Le, H. V. SIAM. 2021: 181-183

View details for Web of Science ID 001284362900013
Improved Algorithms for Edge Colouring in the W-Streaming Model Charikar, M., Liu, P., Farach-Colton, M., Storandt, S. SIAM. 2021

View details for Web of Science ID 001283952900013
Brief Announcement: A Randomness-efficient Massively Parallel Algorithm for Connectivity Charikar, M., Ma, W., Tan, L., ACM ASSOC COMPUTING MACHINERY. 2021: 431-433

View details for DOI 10.1145/3465084.3467951

View details for Web of Science ID 000744439800044
CoopStore: Optimizing Precomputed Summaries for Aggregation PROCEEDINGS OF THE VLDB ENDOWMENT Gan, E., Bailis, P., Charikar, M. 2020; 13 (11): 2174–87

View details for DOI 10.14778/3407790.3407817

View details for Web of Science ID 000573965600027
Retrieving Top Weighted Triangles in Graphs Kumar, R., Liu, P., Charikar, M., Benson, A. R., ACM ASSOC COMPUTING MACHINERY. 2020: 295–303

View details for DOI 10.1145/3336191.3371823

View details for Web of Science ID 000531489300037
Adaptive Discrete Phase Retrieval Charikar, M., Wu, X., Ye, Y., Farach-Colton, M., Gortz, I. L. SIAM. 2020: 47-56

View details for Web of Science ID 001284364600015
Instance Based Approximations to Profile Maximum Likelihood Anari, N., Charikar, M., Shiragur, K., Sidford, A., Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M. F., Lin, H. NEURAL INFORMATION PROCESSING SYSTEMS (NIPS). 2020

View details for Web of Science ID 001207696401012
Institutions Share Successes, Failures, and Advice in Moving the Diversity Needle Garcia, D., Charikar, M., Hearn, E., Lazowska, E., Reynolds, J., ASSOC COMP MACHINERY ASSOC COMPUTING MACHINERY. 2020: 331-332

View details for DOI 10.1145/3328778.3366976

View details for Web of Science ID 000810169400056
Unconditional Lower Bounds for Adaptive Massively Parallel Computation Charikar, M., Ma, W., Tan, L., ACM ASSOC COMPUTING MACHINERY. 2020: 141-151

View details for DOI 10.1145/3350755.3400230

View details for Web of Science ID 000744436200012
Kernel Density Estimation through Density Constrained Near Neighbor Search Charikar, M., Kapralov, M., Nouri, N., Siminelakis, P., IEEE IEEE. 2020: 172-183

View details for DOI 10.1109/FOCS46700.2020.00025

View details for Web of Science ID 000652333400017
A General Framework for Symmetric Property Estimation Charikar, M., Shiragur, K., Sidford, A., Wallach, H., Larochelle, H., Beygelzimer, A., d'Alche-Buc, F., Fox, E., Garnett, R. NEURAL INFORMATION PROCESSING SYSTEMS (NIPS). 2019

View details for Web of Science ID 000535866904013
Hierarchical Clustering better than Average-Linkage Charikar, M., Chatziafratis, V., Niazadeh, R., Chan, T. M. SIAM. 2019: 2291-2304

View details for Web of Science ID 001282151800043
Multi-commodity Flow with In-Network Processing Charikar, M., Naamad, Y., Rexford, J., Zou, X., Disser, Y., Verykios, V. S. SPRINGER INTERNATIONAL PUBLISHING AG. 2019: 73-101

View details for DOI 10.1007/978-3-030-19759-9_6

View details for Web of Science ID 000769657600006
Rehashing Kernel Evaluation in High Dimensions Siminelakis, P., Rong, K., Bailis, P., Charikar, M., Levis, P., Chaudhuri, K., Salakhutdinov, R. JMLR-JOURNAL MACHINE LEARNING RESEARCH. 2019

View details for Web of Science ID 000684034305094
Sampling Methods for Counting Temporal Motifs Liu, P., Benson, A. R., Charikar, M., ACM ASSOC COMPUTING MACHINERY. 2019: 294–302

View details for DOI 10.1145/3289600.3290988

View details for Web of Science ID 000482120400038
Efficient Profile Maximum Likelihood for Universal Symmetric Property Estimation Charikar, M., Shiragur, K., Sidford, A., Charikar, M., Cohen, E. ASSOC COMPUTING MACHINERY. 2019: 780–91

View details for DOI 10.1145/3313276.3316398

View details for Web of Science ID 000523199100070
Multi-Resolution Hashing for Fast Pairwise Summations Charikar, M., Siminelakis, P., IEEE IEEE COMPUTER SOC. 2019: 769–92

View details for DOI 10.1109/FOCS.2019.00051

View details for Web of Science ID 000510015300042
Hierarchical Clustering for Euclidean Data Charikar, M., Chatziafratis, V., Niazadeh, R., Yaroslavtsev, G., Chaudhuri, K., Sugiyama, M. MICROTOME PUBLISHING. 2019

View details for Web of Science ID 000509687902079
Recovery Guarantees For Quadratic Tensors With Sparse Observations Zhang, H., Sharan, V., Charikar, M., Liang, Y., Chaudhuri, K., Sugiyama, M. MICROTOME PUBLISHING. 2019

View details for Web of Science ID 000509687903039
Efficient Density Evaluation for Smooth Kernels Backurs, A., Charikar, M., Indyk, P., Siminelakis, P., Thorup, M. IEEE COMPUTER SOC. 2018: 615–26

View details for DOI 10.1109/FOCS.2018.00065

View details for Web of Science ID 000455014500056
Hierarchical Clustering with Structural Constraints Chatziafratis, V., Niazadeh, R., Charikar, M., Dy, J., Krause, A. JMLR-JOURNAL MACHINE LEARNING RESEARCH. 2018

View details for Web of Science ID 000683379200080
Local Density Estimation in High Dimensions Wu, X., Charikar, M., Natchu, V., Dy, J., Krause, A. JMLR-JOURNAL MACHINE LEARNING RESEARCH. 2018

View details for Web of Science ID 000683379205044
Hashing-Based-Estimators for Kernel Density in High Dimensions Charikar, M., Siminelakis, P., IEEE IEEE. 2017: 1032–43

View details for DOI 10.1109/FOCS.2017.99

View details for Web of Science ID 000417425300090
Learning from Untrusted Data Charikar, M., Steinhardt, J., Valiant, G., Hatami, H., McKenzie, P., King ASSOC COMPUTING MACHINERY. 2017: 47–60

View details for DOI 10.1145/3055399.3055491

View details for Web of Science ID 000440317600012
Approximate Hierarchical Clustering via Sparsest Cut and Spreading Metrics Charikar, M., Chatziafratis, V., ACM ASSOC COMPUTING MACHINERY. 2017: 841–54

View details for Web of Science ID 000426965800053
Local Guarantees in Graph Cuts and Clustering Charikar, M., Gupta, N., Schwartz, R., Eisenbrand, F., Koenemann, J. SPRINGER INTERNATIONAL PUBLISHING AG. 2017: 136–47

View details for DOI 10.1007/978-3-319-59250-3_12

View details for Web of Science ID 000428941700012
Top-k Frequent Item Maintenance over Streams DATA STREAM MANAGEMENT: PROCESSING HIGH-SPEED DATA STREAMS Charikar, M., Garofalakis, M., Gehrke, J., Rastogi, R. 2016: 103–19

View details for DOI 10.1007/978-3-540-28608-0_5

View details for Web of Science ID 000387880400005
Spectral Embedding of k-Cliques, Graph Partitioning and k-Means Awasthi, P., Charikar, M., Krishnaswamy, R., Sinop, A., ACM ASSOC COMPUTING MACHINERY. 2016: 301–10

View details for DOI 10.1145/2840728.2840751

View details for Web of Science ID 000390296900030
Avoiding Imposters and Delinquents: Adversarial Crowdsourcing and Peer Prediction Steinhardt, J., Valiant, G., Charikar, M., Lee, D. D., Sugiyama, M., Luxburg, U. V., Guyon, Garnett, R. NEURAL INFORMATION PROCESSING SYSTEMS (NIPS). 2016

View details for Web of Science ID 000458973703076
Targeted exploration and analysis of large cross-platform human transcriptomic compendia NATURE METHODS Zhu, Q., Wong, A. K., Krishnan, A., Aure, M. R., Tadych, A., Zhang, R., Corney, D. C., Greene, C. S., Bongo, L. A., Kristensen, V. N., Charikar, M., Li, K., Troyanskaya, O. G. 2015; 12 (3): 211-?

Abstract

We present SEEK (search-based exploration of expression compendia; http://seek.princeton.edu/), a query-based search engine for very large transcriptomic data collections, including thousands of human data sets from many different microarray and high-throughput sequencing platforms. SEEK uses a query-level cross-validation-based algorithm to automatically prioritize data sets relevant to the query and a robust search approach to identify genes, pathways and processes co-regulated with the query. SEEK provides multigene query searching with iterative metadata-based search refinement and extensive visualization-based analysis options.

View details for DOI 10.1038/NMETH.3249

View details for Web of Science ID 000350670300018

View details for PubMedID 25581801

View details for PubMedCentralID PMC4768301
Relax, No Need to Round: Integrality of Clustering Formulations Awasthi, P., Bandeira, A. S., Charikar, M., Krishnaswamy, R., Villar, S., Ward, R., ACM ASSOC COMPUTING MACHINERY. 2015: 191–200

View details for DOI 10.1145/2688073.2688116

View details for Web of Science ID 000571455400022
Smoothed Analysis of Tensor Decompositions Bhaskara, A., Charikar, M., Moitra, A., Vijayaraghavan, A., Assoc Comp Machinery ASSOC COMPUTING MACHINERY. 2014: 594–603

View details for DOI 10.1145/2591796.2591881

View details for Web of Science ID 000485547000063
Online Bipartite Matching with Decomposable Weights Charikar, M., Henzinger, M., Nguyen, H. L., Schulz, A. S., Wagner, D. SPRINGER-VERLAG BERLIN. 2014: 260–71

View details for Web of Science ID 000345502900022
On Quadratic Programming with a Ratio Objective Bhaskara, A., Charikar, M., Manokaran, R., Vijayaraghavan, A., Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. SPRINGER-VERLAG BERLIN. 2012: 109–20

View details for Web of Science ID 000342761000010
A Dependent LP-Rounding Approach for the k-Median Problem Charikar, M., Li, S., Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. SPRINGER-VERLAG BERLIN. 2012: 194–205

View details for Web of Science ID 000342761000017
Improved Approximation Algorithms for Label Cover Problems ALGORITHMICA Charikar, M., Hajiaghayi, M., Karloff, H. 2011; 61 (1): 190-206

View details for DOI 10.1007/s00453-010-9464-3

View details for Web of Science ID 000291481900011
BEATING THE RANDOM ORDERING IS HARD: EVERY ORDERING CSP IS APPROXIMATION RESISTANT SIAM JOURNAL ON COMPUTING Guruswami, V., Hastad, J., Manokaran, R., Raghavendra, P., Charikar, M. 2011; 40 (3): 878-914

View details for DOI 10.1137/090756144

View details for Web of Science ID 000292108900014
Tight Hardness Results for Minimizing Discrepancy Charikar, M., Newman, A., Nikolov, A., SIAM, ACM SIAM. 2011: 1607–14

View details for Web of Science ID 000296182400124
Near Linear Lower Bound for Dimension Reduction in l(1) Andoni, A., Charikar, M. S., Neiman, O., Nguyen, H. L., Ostrovsky, R. IEEE COMPUTER SOC. 2011: 315–23

View details for DOI 10.1109/FOCS.2011.87

View details for Web of Science ID 000298962700035
FITTING TREE METRICS: HIERARCHICAL CLUSTERING AND PHYLOGENY SIAM JOURNAL ON COMPUTING Ailon, N., Charikar, M. 2011; 40 (5): 1275-1291

View details for DOI 10.1137/100806886

View details for Web of Science ID 000296584900004
l(2)(2) Spreading Metrics for Vertex Ordering Problems ALGORITHMICA Charikar, M., Hajiaghayi, M. T., Karloff, H., Rao, S. 2010; 56 (4): 577-604

View details for DOI 10.1007/s00453-008-9191-1

View details for Web of Science ID 000273587100010
LOCAL GLOBAL TRADEOFFS IN METRIC EMBEDDINGS SIAM JOURNAL ON COMPUTING Charikar, M., Makarychev, K., Makarychev, Y. 2010; 39 (6): 2487-2512

View details for DOI 10.1137/070712080

View details for Web of Science ID 000277585000017
Vertex Sparsifiers and Abstract Rounding Algorithms Charikar, M., Leighton, T., Li, S., Moitra, A., IEEE Computer Society IEEE COMPUTER SOC. 2010: 265–74

View details for DOI 10.1109/FOCS.2010.32

View details for Web of Science ID 000287040100028
Detecting High Log-Densities - an O(n(1/4)) Approximation for Densest k-Subgraph Bhaskara, A., Charikar, M., Chlamtac, E., Feige, U., Vijayaraghavan, A., ACM ASSOC COMPUTING MACHINERY. 2010: 201–10

View details for Web of Science ID 000286949900021
Near-Optimal Algorithms for Maximum Constraint Satisfaction Problems ACM TRANSACTIONS ON ALGORITHMS Charikar, M., Makarychev, K., Makarychev, Y. 2009; 5 (3)

View details for DOI 10.1145/1541885.1541893

View details for Web of Science ID 000268471900008
Every Permutation CSP of arity 3 is Approximation Resistant PROCEEDINGS OF THE 24TH ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY Charikar, M., Guruswami, V., Manokaran, R. 2009: 62-73

View details for DOI 10.1109/CCC.2009.29

View details for Web of Science ID 000273015300008
Improved Approximation Algorithms for Label Cover Problems Charikar, M., Hajiaghayi, M., Karloff, H., Fiat, A., Sanders, P. SPRINGER-VERLAG BERLIN. 2009: 23-+

View details for Web of Science ID 000279102100003
MaxMin Allocation via Degree Lower-bounded Arborescences STOC'09: PROCEEDINGS OF THE 2009 ACM SYMPOSIUM ON THEORY OF COMPUTING Bateni, M., Charikar, M., Guruswami, V. 2009: 543-552

View details for Web of Science ID 000268182000060
Integrality Gaps for Sherali-Adams Relaxations STOC'09: PROCEEDINGS OF THE 2009 ACM SYMPOSIUM ON THEORY OF COMPUTING Charikar, M., Makarychev, K., Makarychev, Y. 2009: 283-292

View details for Web of Science ID 000268182000033
Aggregating Inconsistent Information: Ranking and Clustering JOURNAL OF THE ACM Ailon, N., Charikar, M., Newman, A. 2008; 55 (5)

View details for DOI 10.1145/1411509.1411513

View details for Web of Science ID 000260916000004
Online Multicast with Egalitarian Cost Sharing SPAA'08: PROCEEDINGS OF THE TWENTIETH ANNUAL SYMPOSIUM ON PARALLELISM IN ALGORITHMS AND ARCHITECTURES Charikar, M., Karloff, H., Mathieu, C., Naor, J. (., Saks, M. 2008: 70-76

View details for Web of Science ID 000266217200008
Sizing Sketches: A Rank-Based Analysis for Similarity Search SIGMETRICS'07: PROCEEDINGS OF THE 2007 INTERNATIONAL CONFERENCE ON MEASUREMENT & MODELING OF COMPUTER SYSTEMS Wang, Z., Dong, W., Josephson, W., Lv, Q., Charikar, M., Li, K. 2007; 35 (1): 157-168

View details for Web of Science ID 000266241500014
A Divide and Conquer Algorithm for d-Dimensional Arrangement Charikar, M., Makarychev, K., Makarychev, Y., SIAM/ACM SIAM. 2007: 541–46

View details for Web of Science ID 000281596700058
Near-Optimal Algorithms for Maximum Constraint Satisfaction Problems Charikar, M., Makarychev, K., Makarychev, Y., SIAM/ACM SIAM. 2007: 62–68

View details for Web of Science ID 000281596700008
On finding frequent elements in a data stream APPROXIMATION, RANDOMIZATION, AND COMBINATORIAL OPTIMIZATION: ALGORITHMS AND TECHNIQUES Charikar, M., Chen, K., Farach-Colton, M. 2007; 4627: 584-?

View details for Web of Science ID 000250357100042
On the advantage over random for maximum acyclic subgraph 48TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS Charikar, M., Makarychev, K., Makarychev, Y. 2007: 625-633

View details for DOI 10.1109/FOCS.2007.65

View details for Web of Science ID 000252161900057
Local global tradeoffs in metric embeddings 48TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS Charikar, M., Makarychev, K., Makarychev, Y. 2007: 713-723

View details for DOI 10.1109/FOCS.2007.64

View details for Web of Science ID 000252161900065
Improved Approximation for Directed Cut Problems STOC 07: PROCEEDINGS OF THE 39TH ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING Agarwal, A., Alon, N., Charikar, M. 2007: 671-680

View details for Web of Science ID 000267050000074
Special issue on FOCS 2001 - Guest editor's foreword JOURNAL OF COMPUTER AND SYSTEM SCIENCES Charikar, M. 2006; 72 (5): 785

View details for DOI 10.1016/j.jcss.2006.01.004

View details for Web of Science ID 000238163800001
On the integrality ratio for the asymmetric traveling salesman problem MATHEMATICS OF OPERATIONS RESEARCH Charikar, M., Goemans, M. X., Karloff, H. 2006; 31 (2): 245-252

View details for DOI 10.1287/moor.1060.0191

View details for Web of Science ID 000244423300003
l(2)(2) Spreading Metrics For Vertex Ordering Problems Charikar, M., Hajiaghayi, M., Karloff, H., Rao, S., SIAM/ACM SIAM. 2006: 1018-+

View details for DOI 10.1145/1109557.1109670

View details for Web of Science ID 000281596300113
Directed Metrics and Directed Graph Partitioning Problems Charikar, M., Makarychev, K., Makarychev, Y., SIAM/ACM SIAM. 2006: 51–60

View details for DOI 10.1145/1109557.1109564

View details for Web of Science ID 000281596300007
A Robust Maximum Completion Time Measure for Scheduling Charikar, M., Khuller, S., SIAM/ACM SIAM. 2006: 324-+

View details for DOI 10.1145/1109557.1109594

View details for Web of Science ID 000281596300037
Clustering with qualitative information JOURNAL OF COMPUTER AND SYSTEM SCIENCES Charikar, M., Guruswami, V., Wirth, A. 2005; 71 (3): 360-383

View details for DOI 10.1016/j.jcss.2004.10.012

View details for Web of Science ID 000232180200007
On the impossibility of dimension reduction in l(1) JOURNAL OF THE ACM Brinkman, B., Charikar, M. 2005; 52 (5): 766-788

View details for Web of Science ID 000232581700003
The smallest grammar problem 13th Annual ACM/SIAM Symposium on Discrete Algorithms Charikar, M., Lehman, E., Liu, D., Panigrahy, R., Prabhakaran, M., Sahai, A., Shelat, A. IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC. 2005: 2554–76

View details for DOI 10.1109/TIT.2005.850116

View details for Web of Science ID 000230151700018
Improved combinatorial algorithms for facility location problems SIAM JOURNAL ON COMPUTING Charikar, M., Guha, S. 2005; 34 (4): 803-824

View details for DOI 10.1137/S0097539701398594

View details for Web of Science ID 000229826500003
A Tight Threshold for Metric Ramsey Phenomena Charikar, M., Karagiozova, A., SIAM/ACM SIAM. 2005: 129–36

View details for Web of Science ID 000281595800015
Fitting tree metrics: Hierarchical clustering and phylogeny 46TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS Ailon, N., Charikar, M. 2005: 73-82

View details for Web of Science ID 000234538200007
Sampling bounds for stochastic optimization APPROXIMATION, RANDOMIZATION AND COMBINATORIAL OPTIMIZATION: ALGORITHMS AND TECHNIQUES Charikar, M., Chekuri, C., Pal, M. 2005; 3624: 257-269

View details for Web of Science ID 000232240900022
Resource optimization in QoS multicast routing of real-time multimedia IEEE-ACM TRANSACTIONS ON NETWORKING Charikar, M., Naor, J., Schieber, B. 2004; 12 (2): 340-348

View details for DOI 10.1109/TNET.2004.826288

View details for Web of Science ID 000220970400011
Clustering to minimize the sum of cluster diameters JOURNAL OF COMPUTER AND SYSTEM SCIENCES Charikar, M., Panigrahy, R. 2004; 68 (2): 417-441

View details for DOI 10.1016/j.jcss.2003.07.014

View details for Web of Science ID 000220144900010
Finding frequent items in data streams THEORETICAL COMPUTER SCIENCE Charikar, M., Chen, K., Farach-Colton, M. 2004; 312 (1): 3-15

View details for DOI 10.1016/S0304-3975(03)00400-6

View details for Web of Science ID 000188530600002
Incremental clustering and dynamic information retrieval SIAM JOURNAL ON COMPUTING Charikar, M., Chekuri, C., Feder, T., Motwani, R. 2004; 33 (6): 1417-1440

View details for DOI 10.1137/S0097539702418498

View details for Web of Science ID 000224348600006
The advantage of network coding for improving network throughput 2004 IEEE INFORMATION THEORY WORKSHOP, PROCEEDINGS Agarwal, A., Charikar, M. 2004: 247-249

View details for Web of Science ID 000226087200045
Minimizing wirelength in zero and bounded skew clock trees SIAM JOURNAL ON DISCRETE MATHEMATICS Charikar, M., Kleinberg, J., Kumar, R., Rajagopalan, S., Sahai, A., Tomkins, A. 2004; 17 (4): 582-595

View details for DOI 10.1137/S0895480199352622

View details for Web of Science ID 000222456900005
On the integrality ratio for asymmetric TSP 45TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS Charikar, M., Goemans, M. X., Karloff, H. 2004: 101-107

View details for Web of Science ID 000225221700011
Maximizing quadratic programs: extending Grothendieck's inequality 45TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS Charikar, M., Wirth, A. 2004: 54-60

View details for Web of Science ID 000225221700006
On the impossibility of dimension reduction in l(1) 44TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS Brinkman, B., Charikar, M. 2003: 514-523

View details for Web of Science ID 000186758200051
Clustering with qualitative information 44TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS Charikar, M., Guruswami, V., Wirth, A. 2003: 524-533

View details for Web of Science ID 000186758200052
A constant-factor approximation algorithm for the k-median problem 31st Annual ACM Symposium on Theory of Computing Charikar, M., Guha, S., Tardos, E., Shmoys, D. B. ACADEMIC PRESS INC ELSEVIER SCIENCE. 2002: 129–49

View details for DOI 10.1006/jcss.2002.1882

View details for Web of Science ID 000179011000006
Query strategies for priced information 32nd Annual ACM Symposium on Theory of Computing Charikar, M., Fagin, R., Guruswami, V., Kleinberg, J., Raghavan, P., Sahai, A. ACADEMIC PRESS INC ELSEVIER SCIENCE. 2002: 785–819

View details for DOI 10.1006/jcss.2002.1828

View details for Web of Science ID 000176720500004
Algorithms for capacitated vehicle routing SIAM JOURNAL ON COMPUTING Charikar, M., Khuller, S., Raghavachari, B. 2002; 31 (3): 665-682

View details for Web of Science ID 000174378200001
New algorithms for subset query, partial match, orthogonal range searching, and related problems AUTOMATA, LANGUAGES AND PROGRAMMING Charikar, M., Indyk, P., Panigrahy, R. 2002; 2380: 451-462

View details for Web of Science ID 000180069500039
Dimension reduction in the l(1) norm FOCS 2002: 43RD ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS Charikar, M., Sahai, A. 2002: 551-560

View details for Web of Science ID 000179945300055
On semidefinite programming relaxations for graph coloring and vertex cover PROCEEDINGS OF THE THIRTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS Charikar, M. 2002: 616-620

View details for Web of Science ID 000177258600081
Finding frequent items in data streams AUTOMATA, LANGUAGES AND PROGRAMMING Charikar, M., Chen, K., Farach-Colton, M. 2002; 2380: 693-703

View details for Web of Science ID 000180069500059
Delayed information and action in on-line algorithms INFORMATION AND COMPUTATION Albers, S., Charikar, M., Mitzenmacher, M. 2001; 170 (2): 135-152

View details for Web of Science ID 000172432000001
On page migration and other relaxed task systems THEORETICAL COMPUTER SCIENCE Bartal, Y., Charikar, M., Indyk, P. 2001; 268 (1): 43-66

View details for Web of Science ID 000171276300004
Algorithms for facility location problems with outliers 12th Annual ACM-SIAM Symposium on Discrete Algorithms Charikar, M., Khuller, S., Mount, D. M., Narasimhan, G. SIAM. 2001: 642–651

View details for Web of Science ID 000177257800089
Min-wise independent permutations 30th Annual ACM Symposium on Theory of Computing Broder, A. Z., Charikar, M., Frieze, A. M., Mitzenmacher, M. ACADEMIC PRESS INC ELSEVIER SCIENCE. 2000: 630–59

View details for Web of Science ID 000087652500008
On-line load balancing for related machines JOURNAL OF ALGORITHMS Berman, P., Charikar, M., Karpinski, M. 2000; 35 (1): 108-121

View details for Web of Science ID 000086054600006
Minimum outage transmission over fading channels with delay constraint IEEE International Conference on Communications (ICC 2000) Negi, R., Charikar, M., Cioffi, J. IEEE. 2000: 282–286

View details for Web of Science ID 000089018200056
Approximation algorithms for directed Steiner problems JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC Charikar, M., Chekuri, C., Cheung, T. Y., Dai, Z., Goel, A., Guha, S., Li, M. 1999; 33 (1): 73-91

View details for Web of Science ID 000082817100004
Minimizing wirelength in zero and bounded skew clock trees 10th Annual ACM-SIAM Symposium on Discrete Algorithms Charikar, M., Kleinberg, J., Kumar, R., Rajagopalan, S., Sahai, A., Tomkins, A. SIAM. 1999: 177–184

View details for Web of Science ID 000078494900021
Approximating a finite metric by a small number of tree metrics 39th Annual Symposium on Foundations of Computer Science Charikar, M., Chekuri, C., Goel, A., Guha, S., Plotkin, S. IEEE COMPUTER SOC. 1998: 379–388

View details for Web of Science ID 000077523900042
Delayed information and action in on-line algorithms 39th Annual Symposium on Foundations of Computer Science Albers, S., Charikar, M., Mitzenmacher, M. IEEE COMPUTER SOC. 1998: 71–80

View details for Web of Science ID 000077523900009
The finite capacity dial-a-ride problem 39th Annual Symposium on Foundations of Computer Science Charikar, M., Raghavachari, B. IEEE COMPUTER SOC. 1998: 458–467

View details for Web of Science ID 000077523900050
A derandomization using min-wise independent permutations 2nd International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM 98) Broder, A. Z., Charikar, M., Mitzenmacher, M. SPRINGER-VERLAG BERLIN. 1998: 15–24

View details for Web of Science ID 000082116300002
On-line load balancing for related machines 5th International Workshop on Algorithms and Data Structures (WADS 97) Berman, P., Charikar, M., Karpinski, M. SPRINGER-VERLAG BERLIN. 1997: 116–125

View details for Web of Science ID 000074043700010
Constrained TSP and low-power computing 5th International Workshop on Algorithms and Data Structures (WADS 97) Charikar, M., Motwani, R., Raghavan, P., Silverstein, C. SPRINGER-VERLAG BERLIN. 1997: 104–115

View details for Web of Science ID 000074043700009
On page migration and other relaxed task systems 8th Annual ACM/SIAM Symposium on Discrete Algorithms Bartal, Y., Charikar, M., Indyk, P. SIAM. 1997: 43–52

View details for Web of Science ID A1997BG97N00006