{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,3]],"date-time":"2025-10-03T17:48:17Z","timestamp":1759513697467,"version":"3.40.3"},"publisher-location":"Cham","reference-count":31,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030794156"},{"type":"electronic","value":"9783030794163"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"DOI":"10.1007\/978-3-030-79416-3_11","type":"book-chapter","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T18:03:46Z","timestamp":1623866626000},"page":"186-205","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Average-Case Rigidity Lower Bounds"],"prefix":"10.1007","author":[{"given":"Xuangui","family":"Huang","sequence":"first","affiliation":[]},{"given":"Emanuele","family":"Viola","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,6,17]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Alman, J., Chan, T.M., Williams, R.: Polynomial representations of threshold functions and algorithmic applications. In: IEEE Symposium on Foundations of Computer Science (FOCS) (2016)","key":"11_CR1","DOI":"10.1109\/FOCS.2016.57"},{"doi-asserted-by":"crossref","unstructured":"Alman, J., Chen, L.: Efficient construction of rigid matrices using an NP oracle. In: IEEE Symposium on Foundations of Computer Science (FOCS), pp. 1034\u20131055 (2019)","key":"11_CR2","DOI":"10.1109\/FOCS.2019.00067"},{"doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Viola, E.: Short PCPs with projection queries. In: Colloquium on Automata, Languages and Programming (ICALP) (2014)","key":"11_CR3","DOI":"10.1007\/978-3-662-43948-7_14"},{"unstructured":"Bhangale, A., Harsha, P., Paradise, O., Tal, A.: Rigid matrices from rectangular PCPs. In: IEEE Symposium on Foundations of Computer Science (FOCS) (2020)","key":"11_CR4"},{"doi-asserted-by":"crossref","unstructured":"Chan, T.M., Williams, R.: Deterministic APSP, orthogonal vectors, and more: quickly derandomizing razborov-smolensky. In: ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1246\u20131255 (2016)","key":"11_CR5","DOI":"10.1137\/1.9781611974331.ch87"},{"doi-asserted-by":"crossref","unstructured":"Chen, L.: Non-deterministic quasi-polynomial time is average-case hard for ACC circuits. In: IEEE Symposium on Foundations of Computer Science (FOCS) (2019)","key":"11_CR6","DOI":"10.1109\/FOCS.2019.00079"},{"doi-asserted-by":"crossref","unstructured":"Chen, L., Lyu, X.: Inverse-exponential correlation bounds and extremely rigid matrices from a new derandomized XOR lemma. In: ACM Symposium on the Theory of Computing (STOC) (2021)","key":"11_CR7","DOI":"10.1145\/3406325.3451132"},{"doi-asserted-by":"crossref","unstructured":"Chen, L., Lyu, X., Williams, R.: Almost everywhere circuit lower bounds from non-trivial derandomization. In: IEEE Symposium on Foundations of Computer Science (FOCS) (2020)","key":"11_CR8","DOI":"10.1109\/FOCS46700.2020.00009"},{"doi-asserted-by":"crossref","unstructured":"Chen, L., Ren, H.: Strong average-case circuit lower bounds from non-trivial derandomization. In: ACM Symposium on the Theory of Computing (STOC) (2020)","key":"11_CR9","DOI":"10.1145\/3357713.3384279"},{"unstructured":"Chen, L., Williams, R.R.: Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity. In: IEEE Conference on Computational Complexity (CCC), pp. 19:1\u201319:43 (2019)","key":"11_CR10"},{"doi-asserted-by":"crossref","unstructured":"Chen, R., Oliveira, I.C., Santhanam, R.: An average-case lower bound against $$ACC^0$$. In: LATIN. Lecture Notes in Computer Science, vol. 10807, pp. 317\u2013330. Springer (2018)","key":"11_CR11","DOI":"10.1007\/978-3-319-77404-6_24"},{"issue":"4","key":"11_CR12","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1016\/S0022-0000(73)80028-5","volume":"7","author":"SA Cook","year":"1973","unstructured":"Cook, S.A.: A hierarchy for nondeterministic time complexity. J. Comput. Syst. Sci. 7(4), 343\u2013353 (1973)","journal-title":"J. Comput. Syst. Sci."},{"key":"11_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1007\/978-3-642-22670-0_23","volume-title":"Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation","author":"O Goldreich","year":"2011","unstructured":"Goldreich, O., Nisan, N., Wigderson, A.: On Yao\u2019s XOR-Lemma. In: Goldreich, O. (ed.) Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation. LNCS, vol. 6650, pp. 273\u2013301. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-22670-0_23"},{"doi-asserted-by":"crossref","unstructured":"Murray, C., Williams, R.R.: Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP. In: STOC, pp. 890\u2013901. ACM (2018)","key":"11_CR14","DOI":"10.1145\/3188745.3188910"},{"unstructured":"Paradise, O.: Smooth and strong PCPss. In: ACM Innovations in Theoretical Computer Science conf. (ITCS), pp. 2:1\u20132:41 (2020)","key":"11_CR15"},{"doi-asserted-by":"publisher","unstructured":"Rajgopal, N., Santhanam, R., Srinivasan, S.: Deterministically counting satisfying assignments for constant-depth circuits with parity gates, with implications for lower bounds. In: Potapov, I., Spirakis, P.G., Worrell, J. (eds.) Symposium on Mathamatics Foundations of Computer Science (MFCS). LIPIcs, vol. 117, pp. 78:1\u201378:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2018). https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2018.78","key":"11_CR16","DOI":"10.4230\/LIPIcs.MFCS.2018.78"},{"doi-asserted-by":"crossref","unstructured":"Razborov, A.: Lower bounds on the dimension of schemes of bounded depth in a complete basis containing the logical addition function. Math. Notes Acad. Sci. USSR 41(4), 598\u2013607 (1987)","key":"11_CR17","DOI":"10.1007\/BF01137685"},{"issue":"1","key":"11_CR18","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1145\/322047.322061","volume":"25","author":"JI Seiferas","year":"1978","unstructured":"Seiferas, J.I., Fischer, M.J., Meyer, A.R.: Separating nondeterministic time complexity classes. J. ACM 25(1), 146\u2013167 (1978)","journal-title":"J. ACM"},{"unstructured":"Servedio, R.A., Viola, E.: On a special case of rigidity (2012). http:\/\/www.ccs.neu.edu\/home\/viola\/","key":"11_CR19"},{"doi-asserted-by":"crossref","unstructured":"Smolensky, R.: Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In: 19th ACM Symposium on the Theory of Computing (STOC), pp. 77\u201382. ACM (1987)","key":"11_CR20","DOI":"10.1145\/28395.28404"},{"unstructured":"Smolensky, R.: On representations by low-degree polynomials. In: 34th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 130\u2013138 (1993)","key":"11_CR21"},{"unstructured":"Tamaki, S.: A satisfiability algorithm for depth two circuits with a sub-quadratic number of symmetric and threshold gates. Electron. Coll. Comput. Complexity (ECCC) 23, 100 (2016). http:\/\/eccc.hpi-web.de\/report\/2016\/100","key":"11_CR22"},{"key":"11_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1007\/3-540-08353-7_135","volume-title":"Mathematical Foundations of Computer Science 1977","author":"LG Valiant","year":"1977","unstructured":"Valiant, L.G.: Graph-theoretic arguments in low-level complexity. In: Gruska, J. (ed.) MFCS 1977. LNCS, vol. 53, pp. 162\u2013176. Springer, Heidelberg (1977). https:\/\/doi.org\/10.1007\/3-540-08353-7_135"},{"unstructured":"Viola, E.: New lower bounds for probabilistic degree and AC0 with parity gates. Electron. Coll. Computat. Complexity (ECCC) 27, 15 (2020)","key":"11_CR24"},{"unstructured":"Vyas, N., Williams, R.: Lower bounds against sparse symmetric functions of ACC circuits: expanding the reach of #SAT algorithms. In: Symposium on Theoretical Aspects of Computer Science (STACS) (2020)","key":"11_CR25"},{"doi-asserted-by":"crossref","unstructured":"Williams, R.: Improving exhaustive search implies superpolynomial lower bounds. In: 42nd ACM Symposium on the Theory of Computing (STOC), pp. 231\u2013240 (2010)","key":"11_CR26","DOI":"10.1145\/1806689.1806723"},{"issue":"3","key":"11_CR27","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1145\/2034575.2034591","volume":"42","author":"R Williams","year":"2011","unstructured":"Williams, R.: Guest column: a casual tour around a circuit complexity bound. SIGACT News 42(3), 54\u201376 (2011)","journal-title":"SIGACT News"},{"doi-asserted-by":"crossref","unstructured":"Williams, R.: Natural proofs versus derandomization. In: ACM Symposium on the Theory of Computing (STOC) (2013)","key":"11_CR28","DOI":"10.1145\/2488608.2488612"},{"doi-asserted-by":"crossref","unstructured":"Williams, R.: New algorithms and lower bounds for circuits with linear threshold gates. In: ACM Symposium on the Theory of Computing (STOC) (2014)","key":"11_CR29","DOI":"10.1145\/2591796.2591858"},{"doi-asserted-by":"crossref","unstructured":"Williams, R.: Nonuniform ACC circuit lower bounds. J. ACM 61(1), 2:1\u20132:32 (2014). http:\/\/doi.acm.org\/10.1145\/2559903","key":"11_CR30","DOI":"10.1145\/2559903"},{"key":"11_CR31","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1016\/0304-3975(83)90015-4","volume":"26","author":"S Z\u00e1k","year":"1983","unstructured":"Z\u00e1k, S.: A turing machine time hierarchy. Theor. Comput. Sci. 26, 327\u2013333 (1983)","journal-title":"Theor. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Computer Science \u2013 Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-79416-3_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,17]],"date-time":"2021-06-17T23:21:11Z","timestamp":1623972071000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-79416-3_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030794156","9783030794163"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-79416-3_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"17 June 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CSR","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computer Science Symposium in Russia","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Sochi","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Russia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"28 June 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2 July 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"csr2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/logic.pdmi.ras.ru\/csr2021\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"68","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"28","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"41% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.1","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"9.2","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}