{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T09:10:01Z","timestamp":1737364201129,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540551881"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/3-540-46766-1_18","type":"book-chapter","created":{"date-parts":[[2007,8,11]],"date-time":"2007-08-11T15:03:27Z","timestamp":1186844607000},"page":"232-241","source":"Crossref","is-referenced-by-count":0,"title":["Functional Inversion and Communication Complexity"],"prefix":"10.1007","author":[{"given":"Shang-Hua","family":"Teng","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"18_CR1","doi-asserted-by":"crossref","unstructured":"R. Boppana and J. Lagarias. One-way functions and circuit complexity. In Proc. Struc. in Compl. Theory, Lect. Notes. in Computer Science., 1986.","DOI":"10.1007\/3-540-16486-3_89"},{"key":"18_CR2","doi-asserted-by":"crossref","unstructured":"H. Gazit, G. L. Miller, and S.-H. Teng. Optimal tree contraction in the EREW Model, In Current Computations edited by S. K. Tewsburg, B. W. Dickinson, and S. C. Schwartz\u201d, pages 139\u2013156. 1988.","DOI":"10.1007\/978-1-4684-5511-3_9"},{"key":"18_CR3","doi-asserted-by":"crossref","unstructured":"J. Hastad. Computational Limitations for Small Depth Circuits. The MIT Press, 1986.","DOI":"10.1145\/12130.12132"},{"key":"18_CR4","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo and S. Rudich. Limits on the provable consequence of one-way permutations. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing, pages 44\u201361. 1989.","DOI":"10.1145\/73007.73012"},{"key":"18_CR5","volume-title":"Foundations of Computing","author":"F. T. Leighton","year":"1983","unstructured":"Frank Thomson Leighton. complexity Issues in VLSI. Foundations of Computing. MIT Press, Cambridge, MA, 1983."},{"key":"18_CR6","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"R.J. Lipton","year":"1979","unstructured":"R.J. Lipton and R.E. Tarjan. A separator theorem for planar graphs. SIAM J. of Appl. Math., 36:177\u2013189, April 1979.","journal-title":"SIAM J. of Appl. Math."},{"key":"18_CR7","doi-asserted-by":"crossref","unstructured":"G. L. Miller. Finding small simple cycle separators for 2-connected planar graphs. In Proceedings of the 16th Annual ACM Sympoisum on Theory of Computing, pages 376\u2013382, 1984.","DOI":"10.1145\/800057.808703"},{"key":"18_CR8","doi-asserted-by":"crossref","unstructured":"G. L. Miller and J. H. Reif. Parallel tree contraction and its applications. In 26th Symposium on Foundations of Computer Science, pages 478\u2013489, 1985.","DOI":"10.1109\/SFCS.1985.43"},{"key":"18_CR9","unstructured":"J. Pearl. Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison Wesley, 1984."},{"issue":"2","key":"18_CR10","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1145\/359340.359342","volume":"21","author":"R. Rivest","year":"1978","unstructured":"R. Rivest, A. Shamir, and L. Adleman. A method for obtaining digitial signatures and public-key cryptosystems. CACM, 21(2):120\u2013126, 1978.","journal-title":"CACM"},{"key":"18_CR11","doi-asserted-by":"crossref","unstructured":"J. Rompel. One-way functions are necessary and sufficient for secure signatures. In Proceedings of the 22th Annual ACM Symposium on Theory of Computing, pages 387\u2013394. 1990.","DOI":"10.1145\/100216.100269"},{"key":"18_CR12","doi-asserted-by":"crossref","unstructured":"C. Sturtivant and Z.-L. Zhang. Efficiently inverting bijections given by straight line programs. In 31st Annual Symposium on Foundations of Computer Science, pages 327\u2013334. 1990.","DOI":"10.1109\/FSCS.1990.89551"},{"key":"18_CR13","doi-asserted-by":"crossref","unstructured":"M. Szegedy. Functions with bounded symmetric communication complexity and circuit with mod m gates. In Proceedings of the 22th Annual ACM Symposium on Theory of Computing, pages 278\u2013286. 1990.","DOI":"10.1145\/100216.100252"},{"key":"18_CR14","unstructured":"S. H. Teng. Fast parallel algorithms for tree-based constraint satisfaction problems. Manuscript, Carnegie Mellon University, 1990."},{"key":"18_CR15","unstructured":"C. D. Thompson. A Complexity Theory for VLSI. PhD thesis, Carnegie-Mellon University, Department of Computer Science, 1980."},{"key":"18_CR16","doi-asserted-by":"crossref","unstructured":"A. C.-C. Yao. Theory and application of trapdoor functions. In 23th Annual Symposium on Foundations of Computer Science, pages 80\u201391. IEEE, 1982.","DOI":"10.1109\/SFCS.1982.45"},{"key":"18_CR17","doi-asserted-by":"crossref","unstructured":"A. C.-C. Yao. Some complexity questions related to distributive computing. In Proceedings of the 11st Annual ACM Symposium on Theory of Computing, pages 209\u2013213. ACM, 1979.","DOI":"10.1145\/800135.804414"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2014 CRYPTO \u201991"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-46766-1_18.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T08:28:14Z","timestamp":1737361694000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-46766-1_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540551881"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/3-540-46766-1_18","relation":{},"subject":[]}}