596 citations · 3k across the 50 of their papers we have counts for
Showing cs.CCShow all
3 papers · 1 filter
cs.CC2012★ 1 cited
Hamming Approximation of NP Witnesses
Daniel Sheldon, Neal E. Young
Given a satisfiable 3-SAT formula, how hard is it to find an assignment to the variables that has Hamming distance at most n/2 to a satisfying assignment? More generally, consider…
cs.CC2002★ 45 cited
Simple Strategies for Large Zero-Sum Games with Applications to Complexity Theory
Richard Lipton, Neal E. Young
Von Neumann's Min-Max Theorem guarantees that each player of a zero-sum matrix game has an optimal mixed strategy. This paper gives an elementary proof that each player has a near-…
cs.CC2002★ 29 cited
Lecture Notes on Evasiveness of Graph Properties
Laszlo Lovasz, Neal E. Young
This report presents notes from the first eight lectures of the class Many Models of Complexity taught by Laszlo Lovasz at Princeton University in the fall of 1990. The topic is ev…