Brown CS News

The Paris C. Kanellakis Memorial Lecture, a tradition of more than two decades, honors a distinguished computer scientist who was an esteemed and beloved member of the Brown CS community. Paris came to Brown in 1981 and became a full professor in 1990. His research area was theoretical computer science, with emphasis on the principles of database systems, logic in computer science, distributed computing, and combinatorial optimization. He died in an airplane crash on December 20, 1995, along with his wife, Maria Teresa Otoya, and their two young children, Alexandra and Stephanos Kanellakis.

Each year, Brown CS invites one of the field's most prominent scientists to address wide-ranging topics in honor of Paris. Last week, Virginia Vassilevska Williams, Professor of Computer Science and Artificial Intelligence and Decision-making at the Massachusetts of Technology, delivered the twenty-fourth annual Paris C. Kanellakis Memorial Lecture: “A Fine-Grained Approach to Algorithms and Complexity”.

In his opening remarks, Brown CS faculty member Ellis Hershkowitz detailed Virginia’s many honors and spoke of his personal admiration for her work. “She’s a pioneer,” he said, in what he described as the “emerging field” of fine-grained complexity.

Taking the stage, Virginia situated her work by explaining that much of algorithmic research focuses on a key question: how fast can we solve fundamental problems in the worst case?  These problems, she said, can be characterized by four common factors: (1) all techniques intended to solve them have stalled, (2) they’re crucial problems from diverse areas, (3) their best solutions involve simple, textbook algorithms, and (4) these solutions are slow, and haven’t been improved on in years.

For many fundamental problems, she said, the best-known running times are essentially those of classical algorithms now sixty and seventy years old: “The solution has been brute force.”

In recent years, however, theoreticians have developed a new area of study: fine-grained complexity, which allows analysis of problem complexity beyond the traditional "P vs. NP" distinction by means of fine-grained reductions, which transform one problem to another with a focus on exact running times. “NP-hardness,” Virginia explained, “is too coarse-grained”, whereas a fine-grained theory of hardness “mimics NP-hardness but is about concrete runtimes”.

Questions from the packed room came early and often, with the interested audience responding each time that Virginia paused to invite comments. After explaining what she called Traditional Hardness, she then gave an overview of the fine-grained approach, comparing and contrasting it with prior efforts. Her examples included the well-known Boolean satisfiability problem, which asks whether the variables of a given Boolean formula can be consistently replaced by the values TRUE or FALSE in such a way that the formula evaluates to TRUE, as well as the Longest Common Subsequence problem, which attempts to find the longest common subsequence of two strings.  

Finally, Virginia gave an overview of some new applications of a fine-grained approach, including quantum algorithms and data structures. “By using alternate hardness assumptions,” she explained, “one can unravel even more structure….and nail down the structure that makes these problems hard.”

Brown CS faculty member Philip Klein was one of the event’s many attendees. “For me,” he said, “the Kanellakis lecture is a high point of the year, both because it is a moment to remember Paris Kanellakis, who was to me both inspirational and kind, and because we get such wonderful speakers. Virgie is a great example. She is a pioneer in fine-grained complexity, a research area of theory of computation that has helped to guide those of us who seek to design new algorithms and that, more broadly, sheds light on the landscape of computational complexity of concrete, uncontrived problems. She gave a lovely survey of the research area, which I think is helpful to the Brown CS community because most people studying algorithms are unaware of the area.”

A recording of the lecture is available here.

For more information, click the link that follows to contact Brown CS Communications Manager Jesse C. Polhemus.