11 citations · 15 across the 3 of their papers we have counts for
3 papers
cs.CC2016★ 11 cited
Nonnegative Rank vs. Binary Rank
Thomas Watson
Motivated by (and using tools from) communication complexity, we investigate the relationship between the following two ranks of a - matrix: its nonnegative rank and its bina…
cs.DS2011
Lift-and-Project Integrality Gaps for the Traveling Salesperson Problem
Thomas Watson
We study the lift-and-project procedures of Lov{á}sz-Schrijver and Sherali-Adams applied to the standard linear programming relaxation of the traveling salesperson problem with tri…
quant-ph2007★ 4 cited
A Quantum Time-Space Lower Bound for the Counting Hierarchy
Dieter van Melkebeek, Thomas Watson
We obtain the first nontrivial time-space lower bound for quantum algorithms solving problems related to satisfiability. Our bound applies to MajSAT and MajMajSAT, which are comple…