Publications


Journal Papers

"Sublinear Methods for Detecting Periodic Trends in Data Streams"
F. Ergun, S. Muthukrishnan, S.C. Sahinalp
ACM Transactions on Algorithms, 6(2), 2010.

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

"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

"An Improved FPTAS for Routing using Restricted Shortest Paths",
F. Ergun, R. Sinha, L. Zhang.
Information Processing Letters, 2002

``Approximate Checking of Polynomials and Functional Equations'' ,
F. Ergun, R. Kumar, R. Rubinfeld.
SIAM J. on Computing, 2001.

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


Refereed Conferences

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

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

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

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

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

"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

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