{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:24:36Z","timestamp":1759638276539},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2014,2,8]],"date-time":"2014-02-08T00:00:00Z","timestamp":1391817600000},"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":[[2014,4]]},"DOI":"10.1007\/s00493-014-2367-1","type":"journal-article","created":{"date-parts":[[2014,2,8]],"date-time":"2014-02-08T06:32:47Z","timestamp":1391841167000},"page":"173-206","source":"Crossref","is-referenced-by-count":9,"title":["Constructing Ramsey graphs from Boolean function representations"],"prefix":"10.1007","volume":"34","author":[{"given":"Parikshit","family":"Gopalan","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,2,8]]},"reference":[{"key":"2367_CR1","volume-title":"Proceedings of the 16th IEEE Conference on Computational Complexity (CCC)","author":"N Alon","year":"2001","unstructured":"N. Alon and R. Beigel: Lower bounds for approximations by low degree polynomials over \u2124m, Proceedings of the 16th IEEE Conference on Computational Complexity (CCC), 2001."},{"key":"2367_CR2","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1007\/PL00009824","volume":"18","author":"N Alon","year":"1998","unstructured":"N. Alon: The Shannon capacity of a union, Combinatorica, 18 (1998), 301\u2013310.","journal-title":"Combinatorica"},{"key":"2367_CR3","unstructured":"B. Barak: A simple explicit construction of an n \u00f5(log n) Ramsey graph, arXiv.org, math.CO\/0601651, 2006."},{"key":"2367_CR4","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1007\/BF01263424","volume":"4","author":"D A Barrington","year":"1994","unstructured":"D. A. Barrington, R. Beigel and S. Rudich: Representing Boolean functions as polynomials modulo composite numbers, Computational Complexity, 4 (1994), 367\u2013382.","journal-title":"Computational Complexity"},{"key":"2367_CR5","volume-title":"Linear Algebra Methods in Combinatorics, Preliminary version 2","author":"L Babai","year":"1992","unstructured":"L. Babai and P. Frankl: Linear Algebra Methods in Combinatorics, Preliminary version 2, 1992."},{"key":"2367_CR6","doi-asserted-by":"crossref","unstructured":"L. Babai, P. Frankl, S. Kutin, and D. \u0160tefankovi\u010d Set systems with restricted intersections modulo prime powers, Journal of Combinatorial Theory, Ser. A, 95 (2001).","DOI":"10.1006\/jcta.2000.3149"},{"key":"2367_CR7","volume-title":"Proceedings of the 44th Annual Symposium on the Foundations of Computer Science (FOCS)","author":"N Bhatnagar","year":"2003","unstructured":"N. Bhatnagar, P. Gopalan and R. J. Lipton: Symmetric polynomials over \u2124m and simultaneous communication protocols, Proceedings of the 44 th Annual Symposium on the Foundations of Computer Science (FOCS), 2003."},{"key":"2367_CR8","volume-title":"Proceedings of the 38th Symposium on Theory of Computing (STOC)","author":"B Barak","year":"2006","unstructured":"B. Barak, A. Rao, R. Shaltiel and A. Wigderson: 2-source dispersers for n o(1) entropy and Ramsey graphs beating the Frankl-Wilson construction, in: Proceedings of the 38th Symposium on Theory of Computing (STOC), 2006."},{"key":"2367_CR9","volume-title":"Proceedings of the 51 st Annual Symposium on the Foundations of Computer Science (FOCS)","author":"Z Dvir","year":"2010","unstructured":"Z. Dvir, P. Gopalan and S. Yekhanin: Matching vector codes, in: Proceedings of the 51 st Annual Symposium on the Foundations of Computer Science (FOCS), 2010."},{"key":"2367_CR10","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1145\/1536414.1536422","volume-title":"41st ACM Symposium on Theory of Computing (STOC)","author":"K Efremenko","year":"2009","unstructured":"K. Efremenko: 3-query locally decodable codes of subexponential length, in: 41st ACM Symposium on Theory of Computing (STOC), 39\u201344, 2009."},{"key":"2367_CR11","doi-asserted-by":"crossref","first-page":"292","DOI":"10.1090\/S0002-9904-1947-08785-1","volume":"53","author":"P Erd\u00f6s","year":"1947","unstructured":"P. Erd\u00f6s: Some remarks on the theory of graphs. Bulletin of the A. M. S., 53 (1947), 292\u2013294.","journal-title":"Bulletin of the A. M. S."},{"key":"2367_CR12","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1007\/BF02579457","volume":"1","author":"P Frankl","year":"1981","unstructured":"P. Frankl and R. Wilson: Intersection theorems with geometric consequences, Combinatorica, 1 (1981), 357\u2013368.","journal-title":"Combinatorica"},{"key":"2367_CR13","volume-title":"Proceedings of the 21st IEEE Conference on Computational Complexity (CCC)","author":"P Gopalan","year":"2006","unstructured":"P. Gopalan: Constructing Ramsey graphs from Boolean function representations, in: Proceedings of the 21st IEEE Conference on Computational Complexity (CCC), 2006."},{"key":"2367_CR14","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete algorithms (SODA)","author":"P Gopalan","year":"2006","unstructured":"P. Gopalan: Query-efficient algorithms for polynomial interpolation over composites, in: Proceedings of the ACM-SIAM Symposium on Discrete algorithms (SODA), 2006."},{"key":"2367_CR15","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1007\/PL00001599","volume":"9","author":"F Green","year":"2000","unstructured":"F. Green: Complex Fourier technique for lower bounds on the mod-m degree, Computational Complexity, 9 (2000), 16\u201338.","journal-title":"Computational Complexity"},{"key":"2367_CR16","unstructured":"V. Grolmusz: On the weak mod m representation of Boolean functions. Chicago Journal of Theoretical Computer Science, 2 (1995)."},{"key":"2367_CR17","first-page":"82","volume-title":"COCOON","author":"V Grolmusz","year":"1997","unstructured":"V. Grolmusz: On set systems with restricted intersections modulo a composite number, in: COCOON, pages 82\u201390, 1997."},{"key":"2367_CR18","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1007\/s004930070032","volume":"20","author":"V Grolmusz","year":"2000","unstructured":"V. Grolmusz: Superpolynomial size set-systems with restricted intersections mod 6 and explicit Ramsey graphs, Combinatorica, 20 (2000), 71\u201386.","journal-title":"Combinatorica"},{"key":"2367_CR19","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1016\/S0196-6774(02)00204-3","volume":"44","author":"V Grolmusz","year":"2002","unstructured":"V. Grolmusz: Constructing set systems with prescribed intersection sizes, Journal of Algorithms, 44 (2002), 321\u2013337.","journal-title":"Journal of Algorithms"},{"key":"2367_CR20","volume-title":"An Introduction to the Theory of Numbers","author":"G H Hardy","year":"1985","unstructured":"G. H. Hardy and E. M. Wright: An Introduction to the Theory of Numbers, Clarendon Press, Oxford, 1985."},{"key":"2367_CR21","unstructured":"S. Kutin: Constructing large set systems with given intersection sizes modulo composite numbers, Combinatorics, Probability and Computing, 11 (2002)."},{"key":"2367_CR22","volume-title":"Constructing Ramsey graphs from small probability spaces","author":"M Naor","year":"1993","unstructured":"M. Naor: Constructing Ramsey graphs from small probability spaces, Manuscript, available online, 1993."},{"key":"2367_CR23","volume-title":"Electronic Colloquium on Computational Complexity (ECCC)","author":"P Raghavendra","year":"2007","unstructured":"P. Raghavendra: A note on Yekhanin\u2019s locally decodable codes, in: Electronic Colloquium on Computational Complexity (ECCC), TR07-016, 2007."},{"key":"2367_CR24","volume-title":"Proceedings of the 34 th Annual Symposium on Foundations of Computer Science (FOCS)","author":"R Smolensky","year":"1993","unstructured":"R. Smolensky: On representations by low-degree polynomials, in: Proceedings of the 34 th Annual Symposium on Foundations of Computer Science (FOCS), 1993."},{"key":"2367_CR25","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1007\/PL00001597","volume":"7","author":"G Tardos","year":"1998","unstructured":"G. Tardos and D. Barrington: A lower bound on the mod 6 degree of the OR function, Computational Complexity, 7 (1998), 99\u2013108.","journal-title":"Computational Complexity"},{"key":"2367_CR26","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1137\/S0895480193255505","volume":"9","author":"S-C Tsai","year":"1996","unstructured":"S.-C. Tsai: Lower bounds on representing Boolean functions as polynomials in \u2124m, SIAM Journal of Discrete Mathematics, 9 (1996), 55\u201362.","journal-title":"SIAM Journal of Discrete Mathematics"},{"key":"2367_CR27","volume-title":"26th IEEE Conference on Computational Complexity (CCC 2011)","author":"R Williams","year":"2011","unstructured":"R. Williams: Non-uniform acc circuit lower bounds. in: 26th IEEE Conference on Computational Complexity (CCC 2011), 2011."},{"key":"2367_CR28","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1326554.1326555","volume":"55","author":"S Yekhanin","year":"2008","unstructured":"S. Yekhanin: Towards 3-query locally decodable codes of subexponential length, Journal of the ACM, 55 (2008), 1\u201316.","journal-title":"Journal of the ACM"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-014-2367-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00493-014-2367-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-014-2367-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T13:13:32Z","timestamp":1565183612000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00493-014-2367-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,2,8]]},"references-count":28,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,4]]}},"alternative-id":["2367"],"URL":"https:\/\/doi.org\/10.1007\/s00493-014-2367-1","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,2,8]]}}}