{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T21:32:51Z","timestamp":1725485571629},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540651420"},{"type":"electronic","value":"9783540495437"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/3-540-49543-6_15","type":"book-chapter","created":{"date-parts":[[2007,6,7]],"date-time":"2007-06-07T02:58:05Z","timestamp":1181185085000},"page":"172-186","source":"Crossref","is-referenced-by-count":6,"title":["Using Approximation Hardness to Achieve Dependable Computation"],"prefix":"10.1007","author":[{"given":"Mike","family":"Burmester","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yvo","family":"Desmedt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yongge","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[1999,6,11]]},"reference":[{"key":"15_CR1","series-title":"PhD Thesis","volume-title":"Probabilistic Checking of Proofs and Hardness of Approximation Problems","author":"S. Arora","year":"1994","unstructured":"S. Arora. Probabilistic Checking of Proofs and Hardness of Approximation Problems. PhD Thesis, CS Division, UC Berkeley, August, 1994."},{"key":"15_CR2","doi-asserted-by":"crossref","unstructured":"S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and intractability of approximation problems. In: Proceedings of 33rd IEEE Symposium on Foundations of Computer Science, pp. 13\u201322, 1992.","DOI":"10.1109\/SFCS.1992.267823"},{"key":"15_CR3","doi-asserted-by":"crossref","unstructured":"S. Arora and S. Safra. Probabilistic checking of proofs: a new characterization of NP. In: Proceedings of 33rd IEEE Symposium on Foundations of Computer Science, pp. 2\u201313, 1992.","DOI":"10.1109\/SFCS.1992.267824"},{"key":"15_CR4","doi-asserted-by":"crossref","unstructured":"A. Beimel and M. Franklin. Reliable communication over partially authenticated networks. In. Proceedings of the WDAG\u2019 97, Lecture Notes in Computer Science 1320, pp. 245\u2013259, Springer Verlag, 1997.","DOI":"10.1007\/BFb0030688"},{"key":"15_CR5","doi-asserted-by":"crossref","unstructured":"M. Bellare. Proof checking and approximation: towards tight results. In: Complexity Theory Column 12, SIGACT News. 27(1), March 1996.","DOI":"10.1145\/230514.571641"},{"issue":"2","key":"15_CR6","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1007\/BF01994876","volume":"32","author":"R. Boppana","year":"1992","unstructured":"R. Boppana and M. Halldorsson. Approximating maximum independent sets by excluding subgraphs. BIT, 32(2), pp. 180\u2013196, 1992.","journal-title":"BIT"},{"key":"15_CR7","doi-asserted-by":"crossref","unstructured":"M. Burmester, Y. Desmedt, and G. Kabatianski. Trust and security: a new look at the Byzantine general problems. In: R. N. Wright and P. G. Neumann, Eds, Network Threats, DIM ACS, Series in Discrete Mathematics and Theoretical Computer Science, AMS, Vol. 38, 1997.","DOI":"10.1090\/dimacs\/038\/08"},{"key":"15_CR8","doi-asserted-by":"crossref","unstructured":"R. Canetti, E. Kushilevitz, R. Ostrovsky, and A. Rosen. Randomness vs. faulttolerance. In: Proceedings of the PODC\u2019 97, pp. 35\u201344, Springer Verlag, 1997.","DOI":"10.1145\/259380.259416"},{"key":"15_CR9","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1145\/358549.358563","volume":"24","author":"D. Chaum","year":"1981","unstructured":"D. Chaum. Untraceable electronic mail, return addresses and digital pseudonyms. Communication of the ACM, Vol. 24, pp. 84\u201388, 1981.","journal-title":"Communication of the ACM"},{"key":"15_CR10","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1016\/0196-6774(82)90004-9","volume":"3","author":"D. Dolev","year":"1982","unstructured":"D. Dolev. The Byzantine generals strike again. J. of Algorithms, 3, pp. 14\u201330, 1982.","journal-title":"J. of Algorithms"},{"issue":"1","key":"15_CR11","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1145\/138027.138036","volume":"40","author":"D. Dolev","year":"1993","unstructured":"D. Dolev, C. Dwork, O. Waarts, and M. Yung. Perfectly secure message transmission. J. of the ACM, 40(1), pp. 17\u201347, 1993.","journal-title":"J. of the ACM"},{"key":"15_CR12","doi-asserted-by":"crossref","unstructured":"S. Dolev and R. Ostrovsky. Efficient anonymous multicast and reception. In: Advances in Cryptology, Crypto\u201997, pp. 395\u2013409, Springer Verlag, 1997.","DOI":"10.1007\/BFb0052251"},{"key":"15_CR13","doi-asserted-by":"crossref","unstructured":"U. Feige, S. Goldwasser, L. Lovasz, S. Safra, and M. Szegedy. Approximating clique is almost NP-complete. In: Proceedings of 32nd IEEE Symposium on Foundations of Computer Science, pp. 2\u201311, 1991.","DOI":"10.1109\/SFCS.1991.185341"},{"key":"15_CR14","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"M.R. Garey and D.S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, San Francisco, 1979."},{"key":"15_CR15","series-title":"PhD thesis","volume-title":"Issues of Fault Tolerance in Concurrent Computations","author":"V. Hadzilacos","year":"1984","unstructured":"V. Hadzilacos. Issues of Fault Tolerance in Concurrent Computations. PhD thesis, Harvard University, Cambridge, MA, 1984."},{"issue":"2","key":"15_CR16","first-page":"374","volume":"32","author":"L. Lamport","year":"1982","unstructured":"L. Lamport, R. Shostak, and M. Pease. The Byzantine generals problem. J. of the ACM, 32(2), pp. 374\u2013382, 1982.","journal-title":"J. of the ACM"},{"key":"15_CR17","unstructured":"N. J. Nilsson. Principles of Artificial Intelligence. Tioga, 1980."},{"key":"15_CR18","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C. Papadimitriou","year":"1991","unstructured":"C. Papadimitriou and M. Yannakakis. Optimization, approximation and complexity classes. Journal of Computer and System Sciences, 43, 425\u2013440, 1991.","journal-title":"Journal of Computer and System Sciences"},{"key":"15_CR19","doi-asserted-by":"crossref","unstructured":"C. Rackoff and S. Simon. Cryptographic defense against traffic analysis. In: Proceedings of the STOC 93, pp. 672\u2013681.","DOI":"10.1145\/167088.167260"},{"key":"15_CR20","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1145\/321958.321975","volume":"23","author":"S. Sahni","year":"1976","unstructured":"S. Sahni and T. Gonzalez. P-complete approximation problems. J. of the ACM, 23, pp. 555\u2013565, 1976.","journal-title":"J. of the ACM"},{"key":"15_CR21","series-title":"PhD. thesis","volume-title":"Efficient Checking of Polynomials and Proofs and the Hardness of Approximation Problems","author":"M. Sudan","year":"1992","unstructured":"M. Sudan. Efficient Checking of Polynomials and Proofs and the Hardness of Approximation Problems. PhD. thesis, U. C. Berkeley, 1992."},{"key":"15_CR22","unstructured":"Y. Wang, Y. Desmedt, and M. Burmester. Hardness of dependable computation with multiple inputs. Submitted."}],"container-title":["Lecture Notes in Computer Science","Randomization and Approximation Techniques in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-49543-6_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,28]],"date-time":"2019-04-28T19:45:58Z","timestamp":1556480758000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-49543-6_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540651420","9783540495437"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/3-540-49543-6_15","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[1998]]}}}