Moses Charikar

Aditya Bhaskara, Moses Charikar, Aravindan Vijayaraghavan: Uniqueness of Tensor Decompositions with Applications to Polynomial Identifiability. CoRR abs/1304.8087 (2013)

Aditya Bhaskara, Moses Charikar, Rajsekar Manokaran, Aravindan Vijayaraghavan: On Quadratic Programming with a Ratio Objective. ICALP (1) 2012: 109-120

Moses Charikar, Shi Li: A Dependent LP-Rounding Approach for the k-Median Problem. ICALP (1) 2012: 194-205

Wei Dong, Zhe Wang, Moses Charikar, Kai Li: High-confidence near-duplicate image detection. ICMR 2012: 1

Aditya Bhaskara, Moses Charikar, Aravindan Vijayaraghavan, Venkatesan Guruswami, Yuan Zhou: Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph. SODA 2012: 388-405

Moses Charikar, MohammadTaghi Hajiaghayi, Howard J. Karloff: Improved Approximation Algorithms for Label Cover Problems. Algorithmica 61(1): 190-206 (2011)

Venkatesan Guruswami, Johan Håstad, Rajsekar Manokaran, Prasad Raghavendra, Moses Charikar: Beating the Random Ordering Is Hard: Every Ordering CSP Is Approximation Resistant. SIAM J. Comput. 40(3): 878-914 (2011)

Nir Ailon, Moses Charikar: Fitting Tree Metrics: Hierarchical Clustering and Phylogeny. SIAM J. Comput. 40(5): 1275-1291 (2011)

Alexandr Andoni, Moses Charikar, Ofer Neiman, Huy L. Nguyen: Near Linear Lower Bound for Dimension Reduction in L1. FOCS 2011: 315-323

Moses Charikar, Alantha Newman, Aleksandar Nikolov: Tight Hardness Results for Minimizing Discrepancy. SODA 2011: 1607-1614

Wei Dong, Moses Charikar, Kai Li: Efficient k-nearest neighbor graph construction for generic similarity measures. WWW 2011: 577-586

Aditya Bhaskara, Moses Charikar, Rajsekar Manokaran, Aravindan Vijayaraghavan: On Quadratic Programming with a Ratio Objective. CoRR abs/1101.1710 (2011)

Aditya Bhaskara, Moses Charikar, Venkatesan Guruswami, Aravindan Vijayaraghavan, Yuan Zhou: Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph. CoRR abs/1110.1360 (2011)

Venkatesan Guruswami, Johan Håstad, Rajsekar Manokaran, Prasad Raghavendra, Moses Charikar: Beating the Random Ordering is Hard: Every ordering CSP is approximation resistant. Electronic Colloquium on Computational Complexity (ECCC) 18: 27 (2011)

Moses Charikar, Mohammad Taghi Hajiaghayi, Howard J. Karloff, Satish Rao: l₂² Spreading Metrics for Vertex Ordering Problems. Algorithmica 56(4): 577-604 (2010)

Moses Charikar, Konstantin Makarychev, Yury Makarychev: Local Global Tradeoffs in Metric Embeddings. SIAM J. Comput. 39(6): 2487-2512 (2010)

Moses Charikar, Tom Leighton, Shi Li, Ankur Moitra: Vertex Sparsifiers and Abstract Rounding Algorithms. FOCS 2010: 265-274

Aditya Bhaskara, Moses Charikar, Eden Chlamtac, Uriel Feige, Aravindan Vijayaraghavan: Detecting high log-densities: an O(n^1/4) approximation for densest k-subgraph. STOC 2010: 201-210

Moses Charikar (Ed.): Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010. SIAM 2010

Aditya Bhaskara, Moses Charikar, Eden Chlamtac, Uriel Feige, Aravindan Vijayaraghavan: Detecting High Log-Densities -- an O(n^1/4) Approximation for Densest k-Subgraph. CoRR abs/1001.2891 (2010)

Prahladh Harsha, Moses Charikar, Matthew Andrews, Sanjeev Arora, Subhash Khot, Dana Moshkovitz, Lisa Zhang, Ashkan Aazami, Dev Desai, Igor Gorodezky, Geetha Jagannathan, Alexander S. Kulikov, Darakhshan J. Mir, Alantha Newman, Aleksandar Nikolov, David Pritchard, Gwen Spencer: Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes). CoRR abs/1002.3864 (2010)

