In analogy to mathematical proofs, the goal of a proof system is for a prover to convince a verifier of the correctness of a claim. However, by contrast, probabilistic proofs allow the verifier to... Show moreIn analogy to mathematical proofs, the goal of a proof system is for a prover to convince a verifier of the correctness of a claim. However, by contrast, probabilistic proofs allow the verifier to make mistakes, i.e., to accept false claims or reject true claims. Further, probabilistic proofs may have multiple rounds of interaction between the prover and the verifier, in which case they are also referred to as interactive proofs. These two relaxations revolutionized the theory of proofs. For instance, by trading absolute certainty for high probability and allowing interaction, it is possible to prove claims without revealing anything beyond their correctness, i.e., in zero-knowledge. Nowadays, zero-knowledge proofs are widely deployed; they are for instance essential in the public-key infrastructures (PKIs) that manage digital identities and secure communication channels on the internet. Especially the theory of Σ-protocols provides a well-understood basis for the modular design of zero-knowledge proof systems in a wide variety of application domains. However, recently a new folding mechanism was introduced as a drop-in replacement for Σ-protocols, significantly reducing the communication costs in many practical scenarios. In this dissertation, we show that the folding mechanism can be cast as a significant strengthening, rather than a replacement, of Σ-protocol theory, thereby reconciling it with the established theory. In addition, we close several gaps in the theory of probabilistic proofs that were exposed due to the introduction of these efficiency improvements. Show less
This dissertation provides a novel perspective on the interaction between quantifier scope and ellipsis. It presents a detailed investigation of the scopal interaction between English negative... Show moreThis dissertation provides a novel perspective on the interaction between quantifier scope and ellipsis. It presents a detailed investigation of the scopal interaction between English negative indefinites, modals, and quantified phrases in ellipsis. One of the crucial observations is that a negative indefinite in object position cannot scope out of a verbal ellipsis site, while Quantifier Raising (QR) of a quantificational object can escape a verbal ellipsis site. This dissertation presents a unified account of this state of affairs in the context of multidominance. It is argued that both English negative indefinites and quantificational determiners decompose into two independent elements. Their formation is the result of a morphological process, Fusion Under Adjacency. The locality/adjacency required for fusion is established under remerge (multidominance), in combination with cyclic Spell-Out/linearization. The main claim of this dissertation is that the PF-process of ellipsis can block this morphological process. It is proposed that the timing of Fusion Under Adjacency and (derivational) ellipsis plays a crucial role: Fusion Under Adjacency has to take place before the ellipsis licensor is merged. The lack of a blocking effect of ellipsis in QR is accounted for by the fact that QR always has a landing site below the ellipsis licensor. In addition to providing an account for the scopal behavior of quantificational elements under ellipsis, this dissertation also sheds new light on the syntax-to-PF mapping. It contributes to our understanding of how multidominant phrase markers are transferred to PF for (non-)pronunciation in a cyclic model of the grammar. This study is of relevance to scholars interested in the nature of ellipsis and quantifier scope, and the syntax-PF connection, as well as to a general syntactic readership. Show less
