On the Compressibility of $\mathcal{NP}$ Instances and Cryptographic Applications
From MaRDI portal
Publication:3053146
DOI10.1137/060668092zbMath1207.68162OpenAlexW2091434162MaRDI QIDQ3053146
Publication date: 4 November 2010
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/060668092
Cryptography (94A60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
On polynomial kernels for sparse integer linear programs ⋮ Tree size reduction with keeping distinguishability ⋮ New Limits to Classical and Quantum Instance Compression ⋮ Incompressible functions, relative-error extractors, and the power of nondeterministic reductions ⋮ AND-compression of NP-complete problems: streamlined proof and minor observations ⋮ Towards Non-Black-Box Separations of Public Key Encryption and One Way Function ⋮ Polynomial kernels for weighted problems ⋮ Clique Cover and Graph Separation ⋮ Preprocessing subgraph and minor problems: when does a small vertex cover help? ⋮ Infeasibility of instance compression and succinct PCPs for NP ⋮ Complexity with Rod ⋮ Lower Bounds for Kernelizations and Other Preprocessing Procedures ⋮ Unnamed Item ⋮ Composition Implies Adaptive Security in Minicrypt ⋮ Unnamed Item ⋮ FPT is characterized by useful obstruction sets ⋮ Kernel Lower Bounds using Co-Nondeterminism: Finding Induced Hereditary Subgraphs ⋮ Constant-Round Interactive Proofs for Delegating Computation ⋮ Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A completeness theory for polynomial (Turing) kernelization ⋮ On the query complexity of selecting minimal sets for monotone predicates