Moses Charikar, Tom Leighton, Shi Li, Ankur Moitra: Vertex Sparsifiers and Abstract Rounding Algorithms. CoRR abs/1006.4536 (2010)

Moses Charikar, Konstantin Makarychev, Yury Makarychev: Near-optimal algorithms for maximum constraint satisfaction problems. ACM Transactions on Algorithms 5(3) (2009)

Moses Charikar, Venkatesan Guruswami, Rajsekar Manokaran: Every Permutation CSP of arity 3 is Approximation Resistant. IEEE Conference on Computational Complexity 2009: 62-73

Moses Charikar, MohammadTaghi Hajiaghayi, Howard J. Karloff: Improved Approximation Algorithms for Label Cover Problems. ESA 2009: 23-34

Moses Charikar, Konstantin Makarychev, Yury Makarychev: Integrality gaps for Sherali-Adams relaxations. STOC 2009: 283-292

MohammadHossein Bateni, Moses Charikar, Venkatesan Guruswami: MaxMin allocation via degree lower-bounded arborescences. STOC 2009: 543-552

Nir Ailon, Moses Charikar, Alantha Newman: Aggregating inconsistent information: Ranking and clustering. J. ACM 55(5) (2008)

Wei Dong, Zhe Wang, William Josephson, Moses Charikar, Kai Li: Modeling LSH for performance tuning. CIKM 2008: 669-678

Wei Dong, Zhe Wang, Moses Charikar, Kai Li: Efficiently matching sets of features with random histograms. ACM Multimedia 2008: 179-188

Wei Dong, Moses Charikar, Kai Li: Asymmetric distance estimation with sketches for similarity search in high-dimensional spaces. SIGIR 2008: 123-130

Moses Charikar, Howard J. Karloff, Claire Mathieu, Joseph Naor, Michael E. Saks: Online multicast with egalitarian cost sharing. SPAA 2008: 70-76

Zhe Wang, William K. Josephson, Qin Lv, Moses Charikar, Kai Li: Filtering Image Spam with Near-Duplicate Detection. CEAS 2007

Moses Charikar, Konstantin Makarychev, Yury Makarychev: On the Advantage over Random for Maximum Acyclic Subgraph. FOCS 2007: 625-633

Moses Charikar, Konstantin Makarychev, Yury Makarychev: Local Global Tradeoffs in Metric Embeddings. FOCS 2007: 713-723

Zhe Wang, Wei Dong, William Josephson, Qin Lv, Moses Charikar, Kai Li: Sizing sketches: a rank-based analysis for similarity search. SIGMETRICS 2007: 157-168

Moses Charikar, Konstantin Makarychev, Yury Makarychev: Near-optimal algorithms for maximum constraint satisfaction problems. SODA 2007: 62-68

Moses Charikar, Konstantin Makarychev, Yury Makarychev: A divide and conquer algorithm for d-dimensional arrangement. SODA 2007: 541-546

Amit Agarwal, Noga Alon, Moses Charikar: Improved approximation for directed cut problems. STOC 2007: 671-680

Qin Lv, William Josephson, Zhe Wang, Moses Charikar, Kai Li: Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search . VLDB 2007: 950-961

Moses Charikar, Klaus Jansen, Omer Reingold, José D. P. Rolim (Eds.): Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 10th International Workshop, APPROX 2007, and 11th International Workshop, RANDOM 2007, Princeton, NJ, USA, August 20-22, 2007, Proceedings. Lecture Notes in Computer Science 4627, Springer 2007, isbn 978-3-540-74207-4

Moses Charikar, Konstantin Makarychev, Yury Makarychev: On the Advantage over Random for Maximum Acyclic Subgraph. Electronic Colloquium on Computational Complexity (ECCC) 14(104) (2007)

Moses Charikar, Konstantin Makarychev, Yury Makarychev: Local Global Tradeoffs in Metric Embeddings. Electronic Colloquium on Computational Complexity (ECCC) 14(108) (2007)

Moses Charikar: Guest editor's foreword. J. Comput. Syst. Sci. 72(5): 785 (2006)

