Index of Papers by Richard Chang

Papers and publications are indexed by date of conception (most recent first).
Most papers are available on-line in PDF.
For more information, click on the paper titles.

Amplifying ZPPSAT[1] and the Two Queries Problem

Bounded Queries and the NP Machine Hypothesis

One Bit of Advice

Bounded Query Functions with Limited Output Bits

Connecting the Complexities of Approximating Clique and TSP

Bounded Queries, Approximations and the Boolean Hierarchy

Commutative Queries

On Finding the Number of Graph Automorphisms

A Machine Model for the Complexity of NP-approximation Problems

On the Query Complexity of Clique Size and Maximum Satisfiability

On Bounded Queries and Approximation

Relativization: a Revisionistic Retrospective

A Relationship between Difference Hierarchies and Relativized Polynomial Hierarchies

PhD Thesis: On the Structure of NP Computations under Boolean Operators

On Unique Satisfiability and the Threshold Behavior of Randomized Reductions

On Unique Satisfiability and Random Reductions

On Computing Boolean Connectives of Characteristic Functions

On IP = PSPACE and Theorems with Narrow Proofs

The Random Oracle Hypothesis is False

Space Bounded Computations: Review and New Separation Results

An Example of a Theorem that has Contradictory Relativizations and a Diagonalization Proof

The Boolean Hierarchy and the Polynomial Hierarchy: a Closer Connection

On the Structure of Bounded Queries to Arbitrary NP Sets

Some Observations about Relativizations of Space Bounded Computations

Last Modified: 29 Aug 2008 13:44:58 EDT by Richard Chang