{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T05:53:57Z","timestamp":1775282037580,"version":"3.50.1"},"reference-count":8,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1992,6,1]],"date-time":"1992-06-01T00:00:00Z","timestamp":707356800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[1992,6]]},"DOI":"10.1007\/bf01204724","type":"journal-article","created":{"date-parts":[[2005,2,25]],"date-time":"2005-02-25T17:36:37Z","timestamp":1109352997000},"page":"221-226","source":"Crossref","is-referenced-by-count":14,"title":["A combinatorial approach to complexity"],"prefix":"10.1007","volume":"12","author":[{"given":"P.","family":"Pudl\u00e1k","sequence":"first","affiliation":[]},{"given":"V.","family":"R\u00f6dl","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[1992,6,1]]},"reference":[{"key":"BF01204724_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/TIT.1979.1055985","volume":"25","author":"L. Lov\u00e1sz","year":"1979","unstructured":"L. Lov\u00e1sz: On the Shannon capacity of graphs,IEEE Transactions of Information theory,IT-25 (1979), 1\u20137.","journal-title":"IEEE Transactions of Information theory, IT"},{"key":"BF01204724_CR2","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/0012-365X(89)90171-4","volume":"78","author":"T. D. Parsons","year":"1989","unstructured":"T. D. Parsons, andT. Pisanski: Vector representations of graphs, to appear inDiscrete Math. 78 (1989), 143\u2013154.","journal-title":"Discrete Math."},{"key":"BF01204724_CR3","doi-asserted-by":"crossref","unstructured":"R. Paturi, andJ. Simon: Probabilistic communication complexity,25-th FOCS (1984), 118\u2013126.","DOI":"10.1109\/SFCS.1984.715908"},{"key":"BF01204724_CR4","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1007\/BF00279952","volume":"25","author":"P. Pudl\u00e1k","year":"1988","unstructured":"P. Pudl\u00e1k, V. R\u00f6dl, andP. Savick\u00fd: Graph complexity,Acta Informatica 25 (1988), 515\u2013535.","journal-title":"Acta Informatica"},{"key":"BF01204724_CR5","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/BF02122698","volume":"10","author":"A. A. Razborov","year":"1990","unstructured":"A. A. Razborov: Applications of matrix methods for the theory of lower bounds in computational complexity,Combinatorica 10 (1990), 81\u201393.","journal-title":"Combinatorica"},{"key":"BF01204724_CR6","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/0012-365X(89)90142-8","volume":"74","author":"J. Reiterman","year":"1989","unstructured":"J. Reiterman, V. R\u00f6dl, andE. \u0160i\u0148ajov\u00e1: Geometrical embeddings of graphs,Discrete Math. 74 (1989), 291\u2013319.","journal-title":"Discrete Math."},{"key":"BF01204724_CR7","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/BF02187736","volume":"4","author":"J. Reiterman","year":"1989","unstructured":"J. Reiterman, V. R\u00f6dl, andE. \u0160i\u0148ajov\u00e1: Embeddings of graphs in euclidean spaces,Discrete Comput Geom. 4 (1989), 349\u2013364.","journal-title":"Discrete Comput Geom."},{"key":"BF01204724_CR8","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1090\/S0002-9947-1968-0226281-1","volume":"133","author":"H. E. Warren","year":"1968","unstructured":"H. E. Warren: Lower bounds for approximations by nonlinear manifolds,Transactions AMS 133 (1968), 167\u2013178.","journal-title":"Transactions AMS"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01204724.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01204724\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01204724","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01204724.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,23]],"date-time":"2024-12-23T23:45:57Z","timestamp":1734997557000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01204724"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,6]]},"references-count":8,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1992,6]]}},"alternative-id":["BF01204724"],"URL":"https:\/\/doi.org\/10.1007\/bf01204724","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,6]]}}}