Most papers are available on-line in PDF.

For more information, click on the paper titles.

- 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]}.

- 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?

- 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)?

- 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?

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

- 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.

- 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.

- 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.

- 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.

- 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.

- 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.

- 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.

- 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.

- Authors: R. Chang
- Reference: PhD Thesis, Cornell University, 1991.
- In Short: an amalgamation of previously published papers.

- 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.

- 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.

- 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.

- 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.

- 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.

- 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.

- 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.

- 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.

- 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.

- 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.

Last Modified: 22 Jul 2024 11:27:53 EDT by Richard Chang