Ryan Williams

activity

20062021

most citedFinding heaviest H-subgraphs in real weighted graphs, with applications

6 citations · 8 across the 5 of their papers we have counts for

collaborators

Showing cs.DSShow all

4 papers · 1 filter

cs.DS2020★ 1 cited

Fast Low-Space Algorithms for Subset Sum

Ce Jin, Nikhil Vyas, Ryan Williams

We consider the canonical Subset Sum problem: given a list of positive integers $a_{1}, \dots, a_{n}$ and a target integer $t$ with $t > a_{i}$ for all $i$ , determine if there is an $S \s…

cs.DS2018

An Equivalence Class for Orthogonal Vectors

Lijie Chen, Ryan Williams

The Orthogonal Vectors problem ( $OV$ ) asks: given $n$ vectors in ${0, 1}^{O (l o g n)}$ , are two of them orthogonal? $OV$ is easily solved in $O (n^{2} lo g n)$ time,…

cs.DS2016

Faster Online Matrix-Vector Multiplication

Kasper Green Larsen, Ryan Williams

We consider the Online Boolean Matrix-Vector Multiplication (OMV) problem studied by Henzinger et al. [STOC'15]: given an $n \times n$ Boolean matrix $M$ , we receive $n$ Boolean ve…

cs.DS2006★ 6 cited

Finding heaviest H-subgraphs in real weighted graphs, with applications

Virginia Vassilevska, Ryan Williams, Raphael Yuster

For a graph G with real weights assigned to the vertices (edges), the MAX H-SUBGRAPH problem is to find an H-subgraph of G with maximum total weight, if one exists. The all-pairs M…