What makes social interactions hard? A computational study of intentions, knowledge, and beliefs.


Having a social life is engaging and complicated. Still some of its aspects seem harder than others. For instance, telling the truth is much easier than lying. Deception demands the ability to simulate another's reaction in order to determine if a lie will be believable. It is even harder if the goal of the lie is to manipulate. To successfully incept an idea in someone's mind I need to predict the way he will revise his beliefs and knowledge. How hard is it to be a skillful liar and what makes it hard for others to manipulate our beliefs?

The overall aim of this project is to develop a theory that will evaluate factors responsible for the complexity of human reasoning about knowledge and beliefs of others, i.e., epistemic reasoning. Combining, adapting, and enhancing concepts from philosophical logic, cognitive modeling, and computational complexity theory I aim to identify theoretical boundaries in the complexity of reasoning about information flow. I will investigate the borders between easy and difficult epistemic tasks. Finally, I will show how the theoretical findings may be translated into experimental hypotheses. Further on I hope for my theory to be integrated in computational models of cognition with an eye towards education, clinical psychology, and artificial intelligence.


Book or monography

  • J Szymanik(2016): Quantifiers and Cognition. Logical and Computational Perspectives

Chapter in book

  • A Isaac, A Baltag, S Smets, J. Szymanik, R Verbrugge(2014): Johan van Benthem on Logical and Informational Dynamics pp. 787 - 824 , Amsterdam

Scientific article

  • J. Szymanik, R Verbrugge(2013): Logic and Cognition: Special Issue of Best Papers of the ESSLLI 2012 Workshop Journal of Logic, Language and Information pp. 357 - 362
  • M Zajenkowski, J. Szymanik(2013): Most intelligent people are accurate and some fast people are intelligent. Intelligence, working memory, and semantic processing of quantifiers from a computational perspective Intelligence. A Multidisciplinary Journal pp. 456 - 466
  • J Kontinen, J. Szymanik(2014): A characterization of definability of second-order generalized quantifiers with applications to non-definability Journal of Computer and System Sciences pp. 1152 - 1162
  • L Robaldo, J. Szymanik, B Meijering(2014): On the identification of quantifiers' witness sets Journal of Logic, Language and Information pp. 53 - 81
  • C Degremont, L Kurzen, J. Szymanik(2014): Exploring tractability border in epistemic tasks Synthese pp. 371 - 408
  • M Zajenkowski, M Garraffa, J. Szymanik(2014): Working memory mechanism in proportional quantifier verification Journal of Psycholinguistic Research pp. 839 - 853

Publications for the general public


Project number


Main applicant

Dr. J.K. Szymanik

Affiliated with

Universiteit van Amsterdam, Faculteit der Natuurwetenschappen, Wiskunde en Informatica, Institute for Logic, Language and Computation (ILLC)

Team members

Dr. J.K. Szymanik


16/01/2013 to 15/01/2017