Type-omega DPLs (Denotational Proof Languages) are languages for proof presentation and search that offer strong soundness guarantees. LCF-type systems such as HOL offer similar guarantees, but their soundness relies heavily on static type systems. By contrast, DPLs ensure soundness dynamically, through their evaluation semantics; no type system is necessary. This is possible owing to a novel two-tier syntax that separates deductions from computations, and to the abstraction of assumption bases, which is factored into the semantics of the language and allows for sound evaluation. Every type-omega DPL properly contains a type-alpha DPL, which can be used to present proofs in a lucid and detailed form, exclusively in terms of primitive inference rules. Derived inference rules are expressed as user-defined methods, which are "proof recipes" that take arguments and dynamically perform appropriate deductions. Methods arise naturally via parametric abstraction over type-alpha proofs. In that light, the evaluation of a method call can be viewed as a computation that carries out a type-alpha deduction. The type-alpha proof "unwound" by such a method call is called the "certificate" of the call. Certificates can be checked by exceptionally simple type-alpha interpreters, and thus they are useful whenever we wish to minimize our trusted base. Methods are statically closed over lexical environments, but dynamically scoped over assumption bases. They can take other methods as arguments, they can iterate, and they can branch conditionally. These capabilities, in tandem with the bifurcated syntax of type-omega DPLs and their dynamic assumption-base semantics, allow the user to define methods in a style that is disciplined enough to ensure soundness yet fluid enough to permit succinct and perspicuous expression of arbitrarily sophisticated derived inference rules. We demonstrate every major feature of type-omega DPLs by defining and studying NDL-omega, a higher-order, lexically scoped, call-by-value type-omega DPL for classical zero-order natural deduction---a simple choice that allows us to focus on type-omega syntax and semantics rather than on the subtleties of the underlying logic. We start by illustrating how type-alpha DPLs naturally lead to type-omega DPLs by way of abstraction; present the formal syntax and semantics of NDL-omega; prove several results about it, including soundness; give numerous examples of methods; point out connections to the lambda-phi calculus, a very general framework for type-omega DPLs; introduce a notion of computational and deductive cost; define several instrumented interpreters for computing such costs and for generating certificates; explore the use of type-omega DPLs as general programming languages; show that DPLs do not have to be type-less by formulating a static Hindley-Milner polymorphic type system for NDL-omega; discuss some idiosyncrasies of type-omega DPLs such as the potential divergence of proof checking; and compare type-omega DPLs to other approaches to proof presentation and discovery. Finally, a complete implementation of NDL-omega in SML-NJ is given for users who want to run the examples and experiment with the language.

Currently, the most effective complete SAT solvers are based on the DPLL algorithm augmented by Clause Learning. These solvers can handle many real-world problems from application areas like verification, diagnosis, planning, and design. Clause Learning works by storing previously computed, intermediate results and then reusing them to prune the future search tree. Without Clause Learning, however, DPLL loses most of its effectiveness on real world problems. Recently there has been some work on obtaining a deeper understanding of the technique of Clause Learning. In this thesis, we contribute to the understanding of Clause Learning, and the Resolution proof system that underlies it, in a number of ways. We characterize Clause Learning as a new, intuitive Resolution refinement which we call CL. We then show that CL proofs can effectively p-simulate general Resolution. Furthermore, this result holds even for the more restrictive class of greedy, unit propagating CL proofs, which more accurately characterize Clause Learning as it is used in practice. This result is surprising and indicates that Clause Learning is significantly more powerful than was previously known. Since Clause Learning makes use of previously derived clauses, it motivates the study of Resolution space. We contribute to this area of study by proving that determining the variable space of a Resolution derivation is PSPACE-complete. The reduction also yields a surprising exponential size/space trade-off for Resolution in which an increase of just 3 units of variable space results in an exponential decrease in proofsize. This result runs counter to the intuitions of many in the SAT-solving community who have generally believed that proof-size should decrease smoothly as available space increases. In order to prove these Resolution results, we need to make use of some intuition regarding the relationship between Black-White Pebbling and Resolution. In fact, determining the complexity of Resolution variable space required us to first prove that Black-White Pebbling is PSPACE-complete. The complexity of the Black-White Pebbling Game has remained an open problem for 30 years and resisted numerous attempts to solve it. Its solution is the primary contribution of this thesis.

Currently, the most effective complete SAT solvers are based on the DPLL algorithm augmented by Clause Learning. These solvers can handle many real-world problems from application areas like verification, diagnosis, planning, and design. Clause Learning works by storing previously computed, intermediate results and then reusing them to prune the future search tree. Without Clause Learning, however, DPLL loses most of its effectiveness on real world problems. Recently there has been some work on obtaining a deeper understanding of the technique of Clause Learning. In this thesis, we contribute to the understanding of Clause Learning, and the Resolution proof system that underlies it, in a number of ways. We characterize Clause Learning as a new, intuitive Resolution refinement which we call CL. We then show that CL proofs can effectively p-simulate general Resolution. Furthermore, this result holds even for the more restrictive class of greedy, unit propagating CL proofs, which more accurately characterize Clause Learning as it is used in practice. This result is surprising and indicates that Clause Learning is significantly more powerful than was previously known. Since Clause Learning makes use of previously derived clauses, it motivates the study of Resolution space. We contribute to this area of study by proving that determining the variable space of a Resolution derivation is PSPACE-complete. The reduction also yields a surprising exponential size/space trade-off for Resolution in which an increase of just 3 units of variable space results in an exponential decrease in proofsize. This result runs counter to the intuitions of many in the SAT-solving community who have generally believed that proof-size should decrease smoothly as available space increases. In order to prove these Resolution results, we need to make use of some intuition regarding the relationship between Black-White Pebbling and Resolution. In fact, determining the complexity of Resolution variable space required us to first prove that Black-White Pebbling is PSPACE-complete. The complexity of the Black-White Pebbling Game has remained an open problem for 30 years and resisted numerous attempts to solve it. Its solution is the primary contribution of this thesis.

