Pages that link to "Item:Q3053146"
From MaRDI portal
The following pages link to On the Compressibility of $\mathcal{NP}$ Instances and Cryptographic Applications (Q3053146):
Displayed 24 items.
- On the query complexity of selecting minimal sets for monotone predicates (Q253999) (← links)
- On polynomial kernels for sparse integer linear programs (Q269481) (← links)
- Incompressible functions, relative-error extractors, and the power of nondeterministic reductions (Q301524) (← links)
- AND-compression of NP-complete problems: streamlined proof and minor observations (Q309801) (← links)
- Polynomial kernels for weighted problems (Q340549) (← links)
- Preprocessing subgraph and minor problems: when does a small vertex cover help? (Q386050) (← links)
- Infeasibility of instance compression and succinct PCPs for NP (Q619903) (← links)
- Tree size reduction with keeping distinguishability (Q1630987) (← links)
- A completeness theory for polynomial (Turing) kernelization (Q2343083) (← links)
- FPT is characterized by useful obstruction sets (Q2828222) (← links)
- Kernel Lower Bounds using Co-Nondeterminism: Finding Induced Hereditary Subgraphs (Q2828227) (← links)
- Clique Cover and Graph Separation (Q2943572) (← links)
- Complexity with Rod (Q2970952) (← links)
- Towards Non-Black-Box Separations of Public Key Encryption and One Way Function (Q3181026) (← links)
- New Limits to Classical and Quantum Instance Compression (Q3449566) (← links)
- Lower Bounds for Kernelizations and Other Preprocessing Procedures (Q3576044) (← links)
- Composition Implies Adaptive Security in Minicrypt (Q3593104) (← links)
- Constant-Round Interactive Proofs for Delegating Computation (Q4997311) (← links)
- (Q5075820) (← links)
- (Q5091010) (← links)
- Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses (Q5501928) (← links)
- (Q5743380) (← links)
- (Q5743381) (← links)
- (Q5743382) (← links)