Edit Profile Farach-Colton, Martin Compute Distance To: Compute Author ID: farach-colton.martin Published as: Farach-Colton, M.; Farach-Colton, Martin; Farach-Colton, Martín Documents Indexed: 57 Publications since 1998, including 5 Books all top 5 Co-Authors 1 single-authored 18 Bender, Michael A. 11 Mosteiro, Miguel A. 9 Tsai, Meng-Tsung 6 Demaine, Erik D. 3 Cole, Richard John 3 Fernandes, Rohan J. 3 Fineman, Jeremy T. 3 Shah, Rahul 2 Alon, Noga M. 2 Bădoiu, Mihai 2 Bartal, Yair 2 Benson, Gary 2 Charikar, Moses S. 2 Chen, Kevin C. 2 Fekete, Sándor P. 2 Fernández Anta, Antonio 2 Gilbert, Seth 2 Goswami, Mayank 2 Hajiaghayi, Mohammad Taghi 2 Johnson, Rob 2 Landau, Gad M. 2 Sahinalp, Suleyman Cenk 2 Sidiropoulos, Anastasios 2 Tsur, Dekel 2 Yooseph, Shibu 2 Zhang, Lisa 1 Afshani, Peyman 1 Almeida, Paulo Sérgio 1 Amir, Amihood 1 Apostolico, Alberto 1 Baquero, Carlos 1 Bille, Philip 1 Chowdhury, Rezaul Alam 1 Christensen, Jake 1 Christiansen, Anders Roy 1 Conway, Alex 1 Conway, Alexander 1 Crochemore, Maxime 1 Cyran, Mary 1 Ferragina, Paolo 1 Gabow, Harold N. 1 Galil, Zvi 1 Ganapathi, Pramod 1 Hariharan, Ramesh 1 Hsu, Tsan-sheng 1 Huang, Yang 1 Jesus, Paulo 1 Kuszmaul, William 1 Lewenstein, Moshe 1 Li, Meng 1 Liberatore, Vincenzo 1 McCauley, Samuel 1 Medjedovic, Dzejla 1 Milani, Alessia 1 Montes, Pablo 1 Muthukrishnan, S. Muthu 1 Muthukrishnan, Subramani 1 Pemmasani, Giridhar 1 Porat, Ely 1 Prencipe, Giuseppe 1 Przytycka, Teresa M. 1 Roberts, Fred S. 1 Simon, Bertrand 1 Singh, Shikha 1 Skiena, Steven Sol 1 Sumazin, Pavel 1 Thorup, Mikkel 1 Uehara, Ryuhei 1 Vingron, Martin 1 Waterman, Michael S. 1 Zaks, Shmuel 1 Zito, Jack all top 5 Serials 6 Theoretical Computer Science 4 Algorithmica 4 ACM Transactions on Algorithms 2 SIAM Journal on Computing 2 Journal of Algorithms 2 Lecture Notes in Computer Science 1 Journal of Computer and System Sciences 1 Journal of Classification 1 Information and Computation 1 Distributed Computing 1 Theory of Computing Systems 1 Journal of the ACM 1 DIMACS. Series in Discrete Mathematics and Theoretical Computer Science 1 LIPIcs – Leibniz International Proceedings in Informatics all top 5 Fields 55 Computer science (68-XX) 7 General and overarching topics; collections (00-XX) 6 Combinatorics (05-XX) 3 Operations research, mathematical programming (90-XX) 2 Number theory (11-XX) 2 Biology and other natural sciences (92-XX) 1 History and biography (01-XX) 1 Order, lattices, ordered algebraic structures (06-XX) 1 Statistics (62-XX) 1 Numerical analysis (65-XX) 1 Game theory, economics, finance, and other social and behavioral sciences (91-XX) Publications by Year all cited Publications top 5 cited Publications Citations contained in zbMATH 35 Publications have been cited 426 times in 362 Documents Cited by ▼ Year ▼ The LCA problem revisited. Zbl 0959.68133Bender, Michael A.; Farach-Colton, Martín 145 2000 Lowest common ancestors in trees and directed acyclic graphs. Zbl 1085.68103Bender, Michael A.; Farach-Colton, Martín; Pemmasani, Giridhar; Skiena, Steven; Sumazin, Pavel 40 2005 On the sorting-complexity of suffix tree construction. Zbl 1094.68694Farach-Colton, Martin; Ferragina, Paolo; Muthukrishnan, S. 39 2000 The level ancestor problem simplified. Zbl 1068.68047Bender, Michael A.; Farach-Colton, Martín 28 2004 Finding frequent items in data streams. Zbl 1057.68600Charikar, Moses; Chen, Kevin; Farach-Colton, Martin 24 2002 Two simplified algorithms for maintaining order in a list. Zbl 1019.68527Bender, Michael A.; Cole, Richard; Demaine, Erik D.; Farach-Colton, Martin; Zito, Jack 22 2002 Finding frequent items in data streams. Zbl 1071.68020Charikar, Moses; Chen, Kevin; Farach-Colton, Martin 17 2004 An \(O(n\log n)\) algorithm for the maximum agreement subtree problem for binary trees. Zbl 0976.68081Cole, Richard; Farach-Colton, Martin; Hariharan, Ramesh; Przytycka, Teresa; Thorup, Mikkel 16 2000 Cache-oblivious B-trees. Zbl 1092.68028Bender, Michael A.; Demaine, Erik D.; Farach-Colton, Martin 15 2005 Fast and compact regular expression matching. Zbl 1155.68022Bille, Philip; Farach-Colton, Martin 9 2008 The level ancestor problem simplified. Zbl 1059.68563Bender, Michael A.; Farach-Colton, Martín 8 2002 Reallocation problems in scheduling. Zbl 1322.68029Bender, Michael A.; Farach-Colton, Martin; Fekete, Sándor P.; Fineman, Jeremy T.; Gilbert, Seth 5 2015 Sensor network gossiping or how to break the broadcast lower bound. Zbl 1193.68028Farach-Colton, Martín; Mosteiro, Miguel A. 5 2007 Optimal spaced seeds for faster approximate string matching. Zbl 1123.68119Farach-Colton, Martin; Landau, Gad M.; Sahinalp, S. Cenk; Tsur, Dekel 5 2007 Ordinal embeddings of minimum relaxation, general properties, trees, and ultrametrics. Zbl 1297.68079Alon, Noga; Bădoiu, Mihai; Demaine, Erik D.; Farach-Colton, Martin; Hajiaghayi, MohammadTaghi; Sidiropoulos, Anastasios 5 2005 Optimal parallel two dimensional text searching on a CREW PRAM. Zbl 0917.68049Amir, Amihood; Benson, Gary; Farach-Colton, Martin 5 1998 Undiscretized dynamic programming: Faster algorithms for facility location and related problems on trees. Zbl 1093.68628Shah, Rahul; Farach-Colton, Martin 4 2002 Fault-tolerant aggregation: flow-updating meets mass-distribution. Zbl 1420.68022Almeida, Paulo Sérgio; Baquero, Carlos; Farach-Colton, Martín; Jesus, Paulo; Mosteiro, Miguel A. 3 2017 Ordinal embeddings of minimum relaxation: general properties, trees, and ultrametrics. Zbl 1445.68182Alon, Noga; Bădoiu, Mihai; Demaine, Erik D.; Farach-Colton, Martin; Hajiaghayi, Mohammadtaghi; Sidiropoulos, Anastasios 3 2008 Lower bounds for clear transmissions in radio networks. Zbl 1145.68324Farach-Colton, Martín; Fernandes, Rohan J.; Mosteiro, Miguel A. 3 2006 Optimal spaced seeds for faster approximate string matching. Zbl 1081.68674Farach-Colton, Martin; Landau, Gad M.; Sahinalp, S. Cenk; Tsur, Dekel 3 2005 Fast, fair, and frugal bandwidth allocation in ATM networks. Zbl 0934.68013Bartal, Yair; Farach-Colton, Martin; Yooseph, Shibu; Zhang, Lisa 3 1999 Forty years of text indexing. Zbl 1381.68067Apostolico, Alberto; Crochemore, Maxime; Farach-Colton, Martin; Galil, Zvi; Muthukrishnan, S. 2 2013 Bootstrapping a hop-optimal network in the weak sensor model. Zbl 1298.68040Farach-Colton, Martin; Fernandes, Rohan J.; Mosteiro, Miguel A. 2 2009 A linear delay algorithm for building concept lattices. Zbl 1143.68602Farach-Colton, Martin; Huang, Yang 2 2008 Initializing sensor networks of non-uniform density in the weak sensor model. Zbl 1209.68045Farach-Colton, Martín; Mosteiro, Miguel A. 2 2007 Efficient tree layout in a multilevel memory hierarchy. Zbl 1019.68525Bender, Michael A.; Demaine, Erik D.; Farach-Colton, Martin 2 2002 Scanning and traversing: Maintaining data for traversals in a memory hierarchy. Zbl 1019.68526Bender, Michael A.; Cole, Richard; Demaine, Erik D.; Farach-Colton, Martin 2 2002 Parallel lookups in string indexes. Zbl 1397.68237Christiansen, Anders Roy; Farach-Colton, Martín 1 2016 On the complexity of computing prime tables. Zbl 1417.68066Farach-Colton, Martín; Tsai, Meng-Tsung 1 2015 Exact sublinear binomial sampling. Zbl 1331.68278Farach-Colton, Martín; Tsai, Meng-Tsung 1 2013 Optimal memory-aware sensor network gossiping (or how to break the broadcast lower bound). Zbl 1259.68016Farach-Colton, Martín; Anta, Antonio Fernández; Mosteiro, Miguel A. 1 2013 INSERTION SORT is \(O(n \log n)\). Zbl 1107.68034Bender, Michael A.; Farach-Colton, Martin; Mosteiro, Miguel A. 1 2006 Bootstrapping a hop-optimal network in the weak sensor model. Zbl 1142.90338Farach-Colton, Martín; Fernandes, Rohan J.; Mosteiro, Miguel A. 1 2005 Fast, fair and frugal bandwidth allocation in ATM networks. Zbl 0994.68003Bartal, Y.; Farach-Colton, M.; Yooseph, S.; Zhang, L. 1 2002 Fault-tolerant aggregation: flow-updating meets mass-distribution. Zbl 1420.68022Almeida, Paulo Sérgio; Baquero, Carlos; Farach-Colton, Martín; Jesus, Paulo; Mosteiro, Miguel A. 3 2017 Parallel lookups in string indexes. Zbl 1397.68237Christiansen, Anders Roy; Farach-Colton, Martín 1 2016 Reallocation problems in scheduling. Zbl 1322.68029Bender, Michael A.; Farach-Colton, Martin; Fekete, Sándor P.; Fineman, Jeremy T.; Gilbert, Seth 5 2015 On the complexity of computing prime tables. Zbl 1417.68066Farach-Colton, Martín; Tsai, Meng-Tsung 1 2015 Forty years of text indexing. Zbl 1381.68067Apostolico, Alberto; Crochemore, Maxime; Farach-Colton, Martin; Galil, Zvi; Muthukrishnan, S. 2 2013 Exact sublinear binomial sampling. Zbl 1331.68278Farach-Colton, Martín; Tsai, Meng-Tsung 1 2013 Optimal memory-aware sensor network gossiping (or how to break the broadcast lower bound). Zbl 1259.68016Farach-Colton, Martín; Anta, Antonio Fernández; Mosteiro, Miguel A. 1 2013 Bootstrapping a hop-optimal network in the weak sensor model. Zbl 1298.68040Farach-Colton, Martin; Fernandes, Rohan J.; Mosteiro, Miguel A. 2 2009 Fast and compact regular expression matching. Zbl 1155.68022Bille, Philip; Farach-Colton, Martin 9 2008 Ordinal embeddings of minimum relaxation: general properties, trees, and ultrametrics. Zbl 1445.68182Alon, Noga; Bădoiu, Mihai; Demaine, Erik D.; Farach-Colton, Martin; Hajiaghayi, Mohammadtaghi; Sidiropoulos, Anastasios 3 2008 A linear delay algorithm for building concept lattices. Zbl 1143.68602Farach-Colton, Martin; Huang, Yang 2 2008 Sensor network gossiping or how to break the broadcast lower bound. Zbl 1193.68028Farach-Colton, Martín; Mosteiro, Miguel A. 5 2007 Optimal spaced seeds for faster approximate string matching. Zbl 1123.68119Farach-Colton, Martin; Landau, Gad M.; Sahinalp, S. Cenk; Tsur, Dekel 5 2007 Initializing sensor networks of non-uniform density in the weak sensor model. Zbl 1209.68045Farach-Colton, Martín; Mosteiro, Miguel A. 2 2007 Lower bounds for clear transmissions in radio networks. Zbl 1145.68324Farach-Colton, Martín; Fernandes, Rohan J.; Mosteiro, Miguel A. 3 2006 INSERTION SORT is \(O(n \log n)\). Zbl 1107.68034Bender, Michael A.; Farach-Colton, Martin; Mosteiro, Miguel A. 1 2006 Lowest common ancestors in trees and directed acyclic graphs. Zbl 1085.68103Bender, Michael A.; Farach-Colton, Martín; Pemmasani, Giridhar; Skiena, Steven; Sumazin, Pavel 40 2005 Cache-oblivious B-trees. Zbl 1092.68028Bender, Michael A.; Demaine, Erik D.; Farach-Colton, Martin 15 2005 Ordinal embeddings of minimum relaxation, general properties, trees, and ultrametrics. Zbl 1297.68079Alon, Noga; Bădoiu, Mihai; Demaine, Erik D.; Farach-Colton, Martin; Hajiaghayi, MohammadTaghi; Sidiropoulos, Anastasios 5 2005 Optimal spaced seeds for faster approximate string matching. Zbl 1081.68674Farach-Colton, Martin; Landau, Gad M.; Sahinalp, S. Cenk; Tsur, Dekel 3 2005 Bootstrapping a hop-optimal network in the weak sensor model. Zbl 1142.90338Farach-Colton, Martín; Fernandes, Rohan J.; Mosteiro, Miguel A. 1 2005 The level ancestor problem simplified. Zbl 1068.68047Bender, Michael A.; Farach-Colton, Martín 28 2004 Finding frequent items in data streams. Zbl 1071.68020Charikar, Moses; Chen, Kevin; Farach-Colton, Martin 17 2004 Finding frequent items in data streams. Zbl 1057.68600Charikar, Moses; Chen, Kevin; Farach-Colton, Martin 24 2002 Two simplified algorithms for maintaining order in a list. Zbl 1019.68527Bender, Michael A.; Cole, Richard; Demaine, Erik D.; Farach-Colton, Martin; Zito, Jack 22 2002 The level ancestor problem simplified. Zbl 1059.68563Bender, Michael A.; Farach-Colton, Martín 8 2002 Undiscretized dynamic programming: Faster algorithms for facility location and related problems on trees. Zbl 1093.68628Shah, Rahul; Farach-Colton, Martin 4 2002 Efficient tree layout in a multilevel memory hierarchy. Zbl 1019.68525Bender, Michael A.; Demaine, Erik D.; Farach-Colton, Martin 2 2002 Scanning and traversing: Maintaining data for traversals in a memory hierarchy. Zbl 1019.68526Bender, Michael A.; Cole, Richard; Demaine, Erik D.; Farach-Colton, Martin 2 2002 Fast, fair and frugal bandwidth allocation in ATM networks. Zbl 0994.68003Bartal, Y.; Farach-Colton, M.; Yooseph, S.; Zhang, L. 1 2002 The LCA problem revisited. Zbl 0959.68133Bender, Michael A.; Farach-Colton, Martín 145 2000 On the sorting-complexity of suffix tree construction. Zbl 1094.68694Farach-Colton, Martin; Ferragina, Paolo; Muthukrishnan, S. 39 2000 An \(O(n\log n)\) algorithm for the maximum agreement subtree problem for binary trees. Zbl 0976.68081Cole, Richard; Farach-Colton, Martin; Hariharan, Ramesh; Przytycka, Teresa; Thorup, Mikkel 16 2000 Fast, fair, and frugal bandwidth allocation in ATM networks. Zbl 0934.68013Bartal, Yair; Farach-Colton, Martin; Yooseph, Shibu; Zhang, Lisa 3 1999 Optimal parallel two dimensional text searching on a CREW PRAM. Zbl 0917.68049Amir, Amihood; Benson, Gary; Farach-Colton, Martin 5 1998 all cited Publications top 5 cited Publications all top 5 Cited by 637 Authors 15 Navarro, Gonzalo 10 Iliopoulos, Costas S. 10 Inenaga, Shunsuke 9 Hon, Wing-Kai 9 Wang, Haitao 8 Bannai, Hideo 8 Mosteiro, Miguel A. 8 Park, Kunsoo 8 Shah, Rahul 7 Amir, Amihood 7 Bille, Philip 7 Pissis, Solon P. 7 Radoszewski, Jakub 7 Sung, Wing-Kin 7 Takeda, Masayuki 7 Thankachan, Sharma V. 6 Chao, Kunmao 6 Crochemore, Maxime 6 Durocher, Stephane 6 Gawrychowski, Paweł 6 Gørtz, Inge Li 6 Kim, Dong Kyue 6 Kociumaka, Tomasz 6 Lewenstein, Moshe 6 Nekrich, Yakov 6 Rahman, Mohammad Sohel 6 Waleń, Tomasz 5 Fischer, Johannes 5 Ganguly, Sumit 5 Jansson, Jesper 5 Landau, Gad M. 5 Porat, Ely 5 Rytter, Wojciech 5 Sadakane, Kunihiko 5 Woodruff, David P. 5 Yang, Chang-Biau 4 Berry, Vincent 4 Farach-Colton, Martin 4 Fernández Anta, Antonio 4 Grabowski, Szymon 4 Hor, Chiou-Yi 4 I, Tomohiro 4 Kopelowitz, Tsvi 4 Na, Joong Chae 4 Nakashima, Yuto 4 Narisawa, Kazuyuki 4 Nelson, Jelani 4 Smid, Michiel H. M. 4 Stølting Brodal, Gerth 4 Tirthapura, Srikanta 4 Tseng, Chiou-Ting 4 Wang, Biing-Feng 3 Adjeroh, Donald A. 3 Ann, Hsing-Yen 3 Bender, Michael A. 3 Blanchet-Sadri, Francine 3 Bose, Prosenjit K. 3 Chan, Timothy Moon-Yew 3 Chen, Kuanyu 3 Gagie, Travis 3 He, Meng 3 Kubica, Marcin 3 Lam, Tak-Wah 3 Levy, Avivit 3 Mäkinen, Veli 3 Maneth, Sebastian 3 Manzini, Giovanni 3 Munro, J. Ian 3 Nakamura, Kengo 3 Nicolas, François 3 Patil, Manish 3 Peng, Yung-Hsing 3 Pontelli, Enrico 3 Puerto Albandoz, Justo 3 Ranjan, Desh 3 Schmidt, Jens M. 3 Shinohara, Ayumi 3 Silveira, Rodrigo I. 3 Sim, Jeong Seop 3 Skala, Matthew 3 Starikovskaya, Tatiana A. 3 Tam, Siu-Lung 3 Tamir, Arie 3 Vitter, Jeffrey Scott 3 Weimann, Oren 3 Zeh, Norbert 3 Zhang, Jingru 2 Bae, Sang Won 2 Barton, Carl 2 Beal, Richard 2 Cafaro, Massimo 2 Caragiannis, Ioannis 2 Charalampopoulos, Panagiotis 2 Chen, Danny Ziyi 2 Colazzo, Dario 2 Cole, Richard John 2 Cording, Patrick Hagge 2 Dal Palù, Alessandro 2 Davoodi, Pooya 2 de Berg, Mark Theodoor ...and 537 more Authors all top 5 Cited in 59 Serials 64 Theoretical Computer Science 53 Algorithmica 32 Information Processing Letters 22 Journal of Discrete Algorithms 16 Discrete Applied Mathematics 13 Information and Computation 12 Computational Geometry 10 Journal of Computer and System Sciences 8 SIAM Journal on Computing 6 Distributed Computing 6 Algorithms 5 Information Sciences 5 Journal of Combinatorial Optimization 4 Discrete & Computational Geometry 4 International Journal of Foundations of Computer Science 3 Networks 3 Journal of Parallel and Distributed Computing 3 Theory of Computing Systems 3 Data Mining and Knowledge Discovery 3 Journal of Machine Learning Research (JMLR) 3 ACM Journal of Experimental Algorithmics 2 Computers & Mathematics with Applications 2 SIAM Journal on Matrix Analysis and Applications 2 International Journal of Computational Geometry & Applications 2 Journal of Mathematical Imaging and Vision 2 Journal of the ACM 2 Mathematics in Computer Science 1 ACM Computing Surveys 1 Artificial Intelligence 1 Discrete Mathematics 1 International Journal of Systems Science 1 Applied Mathematics and Computation 1 Computing 1 Fuzzy Sets and Systems 1 Journal of Combinatorial Theory. Series A 1 Mathematics of Operations Research 1 Graphs and Combinatorics 1 Journal of Complexity 1 New Generation Computing 1 SIAM Journal on Discrete Mathematics 1 Annals of Operations Research 1 MSCS. Mathematical Structures in Computer Science 1 Geometric and Functional Analysis. GAFA 1 European Journal of Operational Research 1 Information Systems 1 Pattern Recognition 1 Mathematical Programming. Series A. Series B 1 Cybernetics and Systems Analysis 1 Top 1 Constraints 1 Mathematical Problems in Engineering 1 Journal of the European Mathematical Society (JEMS) 1 Journal of Applied Mathematics 1 Sādhanā 1 Computer Languages, Systems & Structures 1 Statistical Analysis and Data Mining 1 Japanese Journal of Mathematics. 3rd Series 1 ACM Transactions on Algorithms 1 Computer Science Review all top 5 Cited in 21 Fields 310 Computer science (68-XX) 68 Combinatorics (05-XX) 34 Operations research, mathematical programming (90-XX) 25 Biology and other natural sciences (92-XX) 17 Numerical analysis (65-XX) 12 Statistics (62-XX) 8 Information and communication theory, circuits (94-XX) 4 Linear and multilinear algebra; matrix theory (15-XX) 4 Probability theory and stochastic processes (60-XX) 3 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 2 Functional analysis (46-XX) 2 Convex and discrete geometry (52-XX) 1 General and overarching topics; collections (00-XX) 1 Order, lattices, ordered algebraic structures (06-XX) 1 Number theory (11-XX) 1 Topological groups, Lie groups (22-XX) 1 Geometry (51-XX) 1 Differential geometry (53-XX) 1 Manifolds and cell complexes (57-XX) 1 Relativity and gravitational theory (83-XX) 1 Systems theory; control (93-XX) Citations by Year