"Strain Level Microbial Detection and Quantification with Applications to Single Cell Metagenomics"
K. Zhu, W. Robinson, A. Schaffer, J. Xu, E. Ruppin, F. Ergun, Y. Ye and S. C. Sahinalp
Nature Communications (significantly extended version of the RECOMB'21 paper), 2022.
"Provably Fast Intratumor Heterogeneity Inference from Single-Cell
Sequencing Data"
C. Kizilkale, F. Rashidi Mehrabadi, E. Perez-Guijarro, K. Marie, E. Sadeqi-Azer, M. Lee, C. Day, G. Merlino, F. Ergun, A. Buluc, S.C. Sahinalp, S. Malikic
Nature Computational Science, 2022.
"Strain Level Microbial Detection and Quantification with Applications to Single Cell Metagenomics"
K. Zhu, W. Robinson, A. Schaffer, J. Xu, E. Ruppin, F. Ergun, Y. Ye, C. Sahinalp
Proceedings of the International Conference on Research in Computational Molecular Biology (RECOMB), 2021.
"PhISCS-BnB: A Fast Branch and Bound Algorithm for the Perfect Tumor Phylogeny Reconstruction Problem"
E. Sadeqi-Azer, Z. Malikic, X. Li, O. Bartok, K. Litchfield, R. Levy, Y. Samuels, A. Schaffer, M. Gertz, C. Day, E. Perez-Guijaro, K. Marie, M. Lee, G. Merlino, F. Ergun, C. Sahinalp
Proceedings of the Conference on Intelligent Systems for Molecular Biology (ISMB), 2020.
Bioinformatics Volume 36, Issue Supplement 1, July 2020, i169-i176, 2020.
"Streaming Periodicity with Wildcards"
F. Ergun, E. Grigorescu, E. Sadeqi-Azer, and S. Zhou,
Theory of Computing Systems, 64(1), 177-197, 2020: By invitation for the special issue for CSR.
Proceedings version: International Computer Science Symposium (CSR), Moscow, Russia, 2018.
"Streaming Periodicity with Mismatches"
F. Ergun, E. Grigorescu, E. Sadeqi-Azer, and S. Zhou,
RANDOM 2017
"On the Monotonicity of a Data Stream"
F. Ergun, H. Jowhari
Combinatorica 35(6): 641-653, 2015.
"On Datacenter-Network-Aware Load Balancing
in MapReduce"
Y. Le, F. Wang, J. Liu, F. Ergun,
IEEE CLOUD 2015
"Online Load Balancing for MapReduce with Skewed Data Input"
Y. Le, J. Liu, F. Ergun, and D. Wang,
IEEE INFOCOM 2014
"Palindrome Recognition in the Streaming Model"
P. Berenbrink, F. Ergun, F. Malmann-Trenn, E. Sadeqi Azer.
STACS 2014.
"Network Design for Tolerating Multiple Link Failures Using Fast Re-Route (FRR)"
R. Sinha, F. Ergun, K. Oikonomou, K. K. Ramakrishnan.
DRCN 2014.
"Periodicity in Streams"
F. Ergun, H. Jowhari, M. Saglam
RANDOM 2010.
"Periodicity testing with sublinear samples and space."
F. Ergun, S. Muthukrishnan, S.C. Sahinalp
ACM Transactions on Algorithms, 6(2), 2010.
"On Distance to Monotonicity
and Longest Increasing Subsequence of a Data Stream"
F. Ergun, H. Jowhari
ACM/SIAM Symposium on Discrete Algorithms (SODA), 2008.
"Oblivious String Embeddings and Edit Distance Approximations"
T. Batu, F. Ergun, C. Sahinalp
ACM/SIAM Symposium on Discrete Algorithms (SODA), 2006.
"Sublinear Approximation of Euclidean Minimum Spanning Tree"
A. Czumaj, F. Ergun, L. Fortnow, A. Magen, I. Newman, R. Rubinfeld,
C. Sohler
SIAM Journal on Computing 35(1):91--109, 2005.
"Finding Frequent Patterns in a String in Sublinear Time"
P. Berenbrink, F. Ergun, T. Friedetzky
European Symposium on Algorithms (ESA) 2005.
"A Layered Architecture for Delay Sensitive Sensor Networks"
D. Wang, Y. Long, F. Ergun
IEEE Communications Society Conference on Sensor
and Ad Hoc Communications and Networks (SECON), 2005.
"Unreserved Bandwidth Protection for MPLS Networks"
D. Wang, F. Ergun
International Conference on Quality of Service in Heterogeneous
Wired/Wireless Networks (QSHINE), 2005.
"Unicast and Multicast QoS Routing with Multiple Constraints"
D. Wang, F. Ergun, Z. Xu
International Workshop on QoS in Multiservice IP Networks (QoSIP),
2005.
"Fast Approximate Probabilistically Checkable Proofs"
F. Ergun, S. R. Kumar, R. Rubinfeld
Information and Computation, 2004.
"Identifying Uniformly Mutated Segments within Repeats"
S. C. Sahinalp, E. Eichler, P. Goldberg, P. Berenbrink, T. Friedetzky,
F. Ergun
Journal of Computational Biology and Bioinformatics, 2004
"Sublinear Methods for Detecting Periodic Trends in Data Streams"
F. Ergun, S. Muthukrishnan, S.C. Sahinalp
Latin American Symposium on Theoretical Informatics (LATIN), 2004.
"Comparing Sequences with Segment Rearrangements"
F. Ergun, S. Muthukrishnan, S.C. Sahinalp
Conference on Foundations of Techonology and
Theoretical Computer Science (FSTTCS), 2003.
``A sublinear algorithm for weakly approximating edit distance",
T. Batu, F. Ergun, J. Kilian, A. Magen, S.
Raskhodnikova, R. Rubinfeld and R. Sami
ACM Symposium on Theory of Computing (STOC) 2003.
"Sublinear Time Approximation of Euclidean Minimum Spanning Tree",
A. Czumaj, F. Ergun, L. Fortnow, A. Magen, I. Newman, R. Rubinfeld, C. Sohler
ACM/SIAM Symposium on Discrete Algorithms (SODA), 2003.
"Statistical
Identification of Uniformly Mutated Segments within Repeats'',
S. Sahinalp, E. Eichler, P. Goldberg, P. Berenbrink, T. Friedetzky, F. Ergun
CPM'02, Combinatorial Pattern Matching Conference, Fukuoka, Japan, 2002.
"An Improved FPTAS for Routing using Restricted Shortest Paths",
F. Ergun, R. Sinha, L. Zhang.
Information Processing Letters, 2002
"A Dynamic Lookup Scheme for Bursty Access Patterns" ,
F. Ergun, S. Mittra, C. Sahinalp, J. Sharp, R. Sinha,
IEEE INFOCOM 2001, Anchorage, Alaska.
"Biased Dictionaries with Fast Insert/Deletes"
F. Ergun, C. Sahinalp, J. Sharp, R. Sinha,
ACM Symposium on Theory of Computing (STOC) 2001, Heraklion, Greece.
``Approximate Checking of Polynomials and Functional Equations'' ,
F. Ergun, R. Kumar, R. Rubinfeld.
SIAM J. on Computing, 2001.
"Biased skip lists for highly skewed access patterns",
Funda Ergun, S. Cenk Sahinalp, Jon Sharp, and
Rakesh K. Sinha,
ALENEX 2001, Washington, DC.
``QoS Routing with Performance Dependent Costs''
F. Ergun, R. Sinha, L. Zhang,
IEEE INFOCOM 00, Tel Aviv, Israel
``Self-Testing without the Generator Bottleneck'' ,
F. Ergun, R. Kumar, D. Sivakumar.
SIAM J. of Computing, 2000.
``Spot Checkers'' ,
F. Ergun, S. Kannan, R. Kumar, R. Rubinfeld, M. Viswanathan.
J. of Computer and System Sciences, 2000,
Special Issue on STOC 98.
``Fast Approximate PCPs''
F. Ergun, R. Kumar, R. Rubinfeld,
ACM Symposium on Theory of Computing (STOC) 1999, Atlanta, GA.
``A Note on the Bounds of Collusion Resistant Watermarks"
F. Ergun, J. Kilian, R. Kumar.
EUROCRYPT 99, Prague, Czech Republic.
``Spot Checkers'' ,
F. Ergun, S. Kannan, R. Kumar, R. Rubinfeld, M. Viswanathan.
ACM Symposium on Theory of Computing (STOC) 1998, Dallas, TX.
``Checking Properties of Polynomials''
B. Codenotti, F. Ergun, P. Gemmell, R. Kumar.
International Conference on Automata, Languages and Programming
(ICALP) 1997, Bologna, Italy.
``Learning Distributions from Random Walks"
F. Ergun, R. Kumar, R. Rubinfeld.
ACM Conference on Computational Learning Theory (COLT) 1997, Nashville, TN.
``Approximate Checking of Polynomials and Functional Equations''
F. Ergun, R. Kumar, R. Rubinfeld.
IEEE Symposium on Foundations of Computer Science (FOCS) 1996,
Burlington, VT.
``Testing Multivariate Linear Functions: Overcoming
the Generator Bottleneck"
F. Ergun.
ACM Symposium on Theory of Computing (STOC) 1995, Las Vegas,
Nevada
``On Learning Bounded Width Branching Programs"
F. Ergun, R. Kumar, R. Rubinfeld,
ACM Conference on Computational Learning Theory (COLT) 1995,
San Diego, CA.