Complexity with Rod

DOI10.1007/978-3-319-50062-1_8zbMath1360.68508OpenAlexW2559051017MaRDI QIDQ2970952

Lance J. Fortnow

Publication date: 4 April 2017

Published in: Computability and Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-50062-1_8

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Biographies, obituaries, personalia, bibliographies (01A70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Unnamed Item
• Infeasibility of instance compression and succinct PCPs for NP
• On problems without polynomial kernels
• Uniformly hard languages.
• Robust simulations and significant separations
• On the Compressibility of $\mathcal{NP}$ Instances and Cryptographic Applications
• Algorithmic Randomness and Complexity
• New Limits to Classical and Quantum Instance Compression
• On the Structure of Polynomial Time Reducibility
• New non-uniform lower bounds for uniform classes
• Recursively enumerable sets of positive integers and their decision problems

This page was built for publication: Complexity with Rod