Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 20 of 60 for “"proof systems"”.
-
Studies in Models of Quantum Proof Systems
… we study several problems related to quantum proof systems. The simplest quantum proof system is captured by the complexity class QMA. Interestingly, it is not known whether QMA retains its expressive power if we force it to have perfect completeness. Currently, the strongest result towards …
-
Quantum Information and Variants of Interactive Proof Systems
… nearly three decades, the model of interactive proof systems and its variants have been central to many important and exciting developments in computational complexity theory such as exact characterization of some well known complexity classes, development of probabilistically checkable proof …
-
Approximation, Proof Systems, and Correlations in a Quantum World
… The approximability of quantum problems, quantum proof systems, and non-classical correlations in quantum systems. Our first area of study concerns the approximability of computational problems which are complete for quantum complexity classes. In the classical setting, the study of approximation …
-
Improving the Scalability and Deployability of Cryptographic Proof Systems
… statement via a succinct, efficiently verifiable proof without revealing any additional information about the witness. Despite their powerful capabilities, the practical deployment of zk-SNARKs remains limited to a narrow set of use cases due to high proving and verification costs. In this …
-
Power of Non-uniformity in Proof Complexity
… concerned with the strength of non-uniformity in proof complexity. The non-uniform part is there because we look at quantified propositional proof systems. With these proof systems we are interested in the minimum size of proofs that prove a family of tautologies. Like circuits, these proofs are …
-
QBF Proof Complexity
Quantified Boolean Formulas (QBF) and their proof complexity are not as well understood as propositional formulas, yet remain an area of interest due to their relation to QBF solving. Proof systems for QBF provide a theoretical underpinning for the performance of these solvers. We define a novel …
-
Leveraging Parallelism in Interactive Proofs
Interactive proof systems enable one party (the prover) to convince another (the verifier) of the validity of some computational statement, and ensure that the verifier will be convinced if and only if the statement is true. Since their introduction, interactive proofs have become one of the most …
-
The Proof Complexity of Integer Programming
Proof complexity provides a promising approach aimed at resolving the P versus NP question by establishing the nonexistence of propositional proof systems which admit short proofs of every tautology. Proof complexity suggests an incremental program of proving lower bounds on the size of proofs in …
-
De relações a vizinhanças: um entendimento sobre não-normalidade modal
… with the goal to relate frame semantics with proof systems. Moreover we aim to understand proof systems with semantic language internalized.
-
Correct Programs, Executed Correctly: Verifying Specifications And Executions
… However, as the complexity of computer systems grows, the complexity of their properties does as well. While traditional verification has focused on proving safety, the same techniques do not extend to other properties of interest, such as liveness, correct execution, and cryptographic …
-
Quantified Boolean Formulas: Proof Complexity and Models of Solving
… introducing new lower-bound techniques for QBF proof systems, we study the relative strengths of models of dependency-aware solving, including the proposal of new, stronger models. Proof Complexity: Using the strategy extraction paradigm, we introduce new lower-bound techniques that apply to …
-
Non-Interactive Proofs: What Assumptions Are Sufficient?
A non-Interactive proof system allows a prover to convince a verifier that a statement is true by sending a single round of messages. In this thesis, we study under what assumptions can we build non-interactive proof systems with succinct verification and zero-knowledge. We obtain the following …
-
Linear logic as a logical framework
This thesis investigates the analyticity of proof systems using Linear Logic (LL). Analyticity refers to the property that a proof of a formula F only uses subformulas of F. In sequent calculus, this property is typically established by showing that the cut rule is admissible, meaning that the …
-
Reasons for Hardness in QBF Proof Complexity
… has much wider applications in practice. QBF proof complexity forms the theoretical basis for understanding QBF solving, as well as providing insights into more general complexity theory, but is less well understood than propositional proof complexity. We begin this thesis by looking at the …
-
Proof Complexity for Quantified Boolean Formulas
… problems can be expressed as QBFs. QBF proof complexity is the theoretical analysis of algorithmic techniques for solving QBFs. We make a detailed comparison of the proof systems Q-Res, QU-Res, and ∀Exp + Res which extend propositional Resolution with different rules for reasoning about …
-
TYPES OF ALGEBRAIC STRUCTURES IN PROOF ASSISTANT SYSTEMS
… standard library of mathematical knowledge for a proof system is a complex task that relies on human effort. By conducting a survey on the standard library of four proof systems (Agda, Idris, Lean, and Coq), we define the scope for our research to study types of algebraic structures in proof …
-
IOPs to SNARKs: Security from Practice to Theory
Interactive Oracle Proofs (IOPs) are a powerful proof system model that combines features of probabilistically checkable proofs and interactive proofs. While IOPs have enabled remarkable advances in zero-knowledge proofs, verifiable computation, and other cryptographic applications, their security …
-
Operators of Higher Order
Motivated by results on interactive proof systems we investigate the computational power of quantifiers applied to well-known complexity classes. In special, we are interested in existential, universal and probabilistic bounded error quantifiers ranging over words and sets of words, i.e. oracles if …
Page 1 of 3