{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:09:37Z","timestamp":1760202577141,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642029264"},{"type":"electronic","value":"9783642029271"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-02927-1_12","type":"book-chapter","created":{"date-parts":[[2009,7,4]],"date-time":"2009-07-04T08:37:10Z","timestamp":1246696630000},"page":"119-131","source":"Crossref","is-referenced-by-count":8,"title":["Towards a Study of Low-Complexity Graphs"],"prefix":"10.1007","author":[{"given":"Sanjeev","family":"Arora","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Steurer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Avi","family":"Wigderson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"12_CR1","doi-asserted-by":"crossref","unstructured":"Mitzenmacher, M.: A brief history of generative models for power law and lognormal distributions. Internet Mathematics\u00a01(2) (2003)","DOI":"10.1080\/15427951.2004.10129088"},{"key":"12_CR2","unstructured":"Hopcroft, J.: Personal communication (2008)"},{"issue":"3","key":"12_CR3","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/S0019-9958(83)80004-7","volume":"56","author":"H. Galperin","year":"1983","unstructured":"Galperin, H., Wigderson, A.: Succinct representations of graphs. Inf. Control\u00a056(3), 183\u2013198 (1983)","journal-title":"Inf. Control"},{"issue":"3","key":"12_CR4","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1016\/S0022-0000(05)80063-7","volume":"48","author":"C.H. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: On the complexity of the parity argument and other inefficient proofs of existence. J. Comput. Syst. Sci.\u00a048(3), 498\u2013532 (1994)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"12_CR5","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1006\/jcss.1997.1494","volume":"55","author":"A.A. Razborov","year":"1997","unstructured":"Razborov, A.A., Rudich, S.: Natural proofs. J. Comput. Syst. Sci.\u00a055(1), 24\u201335 (1997)","journal-title":"J. Comput. Syst. Sci."},{"key":"12_CR6","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090","volume-title":"Computational Complexity: A modern approach","author":"S. Arora","year":"2009","unstructured":"Arora, S., Barak, B.: Computational Complexity: A modern approach. Cambridge University Press, Cambridge (2009)"},{"key":"12_CR7","unstructured":"Nickel, C.L.M.: Random dot product graphs: A model for social networks. PhD thesis, Johns Hopkins University (2008)"},{"key":"12_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1007\/978-3-540-77004-6_11","volume-title":"Algorithms and Models for the Web-Graph","author":"S.J. Young","year":"2007","unstructured":"Young, S.J., Scheinerman, E.R.: Random dot product graph models for social networks. In: Bonato, A., Chung, F.R.K. (eds.) WAW 2007. LNCS, vol.\u00a04863, pp. 138\u2013149. Springer, Heidelberg (2007)"},{"key":"12_CR9","doi-asserted-by":"crossref","unstructured":"Ajtai, M.: $\\sigma_1^1$ formulae on finite structures. Annals of Pure Appl. Logic 24 (1983)","DOI":"10.1016\/0168-0072(83)90038-6"},{"issue":"1","key":"12_CR10","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/BF01744431","volume":"17","author":"M.L. Furst","year":"1984","unstructured":"Furst, M.L., Saxe, J.B., Sipser, M.: Parity, circuits, and the polynomial-time hierarchy. Mathematical Systems Theory\u00a017(1), 13\u201327 (1984)","journal-title":"Mathematical Systems Theory"},{"key":"12_CR11","doi-asserted-by":"crossref","unstructured":"Viola, E.: On approximate majority and probabilistic time. In: IEEE Conference on Computational Complexity, pp. 155\u2013168 (2007)","DOI":"10.1109\/CCC.2007.16"},{"key":"12_CR12","doi-asserted-by":"crossref","unstructured":"Hastad, J.: Almost optimal lower bounds for small depth circuits. In: Randomness and Computation, pp. 6\u201320. JAI Press (1989)","DOI":"10.1145\/12130.12132"},{"key":"12_CR13","doi-asserted-by":"crossref","unstructured":"Hoory, S., Linial, N., Wigderson, A.: Expander graphs and their applications. Bull. AMS (43), 439\u2013561 (2006)","DOI":"10.1090\/S0273-0979-06-01126-8"},{"key":"12_CR14","doi-asserted-by":"crossref","unstructured":"Capalbo, M.R., Reingold, O., Vadhan, S.P., Wigderson, A.: Randomness conductors and constant-degree lossless expanders. In: STOC, pp. 659\u2013668 (2002)","DOI":"10.1145\/509907.510003"},{"key":"12_CR15","unstructured":"Alon, N., Schwartz, O., Shapira, A.: An elementary construction of constant-degree expanders. In: SODA, pp. 454\u2013458 (2007)"},{"key":"12_CR16","doi-asserted-by":"crossref","unstructured":"Reingold, O., Vadhan, S.P., Wigderson, A.: Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors. In: FOCS, pp. 3\u201313 (2000)","DOI":"10.1109\/SFCS.2000.892006"},{"key":"12_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1007\/3-540-45726-7_20","volume-title":"Randomization and Approximation Techniques in Computer Science","author":"M. Mihail","year":"2002","unstructured":"Mihail, M., Papadimitriou, C.H.: On the eigenvalue power law. In: Rolim, J.D.P., Vadhan, S.P. (eds.) RANDOM 2002. LNCS, vol.\u00a02483, pp. 254\u2013262. Springer, Heidelberg (2002)"},{"key":"#cr-split#-12_CR18.1","doi-asserted-by":"crossref","unstructured":"Babai, L., Fortnow, L., Lund, L.: Non-deterministic exponential time has two-prover interactive protocols. Computational Complexity??1, 3???40 (1991);","DOI":"10.1007\/BF01200056"},{"key":"#cr-split#-12_CR18.2","unstructured":"Prelim version FOCS 1990"},{"key":"#cr-split#-12_CR19.1","doi-asserted-by":"crossref","unstructured":"Arora, S., Safra, S.: Probabilistic checking of proofs: A new characterization of??NP. Journal of the ACM??45(1), 70???122 (1998);","DOI":"10.1145\/273865.273901"},{"key":"#cr-split#-12_CR19.2","unstructured":"Prelim version FOCS 1992"},{"key":"#cr-split#-12_CR20.1","doi-asserted-by":"crossref","unstructured":"Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification and the hardness of approximation problems. Journal of the ACM??45(3), 501???555 (1998);","DOI":"10.1145\/278298.278306"},{"key":"#cr-split#-12_CR20.2","unstructured":"Prelim version FOCS 1992"},{"key":"#cr-split#-12_CR21.1","doi-asserted-by":"crossref","unstructured":"Feige, U., Goldwasser, S., Lov??sz, L., Safra, S., Szegedy, M.: Interactive proofs and the hardness of approximating cliques. Journal of the ACM??43(2), 268???292 (1996);","DOI":"10.1145\/226643.226652"},{"key":"#cr-split#-12_CR21.2","unstructured":"Prelim version FOCS 1991"},{"issue":"6","key":"12_CR22","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"M.X. Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM\u00a042(6), 1115\u20131145 (1995)","journal-title":"J. ACM"},{"issue":"4","key":"12_CR23","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1145\/285055.285060","volume":"45","author":"O. Goldreich","year":"1998","unstructured":"Goldreich, O., Goldwasser, S., Ron, D.: Property testing and its connection to learning and approximation. J. ACM\u00a045(4), 653\u2013750 (1998)","journal-title":"J. ACM"},{"issue":"2","key":"12_CR24","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1016\/S0022-0000(03)00008-4","volume":"67","author":"N. Alon","year":"2003","unstructured":"Alon, N., de la Vega, W.F., Kannan, R., Karpinski, M.: Random sampling and approximation of max-csps. J. Comput. Syst. Sci.\u00a067(2), 212\u2013243 (2003)","journal-title":"J. Comput. Syst. Sci."},{"key":"12_CR25","doi-asserted-by":"crossref","unstructured":"Alon, N., Fischer, E., Newman, I., Shapira, A.: A combinatorial characterization of the testable graph properties: it\u2019s all about regularity. In: STOC, pp. 251\u2013260 (2006)","DOI":"10.1145\/1132516.1132555"},{"key":"12_CR26","doi-asserted-by":"crossref","unstructured":"Benjamini, I., Schramm, O., Shapira, A.: Every minor-closed property of sparse graphs is testable. In: STOC, pp. 393\u2013402 (2008)","DOI":"10.1145\/1374376.1374433"},{"key":"12_CR27","doi-asserted-by":"crossref","unstructured":"Frieze, A.M., Kannan, R., Vempala, S.: Fast monte-carlo algorithms for finding low-rank approximations. In: FOCS, pp. 370\u2013378 (1998)","DOI":"10.1109\/SFCS.1998.743487"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-02927-1_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,10]],"date-time":"2025-02-10T17:53:44Z","timestamp":1739210024000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-02927-1_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642029264","9783642029271"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-02927-1_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}