On Unique Satisfiability and the Threshold Behavior of Randomized Reductions

• Authors: R. Chang, J. Kadin and P. Rohatgi.
• Cite as: Journal of Computer and System Sciences, 50(3):359-373, June 1995.
• Previous incarnations:
  • R. Chang, J. Kadin and P. Rohatgi. "Connections between the Complexity of Unique Satisfiability and the Threshold Behavior of Randomized Reductions." In Proceedings of the 6th Structure in Complexity Theory Conference, 255-269, July 1991.
  • R. Chang and P. Rohatgi. "Random Reductions in the Boolean Hierarchy are not Robust." Technical Report 90-1154, Department of Computer Science, Cornell University, October 1990.
  • R. Chang and J. Kadin. "On the Structure of Uniquely Satisfiable Formulas." Technical Report 90-1124, Department of Computer Science, Cornell University, May 1990.
• Most readable version: journal version.
• Status: complete.
• Online:
  • Article on Elsevier's Science Direct: DOI 10.1006/jcss.1995.1028.
  • Final journal submission available as a PDF file (with embedded Type 1 fonts): usat.pdf.

Abstract: