A PCP characterization of NP with optimal amortized query complexity

Abstract

Article A PCP characterization of NP with optimal amortized query complexity Share on Authors: Alex Samorodnitsky Institute for Advanced Study and DIMACS Institute for Advanced Study and DIMACSView Profile , Luca Trevisan Columbia University and DIMACS Columbia University and DIMACSView Profile Authors Info & Claims STOC '00: Proceedings of the thirty-second annual ACM symposium on Theory of computingMay 2000 Pages 191–199https://doi.org/10.1145/335305.335329Online:01 May 2000Publication History 101citation487DownloadsMetricsTotal Citations101Total Downloads487Last 12 Months17Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access