93 citations · 183 across the 19 of their papers we have counts for
Showing 2010Show all
3 papers · 1 filter
cs.DS2010★ 9 cited
Improved Parameterized Algorithms for Constraint Satisfaction
Eun Jung Kim, Ryan Williams
For many constraint satisfaction problems, the algorithm which chooses a random assignment achieves the best possible approximation ratio. For instance, a simple random assignment…
cs.CC2010★ 5 cited
Resolving the Complexity of Some Data Privacy Problems
Jeremiah Blocki, Ryan Williams
We formally study two methods for data sanitation that have been used extensively in the database community: k-anonymity and l-diversity. We settle several open problems concerning…
cs.CC2010
Alternation-Trading Proofs, Linear Programming, and Lower Bounds
Ryan Williams
A fertile area of recent research has demonstrated concrete polynomial time lower bounds for solving natural hard problems on restricted computational models. Among these problems…