-
This dissertation is an in-depth discussion of the theory and applications of span programs. These objects, first introduced in the context of classical counting branching programs by Karchmer and Wigderson, are a model of computation (i.e. they encode 2-output functions) and can be compiled into...
-
This dissertation contains a series of studies on 19th century philosophy of mathematics. The essays are linked together by two common threads: Bolzano's theory of collections on the one hand, and the emergence of modern sets and analysis in the 19th century on the other. Bolzano is often mention...
-
The research covered in this thesis is dedicated to provable post-quantum security of hash functions. Post-quantum security provides security guarantees against quantum attackers. We focus on analyzing the sponge construction, a cryptographic construction used in the standardized hash function SH...
-
This thesis proposes a new, cognitive perspective on the meaning representations and verification of natural language quantifiers. According to the traditional, logical view, quantity words are represented in the form of truth conditions shared across language users. However, a growing body of ev...
-
This dissertation gathers a series of studies on speech acts that appear in contexts of disagreement, and non-cooperative conversations. Seminal works in philosophy of language often take for granted idealised models of conversations to analyse speech acts. They focus on contexts where participan...
-
This dissertation observes how disciplines shared data practices. Data practices enable scholars and scientists to transform observations into data that can be systematically collected and analysed. Observations and observation practices have shaped the foundations of the modern sciences and huma...
-
In this dissertation we study the fascinating interaction between quantum information theory and many-body physics. Many-body physics broadly are physical systems which are made up of a large number of subsystems. While the laws and principles of quantum mechanics are well known and can be formul...
-
There is considerable excitement around quantum computing because of so-called quantum speedups: quantum algorithms can solve many computational problems faster than their classical counterparts. However, the amount of speedup that is possible varies among different computational problems. It is ...
-
Over the past half century, the advent of the computer has increased our ability to perform computations tremendously. Consequently, we can now solve computational problems much more efficiently than ever before, the effects of which have revolutionized many aspects of society, ranging from how g...
-
The tautologies and admissible rules of a formal system may exceed those of its underlying logic. For example, Diaconescu, Goodman and Myhill showed that any set theory containing the axioms (and schemes) of extensionality, empty set, pairing, separation and choice proves the law of excluded midd...
-
A classic question in the study of human cognition is: what are the learning biases that make it possible for them to learn and process language? A similar question can now be asked in the study of machine intelligence: to build machine learning models for language, what are the necessary inducti...