Moses Charikar, Michel X. Goemans, Howard J. Karloff: On the Integrality Ratio for the Asymmetric Traveling Salesman Problem. Math. Oper. Res. 31(2): 245-252 (2006)

Moses Charikar, Robert Krauthgamer: Embedding the Ulam metric into l₁. Theory of Computing 2(1): 207-224 (2006)

Qin Lv, William Josephson, Zhe Wang, Moses Charikar, Kai Li: Ferret: a toolkit for content-based similarity search of feature-rich data. EuroSys 2006: 317-330

Qin Lv, William Josephson, Zhe Wang, Moses Charikar, Kai Li: Efficient filtering with sketches in the ferret toolkit. Multimedia Information Retrieval 2006: 279-288

Moses Charikar, Konstantin Makarychev, Yury Makarychev: Directed metrics and directed graph partitioning problems. SODA 2006: 51-60

Moses Charikar, Samir Khuller: A robust maximum completion time measure for scheduling. SODA 2006: 324-333

Moses Charikar, Mohammad Taghi Hajiaghayi, Howard J. Karloff, Satish Rao: l²₂ spreading metrics for vertex ordering problems. SODA 2006: 1018-1027

Moses Charikar, Konstantin Makarychev, Yury Makarychev: Near-optimal algorithms for unique games. STOC 2006: 205-214

Moses Charikar, Konstantin Makarychev, Yury Makarychev: Approximation Algorithm for the Max k-CSP Problem. Electronic Colloquium on Computational Complexity (ECCC) 13(063) (2006)

Moses Charikar, Konstantin Makarychev, Yury Makarychev: Note on MAX 2SAT. Electronic Colloquium on Computational Complexity (ECCC) 13(064) (2006)

Bo Brinkman, Moses Charikar: On the impossibility of dimension reduction in l₁. J. ACM 52(5): 766-788 (2005)

Moses Charikar, Venkatesan Guruswami, Anthony Wirth: Clustering with qualitative information. J. Comput. Syst. Sci. 71(3): 360-383 (2005)

Moses Charikar, Sudipto Guha: Improved Combinatorial Algorithms for Facility Location Problems. SIAM J. Comput. 34(4): 803-824 (2005)

Moses Charikar, Eric Lehman, Ding Liu, Rina Panigrahy, Manoj Prabhakaran, Amit Sahai, Abhi Shelat: The smallest grammar problem. IEEE Transactions on Information Theory 51(7): 2554-2576 (2005)

Moses Charikar, Chandra Chekuri, Martin Pál: Sampling Bounds for Stochastic Optimization. APPROX-RANDOM 2005: 257-269

Nir Ailon, Moses Charikar: Fitting tree metrics: Hierarchical clustering and Phylogeny. FOCS 2005: 73-82

Moses Charikar, Adriana Karagiozova: A tight threshold for metric Ramsey phenomena. SODA 2005: 129-136

Nikhil Bansal, Moses Charikar, Sanjeev Khanna, Joseph Naor: Approximating the average response time in broadcast scheduling. SODA 2005: 215-221

Moses Charikar, Adriana Karagiozova: On non-uniform multicommodity buy-at-bulk network design. STOC 2005: 176-182

Amit Agarwal, Moses Charikar, Konstantin Makarychev, Yury Makarychev: O(sqrt(log n)) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems. STOC 2005: 573-581

Nir Ailon, Moses Charikar, Alantha Newman: Aggregating inconsistent information: ranking and clustering. STOC 2005: 684-693

Moses Charikar, Rina Panigrahy: Clustering to minimize the sum of cluster diameters. J. Comput. Syst. Sci. 68(2): 417-441 (2004)

Moses Charikar, Chandra Chekuri, Tomás Feder, Rajeev Motwani: Incremental Clustering and Dynamic Information Retrieval. SIAM J. Comput. 33(6): 1417-1440 (2004)

Moses Charikar, Jon M. Kleinberg, Ravi Kumar, Sridhar Rajagopalan, Amit Sahai, Andrew Tomkins: Minimizing Wirelength in Zero and Bounded Skew Clock Trees. SIAM J. Discrete Math. 17(4): 582-595 (2004)

Moses Charikar, Kevin Chen, Martin Farach-Colton: Finding frequent items in data streams. Theor. Comput. Sci. 312(1): 3-15 (2004)

