#### PI Core/Dual

# Virginia Vassilevska Williams

Associate Professor

#### Room

32-G640Last updatedApr 13 '20

## Projects

#### Project

## Using Reductions to Understand Polynomial Time Algorithms

For many problems the best known algorithms take polynomial time but super linear time, we want to understand why problems like diameter, longest common sub-sequence and co-linear point detection can't be solved in linear time.

#### Project

## Algebraic Techniques for Algorithm Design

We work on improving the algorithms for algebraic problems like matrix multiplication, and using these to design algorithms for fundamental non-algebraic problems.

#### Project

## Approximating the diameter of a directed graph

There is a family of approximation algorithms for computing the diameter of an undirected graph that give a time/accuracy trade-off and our goal is to extend these results to directed graphs.

## Groups

#### Community of Research

## Theory of Computation Community of Research

The goal of the Theory of Computation CoR is to study the fundamental strengths and limits of computation as well as how these interact with mathematics, computer science, and other disciplines.

#### Leads

#### Research Areas

#### Impact Areas

#### Research Group

## Algorithms Group

We devise new mathematical tools to tackle the increasing difficulty and importance of problems we pose to computers.

#### Leads

#### Research Areas

#### Impact Areas

#### Research Group

## Complexity Theory Group

Our interests span quantum complexity theory, barriers to solving P versus NP, theoretical computer science with a focus on probabilistically checkable proofs (PCP), pseudo-randomness, coding theory, and algorithms.