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.
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, 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.
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
-
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
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) - Advanced Reading and Research
CS 499P (Aut, Win, Spr) - Curricular Practical Training
CS 390A (Aut, Win, Spr) - Curricular Practical Training
CS 390B (Aut, Win, Spr) - Curricular Practical Training
CS 390C (Aut, Win, Spr) - Independent Project
CS 399 (Aut, Win, Spr) - Independent Project
CS 399P (Aut, Win, Spr) - Independent Work
CS 199 (Aut, Win, Spr) - Independent Work
CS 199P (Aut, Win, Spr) - Part-time Curricular Practical Training
CS 390D (Aut, Win, Spr) - Ph.D. Research Rotation
CME 391 (Aut, Win, Spr) - Senior Honors Thesis
MATH 197 (Win, Spr) - Senior Project
CS 191 (Aut, Win, Spr) - Supervised Undergraduate Research
CS 195 (Aut, Win, Spr) - Writing Intensive Senior Research Project
CS 191W (Aut, Win, Spr)
- Advanced Reading and Research
-
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)
- Artificial Intelligence: Principles and Techniques
Stanford Advisees
-
Doctoral Dissertation Reader (AC)
Mohammad Roghani -
Doctoral Dissertation Co-Advisor (AC)
Ruiquan Gao, Prasanna Ramakrishnan, Anna Thomas -
Master's Program Advisor
Andrew Lee, Anthony Maltsev, Pann Sripitak, Maggie Sun, Ramgopal Venkateswaran, Anthony Zhan -
Doctoral (Program)
Chirag Pabbaraju, Aidan Perreault
All Publications
-
Distributed algorithms from arboreal ants for the shortest path problem.
Proceedings of the National Academy of Sciences of the United States of America
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
-
A Characterization of List Learnability
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
2022
View details for DOI 10.1287/moor.2021.1221
View details for Web of Science ID 000745538900001
-
Multiway Online Correlated Selection
IEEE COMPUTER SOC. 2022: 1277-1284
View details for DOI 10.1109/FOCS52979.2021.00124
View details for Web of Science ID 000802209600114
-
Almost 3-Approximate Correlation Clustering in Constant Rounds
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
MICROTOME PUBLISHING. 2021
View details for Web of Science ID 000659893803030
-
Brief Announcement: A Randomness-efficient Massively Parallel Algorithm for Connectivity
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
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
ASSOC COMPUTING MACHINERY. 2020: 295–303
View details for DOI 10.1145/3336191.3371823
View details for Web of Science ID 000531489300037
-
Institutions Share Successes, Failures, and Advice in Moving the Diversity Needle
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
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
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
NEURAL INFORMATION PROCESSING SYSTEMS (NIPS). 2019
View details for Web of Science ID 000535866904013
-
Multi-commodity Flow with In-Network Processing
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
JMLR-JOURNAL MACHINE LEARNING RESEARCH. 2019
View details for Web of Science ID 000684034305094
-
Sampling Methods for Counting Temporal Motifs
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
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
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
MICROTOME PUBLISHING. 2019
View details for Web of Science ID 000509687902079
-
Recovery Guarantees For Quadratic Tensors With Sparse Observations
MICROTOME PUBLISHING. 2019
View details for Web of Science ID 000509687903039
-
Efficient Density Evaluation for Smooth Kernels
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
JMLR-JOURNAL MACHINE LEARNING RESEARCH. 2018
View details for Web of Science ID 000683379200080
-
Local Density Estimation in High Dimensions
JMLR-JOURNAL MACHINE LEARNING RESEARCH. 2018
View details for Web of Science ID 000683379205044
-
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
-
Top-k Frequent Item Maintenance over Streams
DATA STREAM MANAGEMENT: PROCESSING HIGH-SPEED DATA STREAMS
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
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
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
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
ASSOC COMPUTING MACHINERY. 2015: 191–200
View details for DOI 10.1145/2688073.2688116
View details for Web of Science ID 000571455400022
-
Online Bipartite Matching with Decomposable Weights
SPRINGER-VERLAG BERLIN. 2014: 260–71
View details for Web of Science ID 000345502900022
-
Smoothed Analysis of Tensor Decompositions
ASSOC COMPUTING MACHINERY. 2014: 594–603
View details for DOI 10.1145/2591796.2591881
View details for Web of Science ID 000485547000063
-
A Dependent LP-Rounding Approach for the k-Median Problem
SPRINGER-VERLAG BERLIN. 2012: 194–205
View details for Web of Science ID 000342761000017
-
On Quadratic Programming with a Ratio Objective
SPRINGER-VERLAG BERLIN. 2012: 109–20
View details for Web of Science ID 000342761000010
-
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
-
Tight Hardness Results for Minimizing Discrepancy
SIAM. 2011: 1607–14
View details for Web of Science ID 000296182400124
-
Near Linear Lower Bound for Dimension Reduction in l(1)
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
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
-
Vertex Sparsifiers and Abstract Rounding Algorithms
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
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
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
-
Improved Approximation Algorithms for Label Cover Problems
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
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
-
Near-Optimal Algorithms for Maximum Constraint Satisfaction Problems
SIAM. 2007: 62–68
View details for Web of Science ID 000281596700008
-
A Divide and Conquer Algorithm for d-Dimensional Arrangement
SIAM. 2007: 541–46
View details for Web of Science ID 000281596700058
-
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
-
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
-
Special issue on FOCS 2001 - Guest editor's foreword
JOURNAL OF COMPUTER AND SYSTEM SCIENCES
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
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
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
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
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
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
-
A Tight Threshold for Metric Ramsey Phenomena
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
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