On the compressibility of NP instances and cryptographic applications

DOI10.1137/060668092MaRDI QIDQ3053146zbMATH OpenOpenAlexFDO

Authors D. Harnik, Moni Naor

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

zbMATH Keywords

bounded storage modelcollision resistant hashcompressioncryptographyNP problemswitness length

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Cryptography (94A60)

Recommendations

• New limits to classical and quantum instance compression
• Infeasibility of instance compression and succinct PCPs for NP
• Instance compression for the polynomial hierarchy and beyond
• Polynomial-time compression
• On the complexity of compressing obfuscation

Cited in

(29)

• Polynomial-time compression
• Tree size reduction with keeping distinguishability
• A completeness theory for polynomial (Turing) kernelization
• On the query complexity of selecting minimal sets for monotone predicates
• On polynomial kernels for sparse integer linear programs
• FPT is characterized by useful obstruction sets: connecting algorithms, kernels, and quasi-orders
• Kernel lower bounds using co-nondeterminism: finding induced hereditary subgraphs
• Clique Cover and Graph Separation
• Complexity with Rod
• Incompressible functions, relative-error extractors, and the power of nondeterministic reductions
• 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
• Preprocessing subgraph and minor problems: when does a small vertex cover help?
• Instance compression for the polynomial hierarchy and beyond
• Constant-round interactive proofs for delegating computation
• Equal-subset-sum faster than the meet-in-the-middle
• Data-compression for parametrized counting problems on sparse graphs
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• Compression via matroids: a randomized polynomial kernel for odd cycle transversal
• scientific article; zbMATH DE number 7053262 (Why is no real title available?)
• Co-nondeterminism in compositions: a kernelization lower bound for a Ramsey-type problem
• Infeasibility of instance compression and succinct PCPs for NP
• Probabilistically checkable arguments for all NP
• Instance compression, revisited
• Incompressible encryption with everlasting security
• Parameterized algorithms on integer sets with small doubling: integer programming, subset sum and k-SUM
• Does subset sum admit short proofs?

This page was built for publication: On the compressibility of \(\mathcal{NP}\) instances and cryptographic applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3053146)