Index of Papers by Richard Chang

Amplifying ZPP^SAT[1] and the Two Queries Problem

• Authors: R. Chang and S. Purini
• Reference: In Proceedings of the 23rd Conference on Computational Complexity, 41–52, June 2008.
• In Short: Yes, we can amplify ZPP^SAT[1] and we use this to show that PH collapses to ZPP^SAT[1] if ZPP^SAT[1] = ZPP^SAT[2].

Bounded Queries and the NP Machine Hypothesis

• Authors: R. Chang and S. Purini
• Reference: In Proceedings of the 22nd Conference on Computational Complexity, 52–59, June 2007.
• In Short: What can we prove about the 1 vs 2 queries problem if we assume the NP Machine Hypothesis holds?

One Bit of Advice

• Authors: H. Buhrman, R. Chang and L. Fortnow
• Reference: NEC Research Institute Technical Note #2002-017N. In Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2003), Springer-Verlag Lecture Notes in Computer Science #2607, 547–558, February-March 2003.
• In Short: What if coNP is contained in NP/1 (NP with one bit of advice)?

Bounded Query Functions with Limited Output Bits

• Authors: R. Chang and J. S. Squire
• Reference: In Proceedings of the 16th IEEE Conference on Computational Complexity, 90–98, June 2001.
• In Short: What if bounded query functions were limited to 2 bits of output? Would 3 parallel queries to SAT do more than 2 serial queries?

Connecting the Complexities of Approximating Clique and TSP

• Author: R. Chang
• Reference: unpublished manuscript
• In Short: If MaxClique reduces to 2-approximating MaxClique, then TSP reduces to 2-approximating TSP.

Bounded Queries, Approximations and the Boolean Hierarchy

• Author: R. Chang
• Reference: Information and Computation, 169(2):129–159, September 2001.
• In Short: Connections between the Boolean Hierarchy and the complexity of NP-approximation problems.

Commutative Queries

• Authors: R. Beigel and R. Chang
• Reference: Information and Computation, 166(1):71–91, 2001.
• In Short: The order of queries to two oracles matter when a polynomial time machine is computing a function and querying oracles that are complete for the Polynomial Hierarchy, but the order does not matter when the machine is recognizing a language.

On Finding the Number of Graph Automorphisms

