93 citations · 183 across the 19 of their papers we have counts for
22 papers
Faster Detours in Undirected Graphs
Shyan Akmal, Virginia Vassilevska Williams, Ryan Williams +1
The -Detour problem is a basic path-finding problem: given a graph on vertices, with specified nodes and , and a positive integer , the goal is to determine if…
On the Number of Quantifiers as a Complexity Measure
Ronald Fagin, Jonathan Lenchner, Nikhil Vyas +1
In 1981, Neil Immerman described a two-player game, which he called the "separability game" \cite{Immerman81}, that captures the number of quantifiers needed to describe a property…
Smaller ACC0 Circuits for Symmetric Functions
Brynmor Chapman, Ryan Williams
What is the power of constant-depth circuits with gates, that can count modulo ? Can they efficiently compute MAJORITY and other symmetric functions? When is a const…
MAJORITY-3SAT (and Related Problems) in Polynomial Time
Shyan Akmal, Ryan Williams
Majority-SAT is the problem of determining whether an input -variable formula in conjunctive normal form (CNF) has at least satisfying assignments. Majority-SAT and re…
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 and a target integer with for all , determine if there is an $S \s…
An Equivalence Class for Orthogonal Vectors
Lijie Chen, Ryan Williams
The Orthogonal Vectors problem () asks: given vectors in , are two of them orthogonal? is easily solved in time,…