Moses Charikar, Joseph Naor, Baruch Schieber: Resource optimization in QoS multicast routing of real-time multimedia. IEEE/ACM Trans. Netw. 12(2): 340-348 (2004)

Qin Lv, Moses Charikar, Kai Li: Image similarity search with compact data structures. CIKM 2004: 208-217

Moses Charikar, Anthony Wirth: Maximizing Quadratic Programs: Extending Grothendieck's Inequality. FOCS 2004: 54-60

Moses Charikar, Michel X. Goemans, Howard J. Karloff: On the Integrality Ratio for Asymmetric TSP. FOCS 2004: 101-107

Andrei Z. Broder, Moses Charikar, Michael Mitzenmacher: A derandomization using min-wise independent permutations. J. Discrete Algorithms 1(1): 11-20 (2003)

Bo Brinkman, Moses Charikar: On the Impossibility of Dimension Reduction in l₁. FOCS 2003: 514-523

Moses Charikar, Venkatesan Guruswami, Anthony Wirth: Clustering with Qualitative Information. FOCS 2003: 524-533

Moses Charikar, Liadan O'Callaghan, Rina Panigrahy: Better streaming algorithms for clustering problems. STOC 2003: 30-39

Moses Charikar, Ronald Fagin, Venkatesan Guruswami, Jon M. Kleinberg, Prabhakar Raghavan, Amit Sahai: Query Strategies for Priced Information. J. Comput. Syst. Sci. 64(4): 785-819 (2002)

Moses Charikar, Sudipto Guha, Éva Tardos, David B. Shmoys: A Constant-Factor Approximation Algorithm for the k-Median Problem. J. Comput. Syst. Sci. 65(1): 129-149 (2002)

Moses Charikar, Amit Sahai: Dimension Reduction in the \ell _1 Norm. FOCS 2002: 551-560

Moses Charikar, Piotr Indyk, Rina Panigrahy: New Algorithms for Subset Query, Partial Match, Orthogonal Range Searching, and Related Problems. ICALP 2002: 451-462

Moses Charikar, Kevin Chen, Martin Farach-Colton: Finding Frequent Items in Data Streams. ICALP 2002: 693-703

Moses Charikar: On semidefinite programming relaxations for graph coloring and vertex cover. SODA 2002: 616-620

Moses Charikar: Similarity estimation techniques from rounding algorithms. STOC 2002: 380-388

Moses Charikar, Eric Lehman, Ding Liu, Rina Panigrahy, Manoj Prabhakaran, April Rasala, Amit Sahai, Abhi Shelat: Approximating the smallest grammar: Kolmogorov complexity in natural models. STOC 2002: 792-801

Susanne Albers, Moses Charikar, Michael Mitzenmacher: Delayed Information and Action in On-Line Algorithms. Inf. Comput. 170(2): 135-152 (2001)

Moses Charikar, Samir Khuller, Balaji Raghavachari: Algorithms for Capacitated Vehicle Routing. SIAM J. Comput. 31(3): 665-682 (2001)

Yair Bartal, Moses Charikar, Piotr Indyk: On page migration and other relaxed task systems. Theor. Comput. Sci. 268(1): 43-66 (2001)

Moses Charikar, Samir Khuller, David M. Mount, Giri Narasimhan: Algorithms for facility location problems with outliers. SODA 2001: 642-651

Moses Charikar, Rina Panigrahy: Clustering to minimize the sum of cluster diameters. STOC 2001: 1-10

Yair Bartal, Moses Charikar, Danny Raz: Approximating min-sum k-clustering in metric spaces. STOC 2001: 11-20

Piotr Berman, Moses Charikar, Marek Karpinski: On-Line Load Balancing for Related Machines. J. Algorithms 35(1): 108-121 (2000)

Andrei Z. Broder, Moses Charikar, Alan M. Frieze, Michael Mitzenmacher: Min-Wise Independent Permutations. J. Comput. Syst. Sci. 60(3): 630-659 (2000)

Moses Charikar: Greedy approximation algorithms for finding dense components in a graph. APPROX 2000: 84-95

