• Login
    View Item 
    •   SMARTech Home
    • College of Computing (CoC)
    • Algorithms and Randomness Center (ARC)
    • ARC Talks and Events
    • View Item
    •   SMARTech Home
    • College of Computing (CoC)
    • Algorithms and Randomness Center (ARC)
    • ARC Talks and Events
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Language Edit Distance, (min,+)-Matrix Multiplication and Beyond

    Thumbnail
    View/Open
    saha.mp4 (457.5Mb)
    saha_videostream.html (985bytes)
    transcription.txt (51.82Kb)
    Date
    2017-10-23
    Author
    Saha, Barna
    Metadata
    Show full item record
    Abstract
    The language edit distance is a significant generalization of two basic problems in computer science: parsing and string edit distance computation. Given any context free grammar, it computes the minimum number of insertions, deletions and substitutions required to convert a given input string into a valid member of the language. In 1972, Aho and Peterson gave a dynamic programming algorithm that solves this problem in time cubic in the string length. Despite its vast number of applications, in forty years there has been no improvement over this running time. Computing (min,+)-product of two n by n matrices in truly subcubic time is an outstanding open question, as it is equivalent to the famous All-Pairs-Shortest-Paths problem. Even when matrices have entries bounded in [1,n], obtaining a truly subcubic (min,+)-product algorithm will be a major breakthrough in computer science. In this presentation, I will explore the connection between these two problems which led us to develop the first truly subcubic algorithms for the following problems with improvements coming for each of these problems after several decades: (1) language edit distance, (2) RNA-folding-a basic computational biology problem and a special case of language edit distance computation, (3) stochastic grammar parsing—fundamental to natural language processing, and (4) (min,+)-product of integer matrices with entries bounded in n^(3-ω-c) where c >0 is any constant and, ω is the exponent of the fast matrix multiplication, believed to be 2.
    URI
    http://hdl.handle.net/1853/58857
    Collections
    • ARC Talks and Events [84]

    Browse

    All of SMARTechCommunities & CollectionsDatesAuthorsTitlesSubjectsTypesThis CollectionDatesAuthorsTitlesSubjectsTypes

    My SMARTech

    Login

    Statistics

    View Usage StatisticsView Google Analytics Statistics
    • About
    • Terms of Use
    • Contact Us
    • Emergency Information
    • Legal & Privacy Information
    • Accessibility
    • Accountability
    • Accreditation
    • Employment
    • Login
    Georgia Tech

    © Georgia Institute of Technology

    • About
    • Terms of Use
    • Contact Us
    • Emergency Information
    • Legal & Privacy Information
    • Accessibility
    • Accountability
    • Accreditation
    • Employment
    • Login
    Georgia Tech

    © Georgia Institute of Technology