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


  • The smallest grammar problem IEEE TRANSACTIONS ON INFORMATION THEORY Charikar, M., Lehman, E., Liu, D., Panigrahy, R., Prabhakaran, M., Sahai, A., Shelat, A. 2005; 51 (7): 2554-2576
  • Improved combinatorial algorithms for facility location problems SIAM JOURNAL ON COMPUTING Charikar, M., Guha, S. 2005; 34 (4): 803-824
  • 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
  • Incremental clustering and dynamic information retrieval SIAM JOURNAL ON COMPUTING Charikar, M., Chekuri, C., Feder, T., Motwani, R. 2004; 33 (6): 1417-1440
  • A constant-factor approximation algorithm for the k-median problem JOURNAL OF COMPUTER AND SYSTEM SCIENCES Charikar, M., Guha, S., Tardos, E., Shmoys, D. B. 2002; 65 (1): 129-149
  • Query strategies for priced information JOURNAL OF COMPUTER AND SYSTEM SCIENCES Charikar, M., Fagin, R., Guruswami, V., Kleinberg, J., Raghavan, P., Sahai, A. 2002; 64 (4): 785-819
  • Algorithms for capacitated vehicle routing SIAM JOURNAL ON COMPUTING Charikar, M., Khuller, S., Raghavachari, B. 2002; 31 (3): 665-682
  • 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 PROCEEDINGS OF THE TWELFTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS Charikar, M., Khuller, S., Mount, D. M., Narasimhan, G. 2001: 642-651
  • Min-wise independent permutations JOURNAL OF COMPUTER AND SYSTEM SCIENCES Broder, A. Z., Charikar, M., Frieze, A. M., Mitzenmacher, M. 2000; 60 (3): 630-659
  • 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 ICC 2000: IEEE INTERNATIONAL CONFERENCE ON COMMUNICATIONS, CONFERENCE RECORD, VOLS 1-3 Negi, R., Charikar, M., Cioffi, J. 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 PROCEEDINGS OF THE TENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS Charikar, M., Kleinberg, J., Kumar, R., Rajagopalan, S., Sahai, A., Tomkins, A. 1999: 177-184
  • Approximating a finite metric by a small number of tree metrics 39TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS Charikar, M., Chekuri, C., Goel, A., Guha, S., Plotkin, S. 1998: 379-388
  • The finite capacity dial-a-ride problem 39TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS Charikar, M., Raghavachari, B. 1998: 458-467
  • A derandomization using min-wise independent permutations RANDOMIZATION AND APPROXIMATION TECHNIQUES IN COMPUTER SCIENCE Broder, A. Z., Charikar, M., Mitzenmacher, M. 1998; 1518: 15-24
  • On-line load balancing for related machines ALGORITHMS AND DATA STRUCTURES Berman, P., Charikar, M., Karpinski, M. 1997; 1272: 116-125
  • Constrained TSP and low-power computing ALGORITHMS AND DATA STRUCTURES Charikar, M., Motwani, R., Raghavan, P., Silverstein, C. 1997; 1272: 104-115