Organizer(s):

Karthik C.S., Rutgers University

Elazar Goldenberg, Academic College of Tel Aviv-Yaffo

Description

Evaluating the similarity or dissimilarity between strings stands as a prevalent theme within the computational aspects of string processing. This theme finds practical implications across various domains, including computational biology, signal processing, text retrieval, image compression, data mining, and pattern recognition. The Hamming Distance, a natural metric for measuring similarity, quantifies the number of positions in which the inputs strings differ. However, situations may arise where two strings possess a significant shared substring or one can be transformed into the other using a relatively small number of edit operations. In many of the previously mentioned applications, recognizing such strings as similar proves crucial, although the Hamming metric fails to capture this degree of closeness. Instead, these scenarios often call for the application of metrics like the edit distance or the similarities based on the Longest Common Subsequence.

Calculating the Longest Common Subsequence (LCS) or the edit distance between strings can be achieved using a simple algorithm, often introduced in undergraduate-level algorithms courses. This algorithm runs in quadratic time. However, within many of the previously mentioned applications, this time complexity becomes impractical. Despite extensive scientific endeavors spanning decades, meaningful enhancements to this runtime have remained elusive. This has been substantiated by a series of seminal works indicating that, given reasonable computational assumptions like the strong exponential time hypothesis (SETH), the development of a sub-quadratic time algorithm for calculating the edit distance and LCS between strings is infeasible.

The absence of algorithms with sub-quadratic time complexity for these tasks, along with the existence of impossibility results, have spurred the quest for an approximation algorithm. This has turned into a very extensive line of work commencing with polynomial factor approximation in sub-quadratic time and culminating in the development of a constant factor approximation algorithm with nearly linear time complexity and similarly attaining sub-quadratic time algorithms for approximating LCS. This line of work was further extended into pursuit of algorithms with sublinear time complexity. Apriori, this cannot be accomplished even for the Hamming metric, since in the low distance regime, one must query the entirety of the strings to pinpoint these errors. However, when considering the gap version of the problem, achieving this becomes feasible with the Hamming metric. This was subsequently extended to encompass the computation of edit distance and LIS (a special case of LCS in which one of the input strings is the identity string).

The workshop has two main goals. The first goal is to unite leading researchers exploring the cutting edge results in the fields of: establishing lower bounds for string metrics computation; developing approximation algorithms; and devising sub-linear time algorithms for string metrics. The second goal, is to feature tutorial presentations covering a wider range of stringology tasks. These tutorials will delve into computational challenges arising from computational biology in relation to string metrics, explore the theoretical foundations of error-correcting codes in the context of the edit metric, and investigate the potential use of compression to speed up string task computations.

Current list of confirmed speakers:

• Alex Andoni, Columbia University
• Christina Boucher, University of Florida
• Diptarka Chakraborty, National University of Singapore
• Debarati Das, Pennsylvania State University
• Rajat De, Stony Brook University
• Nick Fischer,  Max Planck Institute for Informatics
• Bingbing Hu, University of California, San Diego
• Ce Jin, University of California, Berkeley
• Tomasz Kociumaka, Max Planck Institute for Informatics
• Michal Koucký, Charles University
• Jakob Nogler, Massachusetts Institute of Technology

FGC Fest: This workshop is the second of three workshops on fine-grained complexity (FGC) that will be held back-to-back at Rutgers in July 2026. Each workshop is self-contained but shares the focus on FGC. FGC Fest is made up of:

• Workshop of Algebraic Techniques in Fine-Grained Complexity, July 20-22, 2026.
• Workshop on Fine-Grained Complexity of String Problems, July 23-25, 2026. (This workshop.)
• Workshop on Fine-Grained Complexity of Graph Problems, July 27-31, 2026. 

Call For Participation

Presentations at this workshop are by invitation but others are welcome to attend. There is no fee to attend but registration is required. Please register using the link at the bottom of the page.

Request support: There are limited funds available to provide lodging to students and/or postdocs attending the workshop. In most cases, lodging will be shared with another student/postdoc attending the workshop. Priority will be given to those whose interests best align with the topic and whose attendance is contingent on support, especially students. 

To request support please complete and submit this form by April 15, 2026 for full consideration.

What information is requested in the form? Here are some things we will ask for:

• A short statement (one paragraph) about your research area and your interest in the workshop .
• CV in PDF format (optional).
• Contact information for one faculty member who could speak to how attendance will benefit you. (We will only contact this person if we need more information.)
• Whether you plan to attend another workshop in FGC Fest.

FGC Fest is sponsored by:

Presented in association with the Special Focus on Fine-grained Complexity.