Infeasibility of instance compression and succinct PCPs for NP
Article Properties
-
LanguageEnglish
-
DOI (url)
-
Publication Date2011/01/01
-
Indian UGC (journal)
-
Refrences33
-
Citations84
-
Lance Fortnow
-
Rahul Santhanam
Cite
Fortnow, Lance, and Rahul Santhanam. “Infeasibility of Instance Compression and Succinct PCPs for NP”. Journal of Computer and System Sciences, vol. 77, no. 1, 2011, pp. 91-106, https://doi.org/10.1016/j.jcss.2010.06.007.
Fortnow, L., & Santhanam, R. (2011). Infeasibility of instance compression and succinct PCPs for NP. Journal of Computer and System Sciences, 77(1), 91-106. https://doi.org/10.1016/j.jcss.2010.06.007
Fortnow, Lance, and Rahul Santhanam. “Infeasibility of Instance Compression and Succinct PCPs for NP”. Journal of Computer and System Sciences 77, no. 1 (2011): 91-106. https://doi.org/10.1016/j.jcss.2010.06.007.
Fortnow L, Santhanam R. Infeasibility of instance compression and succinct PCPs for NP. Journal of Computer and System Sciences. 2011;77(1):91-106.
Journal Categories
Science
Mathematics
Instruments and machines
Electronic computers
Computer science
Science
Mathematics
Instruments and machines
Electronic computers
Computer science
Computer software
Technology
Electrical engineering
Electronics
Nuclear engineering
Electronics
Computer engineering
Computer hardware
Refrences
| Title | Journal | Journal Categories | Citations | Publication Date |
|---|---|---|---|---|
Invitation to data reduction and problem kernelization | ACM SIGACT News | 133 | 2007 | |
| Constructing Locally Computable Extractors and Cryptosystems in the Bounded-Storage Model | Journal of Cryptology |
| 30 | 2004 |
| Graph nonisomorphism has subexponential size proofs unless the polynomial hierarchy collapses | SIAM Journal on Computing |
| 2002 | |
Probabilistic checking of proofs | Journal of the ACM |
| 243 | 1998 |
Proof verification and the hardness of approximation problems | Journal of the ACM |
| 396 | 1998 |
Citations
| Title | Journal | Journal Categories | Citations | Publication Date |
|---|---|---|---|---|
| Preprocessing to reduce the search space: Antler structures for feedback vertex set | Journal of Computer and System Sciences |
| 2024 | |
Local Proofs Approaching the Witness Length | Journal of the ACM |
| 2024 | |
Multistage s–t Path: Confronting Similarity with Dissimilarity | Algorithmica |
| 2023 | |
| Building large k-cores from sparse graphs | Journal of Computer and System Sciences |
| 2023 | |
Polynomial Kernel for Interval Vertex Deletion | ACM Transactions on Algorithms |
| 2023 |
Citations Analysis
The category
Science: Mathematics: Instruments and machines: Electronic computers. Computer science: Computer software 61
is the most commonly referenced area in studies that cite this article. The first research to cite this article was titled Confronting intractability via parameters and was published in 2011. The most recent citation comes from a 2024 study titled Local Proofs Approaching the Witness Length. This article reached its peak citation in 2014, with 12 citations. It has been cited in 19 different journals. Among related journals, the Algorithmica cited this research the most, with 23 citations. The chart below illustrates the annual citation trends for this article.