On the Implementation of Huge Random Objects
We initiate a general study of the feasibility of implementing (huge) random objects, and demonstrate its applicability to a number of areas in which random objects occur naturally. We highlight two types of measures of the quality of the implementation (with respect to the desired specification): T...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Society of Industrial and Applied Mathematics (SIAM)
2011
|
| Online Access: | http://hdl.handle.net/1721.1/60920 https://orcid.org/0000-0003-4728-1535 |
| _version_ | 1826201172372881408 |
|---|---|
| author | Goldreich, Oded Goldwasser, Shafi Nussboim, Asaf |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Goldreich, Oded Goldwasser, Shafi Nussboim, Asaf |
| author_sort | Goldreich, Oded |
| collection | MIT |
| description | We initiate a general study of the feasibility of implementing (huge) random objects, and demonstrate its applicability to a number of areas in which random objects occur naturally. We highlight two types of measures of the quality of the implementation (with respect to the desired specification): The first type corresponds to various standard notions of indistinguishability (applied to function ensembles), whereas the second type is a novel notion that we call truthfulness. Intuitively, a truthful implementation of a random object of Type T must (always) be an object of Type T, and not merely be indistinguishable from a random object of Type T. Our formalism allows for the consideration of random objects that satisfy some fixed property (or have some fixed structure) as well as the consideration of objects supporting complex queries. For example, we consider the truthful implementation of random Hamiltonian graphs as well as supporting complex queries regarding such graphs (e.g., providing the next vertex along a fixed Hamiltonian path in such a graph). |
| first_indexed | 2024-09-23T11:47:21Z |
| format | Article |
| id | mit-1721.1/60920 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T11:47:21Z |
| publishDate | 2011 |
| publisher | Society of Industrial and Applied Mathematics (SIAM) |
| record_format | dspace |
| spelling | mit-1721.1/609202022-10-01T06:02:31Z On the Implementation of Huge Random Objects Goldreich, Oded Goldwasser, Shafi Nussboim, Asaf Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Goldwasser, Shafi Goldwasser, Shafi We initiate a general study of the feasibility of implementing (huge) random objects, and demonstrate its applicability to a number of areas in which random objects occur naturally. We highlight two types of measures of the quality of the implementation (with respect to the desired specification): The first type corresponds to various standard notions of indistinguishability (applied to function ensembles), whereas the second type is a novel notion that we call truthfulness. Intuitively, a truthful implementation of a random object of Type T must (always) be an object of Type T, and not merely be indistinguishable from a random object of Type T. Our formalism allows for the consideration of random objects that satisfy some fixed property (or have some fixed structure) as well as the consideration of objects supporting complex queries. For example, we consider the truthful implementation of random Hamiltonian graphs as well as supporting complex queries regarding such graphs (e.g., providing the next vertex along a fixed Hamiltonian path in such a graph). 2011-02-11T15:56:32Z 2011-02-11T15:56:32Z 2010-05 2010-04 Article http://purl.org/eprint/type/JournalArticle 0097-5397 1095-7111 http://hdl.handle.net/1721.1/60920 Goldreich, Oded, Shafi Goldwasser, and Asaf Nussboim. “On the Implementation of Huge Random Objects.” SIAM Journal on Computing 39.7 (2010): 2761-2822. © 2010 Society for Industrial and Applied Mathematics https://orcid.org/0000-0003-4728-1535 en_US http://dx.doi.org/10.1137/080722771 SIAM Journal on Computing Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Society of Industrial and Applied Mathematics (SIAM) SIAM |
| spellingShingle | Goldreich, Oded Goldwasser, Shafi Nussboim, Asaf On the Implementation of Huge Random Objects |
| title | On the Implementation of Huge Random Objects |
| title_full | On the Implementation of Huge Random Objects |
| title_fullStr | On the Implementation of Huge Random Objects |
| title_full_unstemmed | On the Implementation of Huge Random Objects |
| title_short | On the Implementation of Huge Random Objects |
| title_sort | on the implementation of huge random objects |
| url | http://hdl.handle.net/1721.1/60920 https://orcid.org/0000-0003-4728-1535 |
| work_keys_str_mv | AT goldreichoded ontheimplementationofhugerandomobjects AT goldwassershafi ontheimplementationofhugerandomobjects AT nussboimasaf ontheimplementationofhugerandomobjects |