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. He is broadly interested in the design and analysis of algorithms with an emphasis on approximation algorithms for hard problems, metric embeddings and algorithmic techniques for big data. He won the best paper award at FOCS 2003 for his work on the impossibility of dimension reduction, the best paper award at COLT 2017 and the 10 year best paper award at VLDB 2017. He was jointly awarded the 2012 Paris Kanellakis Theory and Practice Award for his work on locality sensitive hashing, and was named a Simons Investigator in theoretical computer science in 2014.

Academic Appointments

Boards, Advisory Committees, Professional Organizations

  • Scientific Advisory Board member, Simons Institute for the Theory of Computing (2015 - Present)

Professional Education

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

Patents

  • 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

Additional Info

  • Mail Code: 9045

Current Research and Scholarly Interests

Approximation algorithms for discrete optimization problems with provable guarantees; convex optimization approaches for non-convex combinatorial optimization problems; 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; low-distortion embeddings of finite metric spaces.

All Publications

  • 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

  • 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

  • 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

  • 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

  • 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

  • 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

  • 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

  • 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

  • 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

  • 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

  • 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