
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. 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.
Honors & Awards
-
Paris Kanellakis Theory and Practice Award, ACM (2012)
-
Simons Investigator in Theoretical Computer Science, Simons Foundation (2014)
-
10 year best paper award, VLDB (2017)
-
Best paper award, COLT (2017)
-
Best paper award, FOCS (2003)
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
-
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
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.
2018-19 Courses
- Algorithmic Perspective on Machine Learning
CS 369L (Win) - Artificial Intelligence: Principles and Techniques
CS 221 (Spr) - Metric Embeddings and Algorithmic Applications
CS 369M (Aut) -
Independent Studies (15)
- Advanced Reading and Research
CS 499 (Aut, Win, Spr) - Advanced Reading and Research
CS 499P (Aut, Win, Spr) - Curricular Practical Training
CS 390A (Aut, Win, Sum) - Curricular Practical Training
CS 390B (Aut, Win, Sum) - Curricular Practical Training
CS 390C (Win, Spr, Sum) - Independent Project
CS 399 (Aut, Win, Spr) - Independent Project
CS 399P (Aut, Win, Spr) - Independent Work
CS 199 (Aut, Win) - Independent Work
CS 199P (Aut, Spr) - Part-Time CPT
CS 390T (Win) - Part-Time Curricular Practical Training
CS 390Q (Win) - Part-Time Curricular Practical Training
CS 390U (Spr) - Part-time Curricular Practical Training
CS 390D (Aut, Win) - Senior Project
CS 191 (Aut, Win, Spr) - Writing Intensive Senior Project (WIM)
CS 191W (Aut, Win)
- Advanced Reading and Research
-
Prior Year Courses
2017-18 Courses
- Algorithmic Techniques for Big Data
CS 368 (Spr) - Optimization and Algorithmic Paradigms
CS 261 (Win)
2016-17 Courses
- Design and Analysis of Algorithms
CS 161 (Aut) - Hierarchies of Integer Programming Relaxations
CS 369H (Spr)
2015-16 Courses
- Algorithmic Techniques for Big Data
CS 369G (Spr) - Theoretical Perspective on Machine Learning
CS 369L (Aut) - Topics in Analysis of Algorithms: Advanced Approximation Algorithms
CS 369A (Win)
- Algorithmic Techniques for Big Data
Stanford Advisees
-
Postdoctoral Faculty Sponsor
Clement Canonne, Yuanzhi Li, Rad Niazadeh, Avishay Tal -
Master's Program Advisor
Nitya Mani, William Marshall, Cameron Tew, Jingyi Zhong, Jiren Zhu
All Publications
-
Hashing-Based-Estimators for Kernel Density in High Dimensions
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
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
ASSOC COMPUTING MACHINERY. 2017: 841–54
View details for Web of Science ID 000426965800053
-
Local Guarantees in Graph Cuts and Clustering
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
-
Targeted exploration and analysis of large cross-platform human transcriptomic compendia
NATURE METHODS
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
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
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
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
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
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
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
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
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
2009: 283-292
View details for Web of Science ID 000268182000033
-
Aggregating Inconsistent Information: Ranking and Clustering
JOURNAL OF THE ACM
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
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
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
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
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
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
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
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
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
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
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
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
2005: 73-82
View details for Web of Science ID 000234538200007
-
Sampling bounds for stochastic optimization
APPROXIMATION, RANDOMIZATION AND COMBINATORIAL OPTIMIZATION: ALGORITHMS AND TECHNIQUES
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
2002: 616-620
View details for Web of Science ID 000177258600081
-
Finding frequent items in data streams
AUTOMATA, LANGUAGES AND PROGRAMMING
2002; 2380: 693-703
View details for Web of Science ID 000180069500059
-
Delayed information and action in on-line algorithms
INFORMATION AND COMPUTATION
2001; 170 (2): 135-152
View details for Web of Science ID 000172432000001
-
On page migration and other relaxed task systems
THEORETICAL COMPUTER SCIENCE
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
SIAM. 2001: 642–651
View details for Web of Science ID 000177257800089
-
Min-wise independent permutations
30th Annual ACM Symposium on Theory of Computing
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
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)
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
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
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
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
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
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)
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)
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)
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
SIAM. 1997: 43–52
View details for Web of Science ID A1997BG97N00006