{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,4]],"date-time":"2026-05-04T13:49:55Z","timestamp":1777902595141,"version":"3.51.4"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T00:00:00Z","timestamp":1777593600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T00:00:00Z","timestamp":1777593600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["1813930"],"award-info":[{"award-number":["1813930"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["2114116"],"award-info":[{"award-number":["2114116"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2026,6]]},"abstract":"Abstract<\/jats:title>\n \n It is shown that there exists\n \n \n $$\\varvec{f}\\varvec{:} \\varvec{\\{}\\varvec{0}\\varvec{,}\\varvec{1}\\varvec{\\}}^{\\varvec{n\/2}} \\varvec{\\times } \\varvec{\\{0,1\\}}^{\\varvec{n\/2}} \\varvec{\\rightarrow } \\varvec{\\{0,1\\}}$$<\/jats:tex-math>\n \n \n \n f<\/mml:mi>\n <\/mml:mrow>\n \n :<\/mml:mo>\n <\/mml:mrow>\n \n {<\/mml:mo>\n <\/mml:mrow>\n \n 0<\/mml:mn>\n <\/mml:mrow>\n \n ,<\/mml:mo>\n <\/mml:mrow>\n \n 1<\/mml:mn>\n <\/mml:mrow>\n \n \n }<\/mml:mo>\n <\/mml:mrow>\n \n n<\/mml:mi>\n \/<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n \n \u00d7<\/mml:mo>\n <\/mml:mrow>\n \n \n {<\/mml:mo>\n 0<\/mml:mn>\n ,<\/mml:mo>\n 1<\/mml:mn>\n }<\/mml:mo>\n <\/mml:mrow>\n \n n<\/mml:mi>\n \/<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n \n \u2192<\/mml:mo>\n <\/mml:mrow>\n \n {<\/mml:mo>\n 0<\/mml:mn>\n ,<\/mml:mo>\n 1<\/mml:mn>\n }<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n in E\n \n \n $$^\\textbf{NP}$$<\/jats:tex-math>\n \n \n \n \n NP<\/mml:mi>\n <\/mml:mmultiscripts>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n such that for every\n \n \n $$\\varvec{2}^{\\varvec{n\/2}} \\varvec{\\times } \\varvec{2}^{\\varvec{n\/2}}$$<\/jats:tex-math>\n \n \n \n \n 2<\/mml:mn>\n <\/mml:mrow>\n \n n<\/mml:mi>\n \/<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n \n \u00d7<\/mml:mo>\n <\/mml:mrow>\n \n \n 2<\/mml:mn>\n <\/mml:mrow>\n \n n<\/mml:mi>\n \/<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n matrix\n \n \n $$\\varvec{M}$$<\/jats:tex-math>\n \n \n M<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n of rank\n \n \n $$\\varvec{\\le } \\varvec{\\rho }$$<\/jats:tex-math>\n \n \n \n \u2264<\/mml:mo>\n <\/mml:mrow>\n \n \u03c1<\/mml:mi>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n we have\n \n \n $$\\mathbb {P}_{\\varvec{x,y}}\\varvec{[}\\varvec{f}\\varvec{(x,y)}\\varvec{\\ne } \\varvec{M}_{\\varvec{x,y}}\\varvec{]} \\varvec{\\ge } \\varvec{1\/2-2}^{\\varvec{-\\Omega }\\varvec{(k)}}$$<\/jats:tex-math>\n \n \n \n P<\/mml:mi>\n \n x<\/mml:mi>\n ,<\/mml:mo>\n y<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msub>\n \n [<\/mml:mo>\n <\/mml:mrow>\n \n f<\/mml:mi>\n <\/mml:mrow>\n \n (<\/mml:mo>\n x<\/mml:mi>\n ,<\/mml:mo>\n y<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \n \u2260<\/mml:mo>\n <\/mml:mrow>\n \n \n M<\/mml:mi>\n <\/mml:mrow>\n \n x<\/mml:mi>\n ,<\/mml:mo>\n y<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msub>\n \n ]<\/mml:mo>\n <\/mml:mrow>\n \n \u2265<\/mml:mo>\n <\/mml:mrow>\n \n \n 1<\/mml:mn>\n \/<\/mml:mo>\n 2<\/mml:mn>\n -<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n \n \n -<\/mml:mo>\n \u03a9<\/mml:mi>\n <\/mml:mrow>\n \n (<\/mml:mo>\n k<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , whenever\n \n \n $$\\varvec{\\log } \\varvec{\\rho } \\varvec{\\le } \\varvec{\\delta } \\varvec{n\/k}\\varvec{(}\\varvec{\\log } \\varvec{n} \\varvec{+} \\varvec{k}\\varvec{)}$$<\/jats:tex-math>\n \n \n \n log<\/mml:mo>\n <\/mml:mrow>\n \n \u03c1<\/mml:mi>\n <\/mml:mrow>\n \n \u2264<\/mml:mo>\n <\/mml:mrow>\n \n \u03b4<\/mml:mi>\n <\/mml:mrow>\n \n n<\/mml:mi>\n \/<\/mml:mo>\n k<\/mml:mi>\n <\/mml:mrow>\n \n (<\/mml:mo>\n <\/mml:mrow>\n \n log<\/mml:mo>\n <\/mml:mrow>\n \n n<\/mml:mi>\n <\/mml:mrow>\n \n +<\/mml:mo>\n <\/mml:mrow>\n \n k<\/mml:mi>\n <\/mml:mrow>\n \n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n for a sufficiently small\n \n \n $$\\varvec{\\delta } \\varvec{>} \\varvec{0}$$<\/jats:tex-math>\n \n \n \n \u03b4<\/mml:mi>\n <\/mml:mrow>\n \n ><\/mml:mo>\n <\/mml:mrow>\n \n 0<\/mml:mn>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , and\n \n \n $$\\varvec{n}$$<\/jats:tex-math>\n \n \n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n is large enough. This generalizes recent results which bound below the probability by\n \n \n $$\\varvec{1\/2-\\Omega }\\varvec{(1)}$$<\/jats:tex-math>\n \n \n \n 1<\/mml:mn>\n \/<\/mml:mo>\n 2<\/mml:mn>\n -<\/mml:mo>\n \u03a9<\/mml:mi>\n <\/mml:mrow>\n \n (<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n or apply to constant-depth circuits.\n <\/jats:p>","DOI":"10.1007\/s00224-026-10268-9","type":"journal-article","created":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T11:34:05Z","timestamp":1777635245000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Average-Case Rigidity Lower Bounds"],"prefix":"10.1007","volume":"70","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0249-4203","authenticated-orcid":false,"given":"Xuangui","family":"Huang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Emanuele","family":"Viola","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,5,1]]},"reference":[{"issue":"1","key":"10268_CR1","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1145\/2559903","volume":"61","author":"R Williams","year":"2014","unstructured":"Williams, R.: Nonuniform ACC circuit lower bounds. J. ACM 61(1), 2\u20131232 (2014)","journal-title":"J. ACM"},{"issue":"3","key":"10268_CR2","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"},{"key":"10268_CR3","doi-asserted-by":"crossref","unstructured":"Williams, R.: Natural proofs versus derandomization. In: ACM Symp. on the Theory of Computing (STOC) (2013)","DOI":"10.1145\/2488608.2488612"},{"key":"10268_CR4","doi-asserted-by":"crossref","unstructured":"Williams, R.: New algorithms and lower bounds for circuits with linear threshold gates. In: ACM Symp. on the Theory of Computing (STOC) (2014)","DOI":"10.1145\/2591796.2591858"},{"key":"10268_CR5","doi-asserted-by":"crossref","unstructured":"Alman, J., Chan, T.M., Williams, R.: Polynomial representations of threshold functions and algorithmic applications. In: IEEE Symp. on Foundations of Computer Science (FOCS) (2016)","DOI":"10.1109\/FOCS.2016.57"},{"key":"10268_CR6","unstructured":"Tamaki, S.: A satisfiability algorithm for depth two circuits with a sub-quadratic number of symmetric and threshold gates. Electronic Colloquium on Computational Complexity (ECCC) 23, 100 (2016)"},{"key":"10268_CR7","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 (2018)","DOI":"10.1007\/978-3-319-77404-6_24"},{"key":"10268_CR8","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 (2018)","DOI":"10.1145\/3188745.3188910"},{"key":"10268_CR9","unstructured":"Rajgopal, N., Santhanam, R., Srinivasan, S.: Deterministically counting satisfying assignments for constant-depth circuits with parity gates, with implications for lower bounds. In: Symp. on Math. Foundations of Computer Science (MFCS). LIPIcs, vol. 117, pp. 78\u201317815 (2018)"},{"key":"10268_CR10","doi-asserted-by":"crossref","unstructured":"Alman, J., Chen, L.: Efficient construction of rigid matrices using an NP oracle. In: IEEE Symp. on Foundations of Computer Science (FOCS), pp. 1034\u20131055 (2019)","DOI":"10.1109\/FOCS.2019.00067"},{"key":"10268_CR11","doi-asserted-by":"crossref","unstructured":"Chen, L.: Non-deterministic quasi-polynomial time is average-case hard for ACC circuits. In: IEEE Symp. on Foundations of Computer Science (FOCS) (2019)","DOI":"10.1109\/FOCS.2019.00079"},{"key":"10268_CR12","unstructured":"Chen, L., Williams, R.R.: Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity. In: IEEE Conf. on Computational Complexity (CCC), pp. 19\u201311943 (2019)"},{"key":"10268_CR13","unstructured":"Vyas, N., Williams, R.: Lower bounds against sparse symmetric functions of ACC circuits: Expanding the reach of #SAT algorithms. In: Symp. on Theoretical Aspects of Computer Science (STACS) (2020)"},{"key":"10268_CR14","doi-asserted-by":"crossref","unstructured":"Chen, L., Ren, H.: Strong average-case circuit lower bounds from non-trivial derandomization. In: ACM Symp. on the Theory of Computing (STOC) (2020)","DOI":"10.1145\/3357713.3384279"},{"key":"10268_CR15","unstructured":"Viola, E.: New lower bounds for probabilistic degree and AC0 with parity gates. Electronic Coll. on Computational Complexity (ECCC) 27, 15 (2020)"},{"key":"10268_CR16","doi-asserted-by":"crossref","unstructured":"Chen, L., Lyu, X., Williams, R.: Almost everywhere circuit lower bounds from non-trivial derandomization. In: IEEE Symp. on Foundations of Computer Science (FOCS) (2020)","DOI":"10.1109\/FOCS46700.2020.00009"},{"key":"10268_CR17","unstructured":"Bhangale, A., Harsha, P., Paradise, O., Tal, A.: Rigid matrices from rectangular PCPs. In: IEEE Symp. on Foundations of Computer Science (FOCS) (2020)"},{"key":"10268_CR18","doi-asserted-by":"crossref","unstructured":"Valiant, L.G.: Graph-theoretic arguments in low-level complexity. In: 6th Symposium on Mathematical Foundations of Computer Science. Lecture Notes in Computer Science, vol. 53, pp. 162\u2013176 (1977)","DOI":"10.1007\/3-540-08353-7_135"},{"key":"10268_CR19","unstructured":"Servedio, R.A., Viola, E.: On a special case of rigidity. Available at http:\/\/www.ccs.neu.edu\/home\/viola\/ (2012)"},{"key":"10268_CR20","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. Akademiya Nauk SSSR. Matematicheskie Zametki 41(4), 598\u2013607 (1987). English translation in Mathematical Notes of the Academy of Sci. of the USSR, 41(4):333\u2013338, 1987","DOI":"10.1007\/BF01137685"},{"key":"10268_CR21","doi-asserted-by":"crossref","unstructured":"Smolensky, R.: Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In: 19th ACM Symp. on the Theory of Computing (STOC), pp. 77\u201382 (1987)","DOI":"10.1145\/28395.28404"},{"key":"10268_CR22","doi-asserted-by":"crossref","unstructured":"Smolensky, R.: On representations by low-degree polynomials. In: 34th IEEE IEEE Symp. on Foundations of Computer Science (FOCS), pp. 130\u2013138 (1993)","DOI":"10.1109\/SFCS.1993.366874"},{"key":"10268_CR23","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Viola, E.: Short PCPs with projection queries. In: Coll. on Automata, Languages and Programming (ICALP) (2014)","DOI":"10.1007\/978-3-662-43948-7_14"},{"key":"10268_CR24","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 Symp. on the Theory of Computing (STOC) (2021)","DOI":"10.1145\/3406325.3451132"},{"key":"10268_CR25","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Nisan, N., Wigderson, A.: On Yao\u2019s XOR-lemma. In: Studies in Complexity and Cryptography. Lecture Notes in Computer Science, vol. 6650, pp. 273\u2013301 (2011)","DOI":"10.1007\/978-3-642-22670-0_23"},{"key":"10268_CR26","doi-asserted-by":"crossref","unstructured":"Williams, R.: Improving exhaustive search implies superpolynomial lower bounds. In: 42nd ACM Symp. on the Theory of Computing (STOC), pp. 231\u2013240 (2010)","DOI":"10.1145\/1806689.1806723"},{"key":"10268_CR27","doi-asserted-by":"crossref","unstructured":"Chan, T.M., Williams, R.: Deterministic APSP, orthogonal vectors, and more: Quickly derandomizing Razborov-Smolensky. In: ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 1246\u20131255 (2016)","DOI":"10.1137\/1.9781611974331.ch87"},{"key":"10268_CR28","unstructured":"Paradise, O.: Smooth and strong PCPs. In: ACM Innovations in Theoretical Computer Science conf. (ITCS), pp. 2\u20131241 (2020)"},{"key":"10268_CR29","unstructured":"Bhangale, A., Harsha, P., Paradise, O., Tal, A.: Rigid matrices from rectangular PCPs. Electron. Colloquium Comput. Complex. TR20-075 (2020)"},{"issue":"4","key":"10268_CR30","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."},{"issue":"1","key":"10268_CR31","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"},{"key":"10268_CR32","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. Theoret. Comput. Sci. 26, 327\u2013333 (1983)","journal-title":"Theoret. Comput. Sci."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-026-10268-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-026-10268-9","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-026-10268-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T11:34:14Z","timestamp":1777635254000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-026-10268-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,1]]},"references-count":32,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,6]]}},"alternative-id":["10268"],"URL":"https:\/\/doi.org\/10.1007\/s00224-026-10268-9","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,1]]},"assertion":[{"value":"16 October 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 March 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 May 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"32"}}