Richard Chang

According to our database, Richard Chang authored at least 32 papers between 1990 and 2020.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2020

Formal Methods Analysis of the Secure Remote Password Protocol.

Alan T. Sherman, Erin Lanus, Moses Liskov, Edward Zieglar, Richard Chang, Enis Golaszewski, Ryan Wnuk-Fink, Cyrus J. Bonyadi, Mario Yaksetig, Ian Blumenfeld

Proceedings of the Logic, 2020

2008

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

Richard Chang, Suresh Purini

Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, 2008

2007

Bounded Queries and the NP Machine Hypothesis.

Richard Chang, Suresh Purini

Proceedings of the 22nd Annual IEEE Conference on Computational Complexity (CCC 2007), 2007

2003

One Bit of Advice.

Harry Buhrman, Richard Chang, Lance Fortnow

Proceedings of the STACS 2003, 20th Annual Symposium on Theoretical Aspects of Computer Science, Berlin, Germany, February 27, 2003

2001

Commutative Queries.

Richard Beigel, Richard Chang

Inf. Comput., 2001

Bounded Query Functions with Limited Output Bits.

Richard Chang, Jon S. Squire

Proceedings of the 16th Annual IEEE Conference on Computational Complexity, 2001

A Machine Model for the Complexity of NP-Approximation Problems.

Richard Chang

Proceedings of the Current Trends in Theoretical Computer Science, 2001

1999

On Finding the Number of Graph Automorphisms.

Robert Beals, Richard Chang, William I. Gasarch, Jacobo Torán

Chic. J. Theor. Comput. Sci., 1999

1997

On Bounded Queries and Approximation.

Richard Chang, William I. Gasarch, Carsten Lund

SIAM J. Comput., 1997

Bounded Queries, Approximations and the Boolean Hierarchy

Richard Chang

Electron. Colloquium Comput. Complex., 1997

1996

The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection.

Richard Chang, Jim Kadin

SIAM J. Comput., 1996

On the Query Complexity of Clique Size and Maximum Satisfiability.

Richard Chang

J. Comput. Syst. Sci., 1996

1995

On Computing Boolean Connectives of Characteristic Functions.

Richard Chang, Jim Kadin

Math. Syst. Theory, 1995

On Unique Satisfiability and the Threshold Behavior of Randomized Reductions.

Richard Chang, Jim Kadin, Pankaj Rohatgi

J. Comput. Syst. Sci., 1995

On Finding the Number of Graph Automorphisms.

Richard Chang, William I. Gasarch, Jacobo Torán

Proceedings of the Tenth Annual Structure in Complexity Theory Conference, 1995

1994

The Random Oracle Hypothesis Is False.

Richard Chang, Benny Chor, Oded Goldreich, Juris Hartmanis, Johan Håstad, Desh Ranjan, Pankaj Rohatgi

J. Comput. Syst. Sci., 1994

A Machine Model for NP-Approximation Problems and the Revenge of the Boolean Hierarchy.

Richard Chang

Bull. EATCS, 1994

1993

On IP = PSPACE and Theorems with Narrow Proofs.

Juris Hartmanis, Richard Chang, Desh Ranjan, Pankaj Rohatgi

Proceedings of the Current Trends in Theoretical Computer Science - Essays and Tutorials, 1993

Some Observations about Relativization of Space Bounded Computations.

Juris Hartmanis, Richard Chang, Jim Kadin, Stephen G. Mitchell

Proceedings of the Current Trends in Theoretical Computer Science - Essays and Tutorials, 1993

Relativization: a Revisionistic Retrospective.

Juris Hartmanis, Richard Chang, Suresh Chari, Desh Ranjan, Pankaj Rohatgi

Proceedings of the Current Trends in Theoretical Computer Science - Essays and Tutorials, 1993

On Unique Satisfiability and Randomized Reductions.

Richard Chang, Pankaj Rohatgi

Proceedings of the Current Trends in Theoretical Computer Science - Essays and Tutorials, 1993

A Relationship Between Difference Hierarchies and Relativized Polynomial Hierarchies.

Richard Beigel, Richard Chang, Mitsunori Ogiwara

Math. Syst. Theory, 1993

On Bounded Queries and Approximation

Richard Chang, William I. Gasarch

Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

1992

On the Structure of Bounded Queries to Arbitrary NP Sets.

Richard Chang

SIAM J. Comput., 1992

Relativization: a revisionistic retrospective.

Richard Chang, Suresh Chari, Desh Ranjan, Pankaj Rohatgi

Bull. EATCS, 1992

1991

On the Structure of NP Computations under Boolean Operators.

Richard Chang

PhD thesis, 1991

Space Bounded Computations: Review and New Separation Results.

Desh Ranjan, Richard Chang, Juris Hartmanis

Theor. Comput. Sci., 1991

Connections between the Complexity of Unique Satisfiability and the Threshold Behavior of Randomized Reductions.

Richard Chang, Jim Kadin, Pankaj Rohatgi

Proceedings of the Sixth Annual Structure in Complexity Theory Conference, Chicago, Illinois, USA, June 30, 1991

1990

On Unique Staisfiability and Randomized Reductions.

Juris Hartmanis, Richard Chang, Desh Ranjan, Pankaj Rohatgi

Bull. EATCS, 1990

On Unique Staisfiability and Randomized Reductions.

Richard Chang, Pankaj Rohatgi

Bull. EATCS, 1990

An Example of a Theorem that has Contradictory Relativization and Diagonalization Proof.

Richard Chang

Bull. EATCS, 1990

Structural Complexity Theory: recent Surprises.

Juris Hartmanis, Richard Chang, Desh Ranjan, Pankaj Rohatgi

Proceedings of the SWAT 90, 1990