3 papers
cs.GT2002
Combinatorial Auctions with Decreasing Marginal Utilities
Benny Lehmann, Daniel Lehmann, Noam Nisan
In most of microeconomic theory, consumers are assumed to exhibit decreasing marginal utilities. This paper considers combinatorial auctions among such submodular buyers. The valua…
quant-ph1998
Quantum Circuits with Mixed States
Dorit Aharonov, Alexei Kitaev, Noam Nisan
We define the model of quantum circuits with density matrices, where non-unitary gates are allowed. Measurements in the middle of the computation, noise and decoherence are impleme…
quant-ph1996
Limitations of Noisy Reversible Computation
D. Aharonov, M. Ben-Or, R. Impagliazzo +1
Noisy computation and reversible computation have been studied separately, and it is known that they are as powerful as unrestricted computation. We study the case where both noise…