This thesis studies three topics in quantum computation and information: 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 algorithms and hardness of approximation is one of the main research areas of theoretical computer science. Yet, little is known regarding approximability in the quantum setting. We first demonstrate a polynomial-time approximation algorithm for dense instances of the canonical QMA-complete quantum constraint satisfaction problem, the local Hamiltonian problem. We next go in the opposite direction by first introducing a quantum generalization of the polynomial-time hierarchy. We then introduce problems which are not only complete for the second level of this hierarchy, but are in fact hard to approximate. Our second area of study concerns quantum proof systems. Here, an interesting question which remains open despite much effort is whether a proof system with multiple unentangled quantum provers is equal in expressive power to a proof system with a single quantum prover (i.e. is QMA(poly) equal to QMA?). Our results here study variants of this question, and include a proof that the class BellQMA(poly) collapses to QMA. We also give an alternate proof that SepQMA(m) admits perfect parallel repetition. This proof is novel in that it utilizes cone programming duality. Our final area of study concerns non-classical correlations in quantum systems. Specifically, there exist genuinely quantum correlations beyond entanglement in mixed quantum states which may prove useful from a computing and information theoretic perspective. We first explore the presence of such correlations in the locking of classical correlations and the DQC1 model of mixed-state quantum computing. Our second result introduces a novel scheme for quantifying non-classical correlations using local unitary operations. Our third result introduces a protocol through which non-classical correlations in a starting system can be “activated”' into distillable entanglement with an ancilla system. Our last result determines when the entanglement generated in the activation protocol above can be mapped back onto the starting state via entanglement swapping.

Thesis (M. Ed.)--University of Hong Kong, 2001. / Includes bibliographical references (leaves 88-91).

No description available.

If the number of individuals is odd, Campbell and Kelly (2003) show that majority rule is the only non-dictatorial strategy-proof social choice rule on the domain of linear orders that admit a Condorcet winner, an alternative that is preferred to every other by a majority of individuals in pairwise majority voting. This paper shows that the claim is false when the number of individuals is even, and provides a characterization of non-dictatorial strategy-proof social choice rules on this domain. Two examples illustrate the primary reason that the result does not translate to the even case: when the number of individuals is even, no single individual can change her reported preference ordering in a manner that changes the Condorcet winner while remaining within the preference domain. Introducing two new definitions to account for this partitioning of the preference domain, the chapter concludes with a counterpart to the characterization of Campbell and Kelly (2003) for the even case. Adapting the models of Laibson (1994) and O’Donogue and Rabin (2001), a learning–naıve agent is presented who is endowed with beliefs about the value of the quasi–hyperbolic discount factor that enters into the utility calculations of her future–selves. Facing an infinite–horizon decision problem in which the payoff to a particular action varies stochastically, the agent updates her beliefs over time. Conditions are given under which the behavior of a learning–na¨ıve agent is eventually indistinguishable from that of a sophisticated agent, contributing to the efforts of Ali (2011) to justify the use of sophistication as a modeling assumption. Building upon the literature on one–to–one matching pioneered by Gale and Shapley (1962), this paper introduces a social network to the standard marriage model, embodying informational limitations of the agents. Motivated by the restrictive nature of stability in large markets, two new network–stability concepts are introduced that reflect informational limitations; in particular, two agents cannot form a blocking pair if they are not acquainted. Following Roth and Sotomayor (1990), key properties of the sets of network–stable matchings are derived, and concludes by introducing a network–formation game whose set of complete–information Nash equilibria correspond to the set of stable matchings / Economics

This thesis studies three topics in quantum computation and information: 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 algorithms and hardness of approximation is one of the main research areas of theoretical computer science. Yet, little is known regarding approximability in the quantum setting. We first demonstrate a polynomial-time approximation algorithm for dense instances of the canonical QMA-complete quantum constraint satisfaction problem, the local Hamiltonian problem. We next go in the opposite direction by first introducing a quantum generalization of the polynomial-time hierarchy. We then introduce problems which are not only complete for the second level of this hierarchy, but are in fact hard to approximate. Our second area of study concerns quantum proof systems. Here, an interesting question which remains open despite much effort is whether a proof system with multiple unentangled quantum provers is equal in expressive power to a proof system with a single quantum prover (i.e. is QMA(poly) equal to QMA?). Our results here study variants of this question, and include a proof that the class BellQMA(poly) collapses to QMA. We also give an alternate proof that SepQMA(m) admits perfect parallel repetition. This proof is novel in that it utilizes cone programming duality. Our final area of study concerns non-classical correlations in quantum systems. Specifically, there exist genuinely quantum correlations beyond entanglement in mixed quantum states which may prove useful from a computing and information theoretic perspective. We first explore the presence of such correlations in the locking of classical correlations and the DQC1 model of mixed-state quantum computing. Our second result introduces a novel scheme for quantifying non-classical correlations using local unitary operations. Our third result introduces a protocol through which non-classical correlations in a starting system can be “activated”' into distillable entanglement with an ancilla system. Our last result determines when the entanglement generated in the activation protocol above can be mapped back onto the starting state via entanglement swapping.

Thesis (Ph. D.)--University of Texas at Austin, 2008. / Vita. Includes bibliographical references.

Univ., Diss.--Freiburg, 2002. / Literaturverz. S. [243] - 247.