On the Compressibility of $\mathcal{NP}$ Instances and Cryptographic Applications
From MaRDI portal
Publication:3053146
DOI10.1137/060668092zbMath1207.68162MaRDI 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; compression; NP problems; bounded storage model; witness length; collision resistant hash
94A60: Cryptography
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses, Unnamed Item, Unnamed Item, Unnamed Item, On the query complexity of selecting minimal sets for monotone predicates, On polynomial kernels for sparse integer linear programs, Incompressible functions, relative-error extractors, and the power of nondeterministic reductions, AND-compression of NP-complete problems: streamlined proof and minor observations, Polynomial kernels for weighted problems, Preprocessing subgraph and minor problems: when does a small vertex cover help?, Infeasibility of instance compression and succinct PCPs for NP, Tree size reduction with keeping distinguishability, A completeness theory for polynomial (Turing) kernelization, FPT is characterized by useful obstruction sets, Kernel Lower Bounds using Co-Nondeterminism: Finding Induced Hereditary Subgraphs, Clique Cover and Graph Separation, Complexity with Rod, Towards Non-Black-Box Separations of Public Key Encryption and One Way Function, New Limits to Classical and Quantum Instance Compression, Lower Bounds for Kernelizations and Other Preprocessing Procedures, Composition Implies Adaptive Security in Minicrypt
