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 30 for “"interactive proof"”.
-
Quantum Information and Variants of Interactive Proof Systems
For 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 …
-
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 …
-
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 …
-
Formal verification of control software
… level. Libraries of theorems, along with their proofs, are developed to enable an interactive proof assistant to verify control-related properties. Through integration in a prototype tool, the process of verification is made automatic, and applied to several example systems.In a context of …
-
Tactics From Proofs
Proof guarantees the correctness of a formal specification with respect to formal requirements, and of an implementation with respect to a specification, and so provides valuable verification methods in high integrity system development. However, proof development by hand tends to be an erudite, …
-
Forward with separation logic
… it to a case study: the system initialiser proof for the microkernel seL4. We discovered separating coimplication, which, as the dual of separating conjunction and the adjoint of septraction, completes the set of separation logic operators. We demonstrate that it can be used for forward …
-
Equational Reasoning about Object-Oriented Programs
… formally. The latter is the basis of the interactive proof assistant VOOP (Verified Object-Oriented Programs) that allows the user to prove equational properties of programs interactively.
-
Concentration Bounds from Parallel Repetition Theorems
… bounds for nonlocal games and quantum interactive proofs. We make the following contributions: - A lemma that is useful for converting parallel repetition theorems (bounds on the probability of winning all instances of a nonlocal game which is being repeated in parallel) into …
-
Computational Distinguishability of Quantum Channels
… for the class QIP of problems that have quantum interactive proof systems, which implies that it is hard for the class PSPACE of problems solvable by a classical computation in polynomial space. Several restrictions of distinguishability are also shown to be hard. It is no easier when restricted …
-
Continuous-Variable Ramp Quantum Secret Sharing with Gaussian States and Operations
… schemes in the framework of quantum interactive-proof systems. We devise pseudocodes in order to represent the sequence of steps taken to solve the certification problem. Furthermore, we derive the expression for quantum mutual information between the quantum secret extracted by any …
-
An Implementation of Separation Logic in Coq
… an implementation of separation logic in the interactive proof system Coq. Besides verifying that separation logic is correct, we will provide several examples of programs and their correctness proof.
-
Design of a Competency Administration Toolset (CAT)
… The products of this analysis included an interactive proof-of-concept graphical user interface (GUI) and multiple systems engineering artifacts, including user stories, use cases, requirements documentation, and a functional architecture. The project's stakeholders approved the final …
-
Dependently Sorted Theorem Proving for Mathematical Foundations
… convenient automatic rewriting, and interactive proof support. By formalizing the proof theory of the DiaToM logic, we verified that the most suspicious design, namely the "formula variable", does not break the first-orderness of our logic. We assess our implementation by axiomatizing …
-
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 …
-
Using Spammers' Computing Resources for Volunteer Computing
… users to contribute solutions to useful problems interactively, an analogous solution for non-interactive proof-of-work does not exist. Towards this end, this paper describes MetaCAPTCHA and reBOINC, an infrastructure for supporting useful proof-of-work that is integrated into a web spam …
-
Quantum Games, Graphs, and Gödel
… computational complexity, and multiprover interactive proof systems. Specifically, we examine the connections between quantum graph properties, computability theory, and entangled nonlocal games.Building on prior work that defined quantum variants of graph homomorphisms, isomorphism, and …
-
Time and space efficiency of codes and proofs
… space are fundamental measures of complexity. Interactive proofs, PCPs, and error correcting codes are important tools. Error correcting codes have applications from transmitting data through unreliable channels to hardness amplification. Interactive proofs and PCPs have applications from …
-
Formalization of Partial Differential Equations using HOL Theorem Proving
… has been performed using paper-and-pencil based proofs or computer-based numerical methods. However, these analysis techniques compromise the soundness and accuracy of their results, especially in safety-critical systems, due to the risk of human errors and inherent incompleteness of numerical …
-
A model checker for statecharts (linking case tools with formal methods)
… by embedding them in the logical framework of an interactive proof-assistant system called HOL. A software interface is provided to extract a statechart directly from the STATEMATE database. Using HOL in combination with Voss, a binary decision diagram-based verification tool, we have developed a …
Page 1 of 2