Mahdi Boroujeni, PhD Student at Computer Engineering Department of Sharif University of Technology, will present his article “1+ε Approximation of Tree Edit Distance in Quadratic Time”, supervised by Dr. Mohammad Ghodsi, Faculty Member at Computer Engineering Department, in the 51st ACM Symposium on Theory of Computing (STOC).
Edit distance is one of the most fundamental problems in computer science. Tree edit distance is a natural generalization of edit distance to ordered rooted trees. Such a generalization extends the applications of edit distance to areas such as computational biology, structured data analysis (e.g., XML), image analysis, and compiler optimization. Perhaps the most notable application of tree edit distance is in the analysis of RNA molecules in computational biology where the secondary structure of RNA is typically represented as a rooted tree.
The best-known solution for tree edit distance runs in cubic time. Recently, Bringmann et al. have shown that an O(n2.99) algorithm for weighted tree edit distance is unlikely by proving a conditional lower bound on the computational complexity of tree edit distance. This shows a substantial gap between the computational complexity of tree edit distance and that of edit distance for which a simple dynamic program solves the problem in quadratic time.
In the work done by dr. Boroujeni, the first non-trivial approximation algorithms for tree edit distance are given. The main result is a quadratic time approximation scheme for tree edit distance that approximates the solution within a factor of 1+є for any constant є > 0.
To access the paper, you might visit: https://dl.acm.org/citation.cfm?id=3316388
The Annual ACM Symposium on Theory of Computing (STOC), is the flagship conference of SIGACT, the Special Interest Group on Algorithms and Computation Theory, a special interest group of the Association for Computing Machinery (ACM). It has been held annually since 1969 and covers all areas of research within Algorithms and Computation Theory such as algorithms and data structures, computational complexity, randomness in computing, algorithmic graph theory and combinatorics, approximation algorithms, cryptography, computational learning theory, economics and computation, parallel and distributed algorithms, quantum computing, algorithmic coding theory, computational geometry, computational applications of logic, optimization, algebraic algorithms, and theoretical aspects of areas such as networks, privacy, computational biology, and databases.
As Fich (1996) writes, STOC and its annual IEEE counterpart FOCS (the Symposium on Foundations of Computer Science) are considered the two top conferences in theoretical computer science, considered broadly: they “are forums for some of the best work throughout theory of computing that promote breadth among theory of computing researchers and help to keep the community together.”
Prof. Mohammad Ghodsi is the head of Sharif CE Algorithms Lab at SUT. To get familiar with his research group please visit: http://algorithms.ce.sharif.edu/