Arbeitspapier
A Lower Bound on Computational Complexity Given by Revelation Mechanisms
This paper establishes an elementary lower bound on the computational complexity of smooth functions between Euclidean spaces(actually, smooth manifolds). The main motivation for this comes from mechanism design theory. The complexity of computations required by a mechanism determines an element of the costs associated with that mechanism. The lower bound presented in this paper is useful in part because it does not require specification in detail of the computations to be performed by the mechanism, but depends only on the goal function that the mechanism is to realize or implement.
- Sprache
-
Englisch
- Erschienen in
-
Series: Discussion Paper ; No. 1085
- Klassifikation
-
Wirtschaft
- Ereignis
-
Geistige Schöpfung
- (wer)
-
Mount, Kenneth R.
Reiter, Stanley
- Ereignis
-
Veröffentlichung
- (wer)
-
Northwestern University, Kellogg School of Management, Center for Mathematical Studies in Economics and Management Science
- (wo)
-
Evanston, IL
- (wann)
-
1994
- Handle
- Letzte Aktualisierung
-
10.03.2025, 11:43 MEZ
Datenpartner
Dieses Objekt wird bereitgestellt von:
ZBW - Deutsche Zentralbibliothek für Wirtschaftswissenschaften - Leibniz-Informationszentrum Wirtschaft. Bei Fragen zum Objekt wenden Sie sich bitte an den Datenpartner.
ZBW - Deutsche Zentralbibliothek für Wirtschaftswissenschaften - Leibniz-Informationszentrum Wirtschaft. Bei Fragen zum Objekt wenden Sie sich bitte an den Datenpartner.
Objekttyp
- Arbeitspapier
Beteiligte
- Mount, Kenneth R.
- Reiter, Stanley
- Northwestern University, Kellogg School of Management, Center for Mathematical Studies in Economics and Management Science
Entstanden
- 1994
Ähnliche Objekte (12)
Inferring Lower Bounds for Runtime Complexity
Why are Proof Complexity Lower Bounds Hard?
Complexity theoretic lower bounds on cryptographic functions
Number theoretic methods in cryptography : complexity lower bounds
Hadamard tensors and lower bounds on multiparty communication complexity
CROSSING Winter School 2016: Query Complexity and Lower Bounds (1)
CROSSING Winter School 2016: Query Complexity and Lower Bounds (2)
Cryptographic applications of analytic number theory : complexity lower bounds and pseudorandomness
Essential Revelation Mechanisms and Computational Complexity
Lower bounds on computation time for various models in computational complexity theory
Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement
Complexity Bounds for Block-IPs
Inferring Lower Bounds for Runtime Complexity
Why are Proof Complexity Lower Bounds Hard?
Complexity theoretic lower bounds on cryptographic functions
Number theoretic methods in cryptography : complexity lower bounds
Hadamard tensors and lower bounds on multiparty communication complexity
CROSSING Winter School 2016: Query Complexity and Lower Bounds (1)
CROSSING Winter School 2016: Query Complexity and Lower Bounds (2)
Cryptographic applications of analytic number theory : complexity lower bounds and pseudorandomness
Essential Revelation Mechanisms and Computational Complexity
Lower bounds on computation time for various models in computational complexity theory
Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement
Complexity Bounds for Block-IPs
Inferring Lower Bounds for Runtime Complexity
Why are Proof Complexity Lower Bounds Hard?
Complexity theoretic lower bounds on cryptographic functions
Number theoretic methods in cryptography : complexity lower bounds
Hadamard tensors and lower bounds on multiparty communication complexity
CROSSING Winter School 2016: Query Complexity and Lower Bounds (1)
CROSSING Winter School 2016: Query Complexity and Lower Bounds (2)
Cryptographic applications of analytic number theory : complexity lower bounds and pseudorandomness
Essential Revelation Mechanisms and Computational Complexity
Lower bounds on computation time for various models in computational complexity theory
Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement