"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.