45 citations · 65 across the 7 of their papers we have counts for
Showing cs.CCShow all
3 papers · 1 filter
cs.CC2012
Simulating Special but Natural Quantum Circuits
Richard J. Lipton, Kenneth W. Regan, Atri Rudra
We identify a sub-class of BQP that captures certain structural commonalities among many quantum algorithms including Shor's algorithms. This class does not contain all of BQP (e.g…
cs.CC2010★ 15 cited
On Tractable Exponential Sums
Jin-Yi Cai, Xi Chen, Richard Lipton +1
We consider the problem of evaluating certain exponential sums. These sums take the form , where each x_i is summed over…
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-…