{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:03:39Z","timestamp":1725487419892},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540662006"},{"type":"electronic","value":"9783540486862"}],"license":[{"start":{"date-parts":[[1999,1,1]],"date-time":"1999-01-01T00:00:00Z","timestamp":915148800000},"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":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-48686-0_12","type":"book-chapter","created":{"date-parts":[[2007,7,16]],"date-time":"2007-07-16T11:54:12Z","timestamp":1184586852000},"page":"123-133","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["On Covering and Rank Problems for Boolean Matrices and Their Applications"],"prefix":"10.1007","author":[{"given":"Carsten","family":"Damm","sequence":"first","affiliation":[]},{"given":"Ki Hang","family":"Kim","sequence":"additional","affiliation":[]},{"given":"Fred","family":"Roush","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[1999,6,25]]},"reference":[{"key":"12_CR1","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/S0019-9958(85)80041-3","volume":"64","author":"S. A. Cook","year":"1985","unstructured":"Stephen A. Cook. A taxonomy of problems with fast parallel algorithms. Information and Control, 64:2\u201322, 1985.","journal-title":"Information and Control"},{"key":"12_CR2","doi-asserted-by":"crossref","unstructured":"Carsten Damm. On Boolean vs. modular arithmetic for circuits and communication protocols. Forschungsbericht 98-06, Universit\u00e4t Trier, 1998.","DOI":"10.1007\/BFb0055829"},{"key":"12_CR3","first-page":"63","volume":"30","author":"C. Damm","year":"1994","unstructured":"Carsten Damm, Matthias Krause, Christoph Meinel, and Stephan Waack. Separating oblivious linear length MOD p -branching program classes. Journal of Information Processing and Cybernetics EIK, 30:63\u201375, 1994.","journal-title":"Journal of Information Processing and Cybernetics EIK"},{"key":"12_CR4","unstructured":"Carsten Damm, Matthias Krause, Christoph Meinel, and Stephan Waack. On relations between counting communication complexity classes. Journal of computer and System Sciences, (to appear), 1998."},{"key":"12_CR5","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"326","DOI":"10.1007\/3-540-58338-6_79","volume-title":"Proc. of MFCS'94","author":"M. Dietzfelbinger","year":"1994","unstructured":"M. Dietzfelbinger, J. Hromkovi\u010d, and G. Schnitger. A comparison of two lower bound methods for communication complexity. In Proc. of MFCS'94, volume 841 of Lecture Notes in Computer Science, pages 326\u2013336. Springer-Verlag, 1994."},{"key":"12_CR6","unstructured":"P. Erd\u0151s and J. Spencer. Probabilistic Methods in Combinatorics. Academic Press, 1974."},{"key":"12_CR7","unstructured":"W. Feller. An Introduction to Probability Theory and its Applications, Vol.II. Wiley, 1971."},{"key":"12_CR8","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/BF01303207","volume":"13","author":"J. Friedman","year":"1993","unstructured":"J. Friedman. A note on matrix rigidity. Combinatorica, 13:235\u2013239, 1993.","journal-title":"Combinatorica"},{"key":"12_CR9","volume-title":"Boolean Matrix Theory and Applications","author":"K. H. Kim","year":"1982","unstructured":"Ki Hang Kim. Boolean Matrix Theory and Applications. Marcel Dekker, New York, 1982."},{"key":"12_CR10","first-page":"7","volume":"2","author":"J. Koml\u00f3s","year":"1965","unstructured":"J. Koml\u00f3s. On the determinant of (0,1)-matrices. Studia Sci. Math. Hungar., 2:7\u201321, 1965.","journal-title":"Studia Sci. Math. Hungar."},{"key":"12_CR11","doi-asserted-by":"publisher","first-page":"553","DOI":"10.1007\/BF01204170","volume":"28","author":"M. Krause","year":"1995","unstructured":"Matthias Krause and Stephan Waack. Variation ranks of communication matrices and lower bounds for depth-two circuits having nearly symmetric gates with unbounded fan-in. Mathematical Systems Theory, 28:553\u2013564, 1995.","journal-title":"Mathematical Systems Theory"},{"key":"12_CR12","doi-asserted-by":"crossref","unstructured":"E. Kushilevitz and Noam Nisan. Communication Complexity. Cambridge University Press, 1996.","DOI":"10.1017\/CBO9780511574948"},{"key":"12_CR13","unstructured":"Satyanarayana V. Lokam. Spectral methods for matrix rigidity with applications to size-depth tradeoffs and communication complexity. In FOCS, pages 6\u201315, 1995."},{"key":"12_CR14","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/BF02574357","volume":"44","author":"G. Markowsky","year":"1992","unstructured":"George Markowsky. Ordering d-classes and computing schein rank is hard. Semigroup Forum, 44:373\u2013375, 1992.","journal-title":"Semigroup Forum"},{"key":"12_CR15","unstructured":"A. Razborov. On rigid matrices. manuscript, June 1989."},{"key":"12_CR16","doi-asserted-by":"publisher","first-page":"598","DOI":"10.1007\/BF01137685","volume":"41","author":"A. A. Razborov","year":"1987","unstructured":"Alexander A. Razborov. Lower bounds for the size of bounded depth with basis {\u2227, \u2295}. Mathematical Notes of the Academy of Sciences of the USSR, 41:598\u2013607, 1987.","journal-title":"Mathematical Notes of the Academy of Sciences of the USSR"},{"key":"12_CR17","doi-asserted-by":"crossref","unstructured":"Roman Smolensky. Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In 19th ACM STOC, pages 77\u201382, 1987.","DOI":"10.1145\/28395.28404"},{"key":"12_CR18","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/0304-3975(93)90214-E","volume":"113","author":"J. Tarui","year":"1993","unstructured":"Jun Tarui. Probabilistic polynomials, AC 0 functions, and the polynomial-time hierarchy. Theoretical Computer Science, 113:167\u2013183, 1993.","journal-title":"Theoretical Computer Science"},{"key":"12_CR19","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"L. Valiant","year":"1979","unstructured":"Leslie Valiant. The complexity of computing the permanent. TCS, 8:189\u2013201, 1979.","journal-title":"TCS"},{"key":"12_CR20","doi-asserted-by":"crossref","unstructured":"Andy Yao. Some complexity questions related to distributive computing. In Proceedings of the 11th Annual ACM Symposium on the Theory of Computing, 1979.","DOI":"10.1145\/800135.804414"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48686-0_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,19]],"date-time":"2021-08-19T06:50:55Z","timestamp":1629355855000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48686-0_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540662006","9783540486862"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/3-540-48686-0_12","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[1999]]},"assertion":[{"value":"25 June 1999","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}