Bio


Moses Charikar is a 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-2014. 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. His work on dimension reduction won the best paper award at FOCS 2003. He was 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

All Publications


  • 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
  • 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
  • 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)
  • 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
  • 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
  • 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
  • Aggregating Inconsistent Information: Ranking and Clustering JOURNAL OF THE ACM Ailon, N., Charikar, M., Newman, A. 2008; 55 (5)
  • 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
  • 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-?
  • 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
  • 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
  • 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
  • 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
  • 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
  • Clustering with qualitative information JOURNAL OF COMPUTER AND SYSTEM SCIENCES Charikar, M., Guruswami, V., Wirth, A. 2005; 71 (3): 360-383
  • On the impossibility of dimension reduction in l(1) JOURNAL OF THE ACM Brinkman, B., Charikar, M. 2005; 52 (5): 766-788
  • 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
  • Improved combinatorial algorithms for facility location problems SIAM JOURNAL ON COMPUTING Charikar, M., Guha, S. 2005; 34 (4): 803-824
  • Fitting tree metrics: Hierarchical clustering and phylogeny 46TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS Ailon, N., Charikar, M. 2005: 73-82
  • Sampling bounds for stochastic optimization APPROXIMATION, RANDOMIZATION AND COMBINATORIAL OPTIMIZATION: ALGORITHMS AND TECHNIQUES Charikar, M., Chekuri, C., Pal, M. 2005; 3624: 257-269
  • 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
  • Clustering to minimize the sum of cluster diameters JOURNAL OF COMPUTER AND SYSTEM SCIENCES Charikar, M., Panigrahy, R. 2004; 68 (2): 417-441
  • Finding frequent items in data streams THEORETICAL COMPUTER SCIENCE Charikar, M., Chen, K., Farach-Colton, M. 2004; 312 (1): 3-15
  • Incremental clustering and dynamic information retrieval SIAM JOURNAL ON COMPUTING Charikar, M., Chekuri, C., Feder, T., Motwani, R. 2004; 33 (6): 1417-1440
  • The advantage of network coding for improving network throughput 2004 IEEE INFORMATION THEORY WORKSHOP, PROCEEDINGS Agarwal, A., Charikar, M. 2004: 247-249
  • 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
  • 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
  • Maximizing quadratic programs: extending Grothendieck's inequality 45TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS Charikar, M., Wirth, A. 2004: 54-60
  • 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
  • Clustering with qualitative information 44TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS Charikar, M., Guruswami, V., Wirth, A. 2003: 524-533
  • 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
  • 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
  • Algorithms for capacitated vehicle routing SIAM JOURNAL ON COMPUTING Charikar, M., Khuller, S., Raghavachari, B. 2002; 31 (3): 665-682
  • 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
  • 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
  • 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
  • Finding frequent items in data streams AUTOMATA, LANGUAGES AND PROGRAMMING Charikar, M., Chen, K., Farach-Colton, M. 2002; 2380: 693-703
  • Delayed information and action in on-line algorithms INFORMATION AND COMPUTATION Albers, S., Charikar, M., Mitzenmacher, M. 2001; 170 (2): 135-152
  • On page migration and other relaxed task systems THEORETICAL COMPUTER SCIENCE Bartal, Y., Charikar, M., Indyk, P. 2001; 268 (1): 43-66
  • 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
  • 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
  • On-line load balancing for related machines JOURNAL OF ALGORITHMS Berman, P., Charikar, M., Karpinski, M. 2000; 35 (1): 108-121
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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