• Authors: R. Chang, W. Gasarch and J. Torán
• Reference: Chicago Journal of Theoretical Computer Science, 1999(1), February 1999.
• In Short: The enumerability of the number of graph automorphisms (#GA) is related to the complexity of the Graph Isomorphism problem (GI). For example, if #GA is polynomially enumerable, then GI can be decided in randomized polynomial time.

A Machine Model for the Complexity of NP-approximation Problems

• Author: R. Chang.
• Reference: In Current Trends in Theoretical Computer Science: Entering the 21st Century, G. Paun, G. Rozenberg and A. Salomaa, editors, pp. 4–24, World Scientific, 2001.
• In Short: A new model that measures the complexity of finding solutions to NP-approximation problems and how the Boolean Hierarchy helps us resolve natural questions about approximating NP-optimization problems.

On the Query Complexity of Clique Size and Maximum Satisfiability

• Author: R. Chang.
• Reference: Journal of Computer and System Sciences, 53(2):298–313, October 1996.
• In Short: comparing the complexity of approximating clique size and maximum satisfiability using bounded queries as a complexity measure.

On Bounded Queries and Approximation

• Authors: R. Chang, W. I. Gasarch and C. Lund.
• Reference: SIAM Journal on Computing, 26(1):188–209, February 1997.
• In Short: examines bounded queries as a complexity measure for NP-approximation problems; obtains upper and lower bounds for Clique Size, Chromatic Number and Set Cover.

Relativization: a Revisionistic Retrospective

• Authors: J. Hartmanis, R. Chang, S. Chari, D. Ranjan and P. Rohatgi.
• Reference: In Current Trends in Theoretical Computer Science, G. Rozenberg and A. Salomaa, editors, pp. 537–547, World Scientific, 1993.
• In Short: a review of the relativization principle and its effect on 15 years of research in complexity theory.

A Relationship between Difference Hierarchies and Relativized Polynomial Hierarchies

• Authors: R. Beigel, R. Chang and M. Ogiwara.
• Reference: Mathematical Systems Theory, 26(3):293–310, July 1993.
• In Short: generalizing theorems about the Boolean hierarchy to the difference hierarchy over counting classes.

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

• Authors: R. Chang
• Reference: PhD Thesis, Cornell University, 1991.
• In Short: an amalgamation of previously published papers.
  • On Computing Boolean Connectives of Characteristic Functions
  • The Boolean Hierarchy and the Polynomial Hierarchy: a Closer Connection
  • On the Structure of Bounded Queries to Arbitrary NP Sets
  • On Unique Satisfiability and the Threshold Behavior of Randomized Reductions

On Unique Satisfiability and the Threshold Behavior of Randomized Reductions

• Authors: R. Chang, J. Kadin and P. Rohatgi.
• Reference: Journal of Computer and System Sciences, 50(3):359–373, June 1995.
• In Short: some new results on unique satsifiability; also, completeness under randomized reductions make sense when probability of success exceeds certain thresholds.

On Unique Satisfiability and Random Reductions

• Authors: R. Chang and P. Rohatgi.
• Reference: In Current Trends in Theoretical Computer Science, G. Rozenberg and A. Salomaa, editors, pp. 494–503, World Scientific, 1993.
• In Short: expository remarks about the meaning of completeness under randomized reductions, especially for unique satisfiability.

On Computing Boolean Connectives of Characteristic Functions

• Authors: R. Chang and J. Kadin.
• Reference: Mathematical Systems Theory, 28(3): 173–198, May/June 1995.
• In Short: using AND and OR to build the Boolean hierarchy.

On IP = PSPACE and Theorems with Narrow Proofs

• Authors: J. Hartmanis, R. Chang, D. Ranjan and P. Rohatgi.
• Reference: In Current Trends in Theoretical Computer Science, G. Rozenberg and A. Salomaa, editors, pp. 484–493, World Scientific, 1993.
• In Short: expository remarks about the relationship between the existence of short proofs and IP = PSPACE.

The Random Oracle Hypothesis is False

• Authors: R. Chang, B. Chor, O. Goldreich, J. Hartmanis, J. Hastad, D. Ranjan and P. Rohatgi.
• Reference: Journal of Computer and System Sciences, 49(1):24–39, August 1994.
• In Short: the IP = PSPACE result relativizes in the wrong direction with probability one; hence, the Random Oracle Hypothesis is debunked.

Space Bounded Computations: Review and New Separation Results

• Authors: D. Ranjan, R. Chang and J. Hartmanis.
• Reference: Theoretical Computer Science, 80(2):289–302, 1991.
• In Short: some results about the constructibility of log log space bounds.

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

• Author: R. Chang.
• Reference: In Bulletin of the European Association for Theoretical Computer Science, 42:172–173, October 1990.
• In Short: some instances of the Gap Theorem do not relativize.

The Boolean Hierarchy and the Polynomial Hierarchy: a Closer Connection

• Authors: R. Chang and J. Kadin.
• Reference: SIAM Journal on Computing, 25(2):340–354, April 1996.
• In Short: a refinement of Kadin's proof that collapsing the Boolean hierarchy also collapses the polynomial hierarchy.

On the Structure of Bounded Queries to Arbitrary NP Sets

• Author: R. Chang.
• Reference: SIAM Journal on Computing, 21(4):743–754, August 1992.
• In Short: sets in NP − low3 can be used to construct bounded query hierarchies with distinct levels.

Some Observations about Relativizations of Space Bounded Computations

• Authors: J. Hartmanis, R. Chang, J. Kadin and S. Mitchell.
• Reference: In Current Trends in Theoretical Computer Science, G. Rozenberg and A. Salomaa, editors, pp. 423–433, World Scientific, 1993.
• In Short: ruminations on deterministic versus nondeterministic space computations and how to relativize log space computations.