{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,8]],"date-time":"2025-01-08T05:41:10Z","timestamp":1736314870729,"version":"3.32.0"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1994,9,1]],"date-time":"1994-09-01T00:00:00Z","timestamp":778377600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J. Cryptology"],"published-print":{"date-parts":[[1994,9]]},"DOI":"10.1007\/bf02318547","type":"journal-article","created":{"date-parts":[[2006,2,15]],"date-time":"2006-02-15T17:53:28Z","timestamp":1140026008000},"page":"153-170","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Functional inversion and communication complexity"],"prefix":"10.1007","volume":"7","author":[{"given":"Shang-Hua","family":"Teng","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"BF02318547_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1007\/3-540-16486-3_89","volume-title":"Proc. Structure in Complexity Theory","author":"R. Boppana","year":"1986","unstructured":"R. Boppana and J. Lagarias. One-way functions and circuit complexity. InProc. Structure in Complexity Theory. Lecture Notes in Computer Science, Vol. 223. Springer-Verlag, Berlin, pages 51\u201365, 1986."},{"key":"BF02318547_CR2","doi-asserted-by":"crossref","unstructured":"S. A. Cook. The complexity of theorem-proving procedures.Proceedings of the 3nd Annual ACM Symposium on Theory of Computing, pages 151\u2013158, 1971.","DOI":"10.1145\/800157.805047"},{"key":"BF02318547_CR3","volume-title":"Computer and Intractability: a Guide to the Theory of NP-Completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson.Computer and Intractability: a Guide to the Theory of NP-Completeness. Freeman, San Francisco, 1979."},{"key":"BF02318547_CR4","first-page":"139","volume-title":"Current Computations","author":"H. Gazit","year":"1988","unstructured":"H. Gazit, G. L. Miller, and S.-H. Teng. Optimal tree contraction in the EREW model. InCurrent Computations (S. K. Tewsburg, B. W. Dickinson, and S. C. Schwartz, eds.), Plenum, New York, pages 139\u2013156, 1988."},{"key":"BF02318547_CR5","volume-title":"Computational Limitations for Small Depth Circuits","author":"J. H\u00e5stad","year":"1986","unstructured":"J. H\u00e5stad.Computational Limitations for Small Depth Circuits. MIT Press, Cambridge, MA, 1986."},{"key":"BF02318547_CR6","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/0020-0190(87)90053-6","volume":"26","author":"J. H\u00e5stad","year":"1987","unstructured":"J. H\u00e5stad. One-way permutations inNC 0.Inform. Process. Lett., 26:153\u2013156, 1987.","journal-title":"Inform. Process. Lett."},{"key":"BF02318547_CR7","doi-asserted-by":"crossref","first-page":"492","DOI":"10.1016\/0196-6774(90)90023-8","volume":"11","author":"M.-D. A. Huang","year":"1990","unstructured":"M.-D. A. Huang and S.-H. Teng. Security, verifiability, and universality in distributed computing.J. Algorithms, 11:492\u2013521, 1990.","journal-title":"J. Algorithms"},{"key":"BF02318547_CR8","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo and S. Rudich. Limits on the provable consequence of one-way permutations.Proceedings of the 21st Annual ACM Symposium on Theory of Computing, pages 44\u201361, 1989.","DOI":"10.1145\/73007.73012"},{"issue":"4","key":"BF02318547_CR9","doi-asserted-by":"crossref","first-page":"831","DOI":"10.1145\/322217.322232","volume":"27","author":"R. E. Ladner","year":"1980","unstructured":"R. E. Ladner and M. J. Fischer. Parallel prefix computation.J. Assoc. Comput. Mach., 27(4):831\u2013838, 1980.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF02318547_CR10","volume-title":"Complexity Issues in VLSI","author":"F. T. Leighton","year":"1983","unstructured":"F. T. Leighton.Complexity Issues in VLSI. Foundations of Computing, MIT Press, Cambridge, MA, 1983."},{"issue":"2","key":"BF02318547_CR11","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1137\/0211025","volume":"11","author":"D. Lichtenstein","year":"1982","unstructured":"D. Lichtenstein. Planar formulae and their uses.SIAM J. Comput. 11(2):329\u2013343, 1982.","journal-title":"SIAM J. Comput."},{"issue":"3","key":"BF02318547_CR12","doi-asserted-by":"crossref","first-page":"615","DOI":"10.1137\/0209046","volume":"9","author":"R. J. Lipton","year":"1981","unstructured":"R. J. Lipton and R. E. Tarjan. Applications of planar separator theorem.SIAM J. Comput., 9(3):615\u2013627, 1981.","journal-title":"SIAM J. Comput."},{"key":"BF02318547_CR13","doi-asserted-by":"crossref","unstructured":"G. L. Miller. Finding small simple cycle separators for 2-connected planar graphs.Proceedings of the 16th Annual ACM Symposium on Theory of Computing, pages 376\u2013382, 1984.","DOI":"10.1145\/800057.808703"},{"key":"BF02318547_CR14","doi-asserted-by":"crossref","unstructured":"G. L. Miller and J. H. Reif. Parallel tree contraction and its applications.Proceedings of the 26th Symposium on Foundations of Computer Science, pages 478\u2013489, 1985.","DOI":"10.1109\/SFCS.1985.43"},{"key":"BF02318547_CR15","volume-title":"Heuristics: Intelligent Search Strategies for Problem Solving","author":"J. Pearl","year":"1984","unstructured":"J. Pearl.Heuristics: Intelligent Search Strategies for Problem Solving. Addison-Wesley, Reading, MA, 1984."},{"issue":"2","key":"BF02318547_CR16","doi-asserted-by":"publisher","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.Comm. ACM, 21(2):120\u2013126, 1978.","journal-title":"Comm. ACM"},{"key":"BF02318547_CR17","doi-asserted-by":"crossref","unstructured":"J. Rompel. One-way functions are necessary and sufficient for secure signatures.Proceedings of the 22th Annual ACM Symposium on Theory of Computing, pages 387\u2013394, 1990.","DOI":"10.1145\/100216.100269"},{"key":"BF02318547_CR18","doi-asserted-by":"crossref","unstructured":"C. Sturtivant and Z.-L. Zhang. Efficiently inverting bijections given by straight line programs.Proceedings of the 31st Annual Symposium on Foundations of Computer Science, pages 327\u2013334, 1990.","DOI":"10.1109\/FSCS.1990.89551"},{"key":"BF02318547_CR19","doi-asserted-by":"crossref","unstructured":"M. Szegedy. Functions with bounded symmetric communication complexity and circuit with modm gates.Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, pages 278\u2013286, 1990.","DOI":"10.1145\/100216.100252"},{"key":"BF02318547_CR20","unstructured":"S. H. Teng. Fast parallel algorithms for tree-based constraint satisfaction problems. Manuscript, Carnegie Mellon University, 1990."},{"key":"BF02318547_CR21","unstructured":"C. D. Thompson. A Complexity Theory for VLSI. Ph.D. thesis, Department of Computer Science, Carnegie Mellon University, 1980."},{"issue":"12","key":"BF02318547_CR22","doi-asserted-by":"crossref","first-page":"1171","DOI":"10.1109\/TC.1983.1676178","volume":"32","author":"C. D. Thompson","year":"1983","unstructured":"C. D. Thompson. The VLSI complexity of sorting.IEEE Trans. Comput., 32(12):1171\u20131184, 1983.","journal-title":"IEEE Trans. Comput."},{"key":"BF02318547_CR23","series-title":"Wiley-Teubner Series in Computer Science","volume-title":"The Complexity of Boolean Functions","author":"I. Wegener","year":"1987","unstructured":"I. Wegener.The Complexity of Boolean Functions. Wiley-Teubner Series in Computer Science. Wiley, New York, Teubner, Stuttgart, 1987."},{"key":"BF02318547_CR24","doi-asserted-by":"crossref","unstructured":"A. C.-C. Yao. Some complexity questions related to distributive computing.Proceedings of the 11th Annual ACM Symposium on Theory of Computing, pages 209\u2013213, 1979.","DOI":"10.1145\/800135.804414"},{"key":"BF02318547_CR25","doi-asserted-by":"crossref","unstructured":"A. C.-C. Yao. Theory and application of trapdoor functions.Proceedings of the 23th Anual Symposium on Foundations of Computer Science, pages 80\u201391, 1982.","DOI":"10.1109\/SFCS.1982.45"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02318547.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02318547\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02318547","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02318547.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,7]],"date-time":"2025-01-07T19:43:12Z","timestamp":1736278992000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02318547"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,9]]},"references-count":25,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1994,9]]}},"alternative-id":["BF02318547"],"URL":"https:\/\/doi.org\/10.1007\/bf02318547","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"type":"print","value":"0933-2790"},{"type":"electronic","value":"1432-1378"}],"subject":[],"published":{"date-parts":[[1994,9]]},"assertion":[{"value":"19 December 1991","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 September 1993","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}