{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,27]],"date-time":"2026-06-27T07:46:55Z","timestamp":1782546415243,"version":"3.54.5"},"publisher-location":"Cham","reference-count":24,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032297594","type":"print"},{"value":"9783032297600","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,6,28]],"date-time":"2026-06-28T00:00:00Z","timestamp":1782604800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,6,28]],"date-time":"2026-06-28T00:00:00Z","timestamp":1782604800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2027]]},"DOI":"10.1007\/978-3-032-29760-0_8","type":"book-chapter","created":{"date-parts":[[2026,6,27]],"date-time":"2026-06-27T07:05:49Z","timestamp":1782543949000},"page":"66-74","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Circuit Complexity of\u00a0Hierarchical Knowledge Tracing"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0009-1034-453X","authenticated-orcid":false,"given":"Naiming","family":"Liu","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0721-8999","authenticated-orcid":false,"given":"Richard","family":"Baraniuk","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4409-1341","authenticated-orcid":false,"given":"Shashank","family":"Sonkar","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,6,28]]},"reference":[{"key":"8_CR1","doi-asserted-by":"crossref","unstructured":"Allender, E.: A note on the power of threshold circuits. In: 30th Annual Symposium on Foundations of Computer Science, pp. 580\u2013584. IEEE Computer Society (1989)","DOI":"10.1109\/SFCS.1989.63538"},{"key":"8_CR2","doi-asserted-by":"crossref","unstructured":"Arora, S., Barak, B.: Computational complexity: a modern approach. Cambridge University Press (2009)","DOI":"10.1017\/CBO9780511804090"},{"key":"8_CR3","doi-asserted-by":"crossref","unstructured":"Chen, P., Lu, Y., Zheng, V.W., Pian, Y.: Prerequisite-driven deep knowledge tracing. In: 2018 IEEE International Conference on Data Mining (ICDM), pp. 39\u201348. IEEE (2018)","DOI":"10.1109\/ICDM.2018.00019"},{"key":"8_CR4","doi-asserted-by":"crossref","unstructured":"Chiang, D., Cholak, P.: Overcoming a theoretical limitation of self-attention, arXiv preprint. arXiv:2202.12172 (2022)","DOI":"10.18653\/v1\/2022.acl-long.527"},{"issue":"4","key":"8_CR5","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1007\/BF01099821","volume":"4","author":"AT Corbett","year":"1994","unstructured":"Corbett, A.T., Anderson, J.R.: Knowledge tracing: modeling the acquisition of procedural knowledge. User Model. User-Adap. Inter. 4(4), 253\u2013278 (1994)","journal-title":"User Model. User-Adap. Inter."},{"key":"8_CR6","doi-asserted-by":"crossref","unstructured":"Ghosh, A., Heffernan, N., Lan, A.S.: Context-aware attentive knowledge tracing. In: Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 2330\u20132339 (2020)","DOI":"10.1145\/3394486.3403282"},{"key":"8_CR7","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1162\/tacl_a_00306","volume":"8","author":"M Hahn","year":"2020","unstructured":"Hahn, M.: Theoretical limitations of self-attention in neural sequence models. Trans. Associat. Comput. Linguist. 8, 156\u2013171 (2020)","journal-title":"Trans. Associat. Comput. Linguist."},{"issue":"2","key":"8_CR8","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/0022-0000(93)90001-D","volume":"46","author":"A Hajnal","year":"1993","unstructured":"Hajnal, A., Maass, W., Pudl\u00e1k, P., Szegedy, M., Tur\u00e1n, G.: Threshold circuits of bounded depth. J. Comput. Syst. Sci. 46(2), 129\u2013154 (1993)","journal-title":"J. Comput. Syst. Sci."},{"key":"8_CR9","doi-asserted-by":"crossref","unstructured":"H\u00e5stad, J., Goldmann, M.: On the power of small-depth threshold circuits. Comput. Complexity 1(2), 113\u2013129 (1991)","DOI":"10.1007\/BF01272517"},{"key":"8_CR10","doi-asserted-by":"crossref","unstructured":"Liu, N., Wang, Z., Baraniuk, R., Lan, A.: Open-ended knowledge tracing for computer science education. In: Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pp. 3849\u20133862 (2022)","DOI":"10.18653\/v1\/2022.emnlp-main.254"},{"key":"8_CR11","doi-asserted-by":"publisher","first-page":"531","DOI":"10.1162\/tacl_a_00562","volume":"11","author":"W Merrill","year":"2023","unstructured":"Merrill, W., Sabharwal, A.: The parallelism tradeoff: limitations of log-precision transformers. Trans. Associat. Comput. Linguist. 11, 531\u2013545 (2023)","journal-title":"Trans. Associat. Comput. Linguist."},{"key":"8_CR12","doi-asserted-by":"publisher","first-page":"843","DOI":"10.1162\/tacl_a_00493","volume":"10","author":"W Merrill","year":"2022","unstructured":"Merrill, W., Sabharwal, A., Smith, N.A.: Saturated transformers are constant-depth threshold circuits. Trans. Associat. Comput. Linguist. 10, 843\u2013856 (2022)","journal-title":"Trans. Associat. Comput. Linguist."},{"key":"8_CR13","doi-asserted-by":"crossref","unstructured":"Nakagawa, H., Iwasawa, Y., Matsuo, Y.: Graph-based knowledge tracing: modeling student proficiency using graph neural network. In: IEEE\/WIC\/ACM International Conference on Web Intelligence, pp. 156\u2013163. (2019)","DOI":"10.1145\/3350546.3352513"},{"key":"8_CR14","unstructured":"Pandey, S., Karypis, G.: A self-attentive model for knowledge tracing, arXiv preprint, arXiv:1907.06837 (2019)"},{"key":"8_CR15","unstructured":"Piech, C., et al.: Deep knowledge tracing. In: Advances in Neural Information Processing Systems, p. 28 (2015)"},{"issue":"3","key":"8_CR16","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1016\/0022-0000(81)90038-6","volume":"22","author":"WL Ruzzo","year":"1981","unstructured":"Ruzzo, W.L.: On uniform circuit complexity. J. Comput. Syst. Sci. 22(3), 365\u2013383 (1981)","journal-title":"J. Comput. Syst. Sci."},{"key":"8_CR17","unstructured":"Sonkar, S., Baraniuk, R.G.: Deduction under perturbed evidence: probing student simulation (knowledge tracing) capabilities of large language models. In: LLM@ AIED, pp. 26\u201333 (2023)"},{"key":"8_CR18","unstructured":"Sonkar, S., Waters, A.E., Lan, A.S., Grimaldi, P.J., Baraniuk, R.G.: qdkt: question-centric deep knowledge tracing, arXiv preprint arXiv:2005.12442 (2020)"},{"key":"8_CR19","doi-asserted-by":"publisher","first-page":"543","DOI":"10.1162\/tacl_a_00663","volume":"12","author":"L Strobl","year":"2024","unstructured":"Strobl, L., Merrill, W., Weiss, G., Chiang, D., Angluin, D.: What formal languages can transformers express? a survey. Trans. Associat. Comput. Linguist. 12, 543\u2013561 (2024)","journal-title":"Trans. Associat. Comput. Linguist."},{"key":"8_CR20","doi-asserted-by":"crossref","unstructured":"Tong, S., et al.: Structure-based knowledge tracing: an influence propagation view. In: 2020 IEEE international Conference on Data Mining (ICDM), pp. 541\u2013550. IEEE (2020)","DOI":"10.1109\/ICDM50108.2020.00063"},{"key":"8_CR21","doi-asserted-by":"crossref","unstructured":"Vollmer, H.: Introduction to circuit complexity: a uniform approach. Springer Science & Business Media (1999)","DOI":"10.1007\/978-3-662-03927-4"},{"key":"8_CR22","doi-asserted-by":"crossref","unstructured":"Worden, E., Heffernan, C., Heffernan, N., Sonkar, S.: Foundationalassist: an educational dataset for foundational knowledge tracing and pedagogical grounding of llms. arXiv preprint arXiv:2602.00070 (2026)","DOI":"10.1007\/978-3-032-29755-6_36"},{"key":"8_CR23","doi-asserted-by":"crossref","unstructured":"Yao, A.C.: Circuits and local computation. In: Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing, pp. 186\u2013196. (1989)","DOI":"10.1145\/73007.73025"},{"key":"8_CR24","doi-asserted-by":"crossref","unstructured":"Zhang, J., Shi, X., King, I., Yeung, D.Y.: Dynamic key-value memory networks for knowledge tracing. In: Proceedings of the 26th International Conference on World Wide Web, pp. 765\u2013774 (2017)","DOI":"10.1145\/3038912.3052580"}],"container-title":["Lecture Notes in Computer Science","Artificial Intelligence in Education"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-29760-0_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,27]],"date-time":"2026-06-27T07:06:00Z","timestamp":1782543960000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-29760-0_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,28]]},"ISBN":["9783032297594","9783032297600"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-29760-0_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,6,28]]},"assertion":[{"value":"28 June 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"AIED","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Artificial Intelligence in Education","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Seoul","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Korea (Republic of)","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29 June 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"3 July 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"aied2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.aied-conference.org\/2026","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}