Moses Charikar, Venkatesan Guruswami, Ravi Kumar, Sridhar Rajagopalan, Amit Sahai: Combinatorial feature selection problems. FOCS 2000: 631-640

Rohit Negi, Moses Charikar, John M. Cioffi: Minimum Outage Transmission over Fading Channels with Delay Constraint. ICC (1) 2000: 282-286

Moses Charikar, Joseph Naor, Baruch Schieber: Resource Optimization in QoS Multicast Routing of Real-Time Multimedia. INFOCOM 2000: 1518-1527

Moses Charikar, Surajit Chaudhuri, Rajeev Motwani, Vivek R. Narasayya: Towards Estimation Error Guarantees for Distinct Values. PODS 2000: 268-279

Moses Charikar, Ronald Fagin, Venkatesan Guruswami, Jon M. Kleinberg, Prabhakar Raghavan, Amit Sahai: Query strategies for priced information (extended abstract). STOC 2000: 582-591

Piotr Berman, Moses Charikar, Marek Karpinski: On-Line Load Balancing for Related Machines. Electronic Colloquium on Computational Complexity (ECCC) 7(1) (2000)

Moses Charikar, Chandra Chekuri, To-Yat Cheung, Zuo Dai, Ashish Goel, Sudipto Guha, Ming Li: Approximation Algorithms for Directed Steiner Problems. J. Algorithms 33(1): 73-91 (1999)

Moses Charikar, Sudipto Guha: Improved Combinatorial Algorithms for the Facility Location and k-Median Problems. FOCS 1999: 378-388

Moses Charikar, Jon M. Kleinberg, Ravi Kumar, Sridhar Rajagopalan, Amit Sahai, Andrew Tomkins: Minimizing Wirelength in Zero and Bounded Skew Clock Trees. SODA 1999: 177-184

Moses Charikar, Sudipto Guha, Éva Tardos, David B. Shmoys: A Constant-Factor Approximation Algorithm for the k-Median Problem (Extended Abstract). STOC 1999: 1-10

Moses Charikar, Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, Andrew Tomkins: On targeting Markov segments. STOC 1999: 99-108

Susanne Albers, Moses Charikar, Michael Mitzenmacher: Delayed Information and Action in On-line Algorithms. FOCS 1998: 71-81

Moses Charikar, Chandra Chekuri, Ashish Goel, Sudipto Guha, Serge A. Plotkin: Approximating a Finite Metric by a Small Number of Tree Metrics. FOCS 1998: 379-388

Moses Charikar, Balaji Raghavachari: The Finite Capacity Dial-A-Ride Problem. FOCS 1998: 458-467

Andrei Z. Broder, Moses Charikar, Michael Mitzenmacher: A Derandomization Using Min-Wise Independent Permutations. RANDOM 1998: 15-24

Moses Charikar, Chandra Chekuri, To-Yat Cheung, Zuo Dai, Ashish Goel, Sudipto Guha, Ming Li: Approximation Algorithms for Directed Steiner Problems. SODA 1998: 192-200

Moses Charikar, Dan Halperin, Rajeev Motwani: The Dynamic Servers Problem. SODA 1998: 410-419

Moses Charikar, Chandra Chekuri, Ashish Goel, Sudipto Guha: Rounding via Trees: Deterministic Approximation Algorithms for Group Steiner Trees and k-Median. STOC 1998: 114-123

Andrei Z. Broder, Moses Charikar, Alan M. Frieze, Michael Mitzenmacher: Min-Wise Independent Permutations (Extended Abstract). STOC 1998: 327-336

Moses Charikar, Samir Khuller, Balaji Raghavachari: Algorithms for Capacitated Vehicle Routing. STOC 1998: 349-358

Yair Bartal, Moses Charikar, Piotr Indyk: On Page Migration and Other Related Task Systems. SODA 1997: 43-52

Moses Charikar, Chandra Chekuri, Tomás Feder, Rajeev Motwani: Incremental Clustering and Dynamic Information Retrieval. STOC 1997: 626-635

Moses Charikar, Rajeev Motwani, Prabhakar Raghavan, Craig Silverstein: Constrained TSP and Low-Power Computing. WADS 1997: 104-115

Piotr Berman, Moses Charikar, Marek Karpinski: On-line Load Balancing for Related Machines. WADS 1997: 116-125