Infeasibility of instance compression and succinct PCPs for NP
From MaRDI portal
Publication:619903
DOI10.1016/J.JCSS.2010.06.007zbMATH Open1233.68144OpenAlexW1998964055MaRDI QIDQ619903FDOQ619903
Authors: Rahul Santhanam, Lance Fortnow 
Publication date: 18 January 2011
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2010.06.007
Recommendations
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cites Work
- On the compressibility of \(\mathcal{NP}\) instances and cryptographic applications
- Parametrized complexity theory.
- Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
- Proof verification and the hardness of approximation problems
- The probabilistic method. With an appendix on the life and work of Paul Erdős.
- Probabilistic checking of proofs
- The complexity of theorem-proving procedures
- Title not available (Why is that?)
- Constructing locally computable extractors and cryptosystems in the bounded-storage model
- Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
- Title not available (Why is that?)
- Conditionally-perfect secrecy and a provably-secure randomized cipher
- Title not available (Why is that?)
- Advice classes of parametrized tractability
- Some consequences of non-uniform conditions on uniform classes
- On the randomness complexity of efficient sampling
- Simple extractors for all min-entropies and a new pseudorandom generator
- Title not available (Why is that?)
- Title not available (Why is that?)
- Lower bounds for kernelizations and other preprocessing procedures
- Turing machines that take advice
- Title not available (Why is that?)
- The PCP theorem by gap amplification
- On Problems without Polynomial Kernels (Extended Abstract)
- Interactive PCP
- On Everlasting Security in the Hybrid Bounded Storage Model
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (only showing first 100 items - show all)
- Kernel bounds for path and cycle problems
- Parameterized complexity of vertex deletion into perfect graph classes
- Studies in Computational Aspects of Voting
- Fine-grained complexity of safety verification
- Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP
- On polynomial kernels for structural parameterizations of odd cycle transversal
- On the hardness of losing width
- Sparsification upper and lower bounds for graph problems and not-all-equal SAT
- Structural parameterizations of undirected feedback vertex set: FPT algorithms and kernelization
- On polynomial kernels for sparse integer linear programs
- Incremental list coloring of graphs, parameterized by conservation
- Kernelization lower bound for permutation pattern matching
- A basic parameterized complexity primer
- On the kernelization complexity of string problems
- On the approximate compressibility of connected vertex cover
- Polynomial-time compression
- Parameterized computational complexity of finding small-diameter subgraphs
- Kernelization hardness of connectivity problems in \(d\)-degenerate graphs
- On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
- Data-compression for parametrized counting problems on sparse graphs
- FPT and kernelization algorithms for the induced tree problem
- Compression via matroids: a randomized polynomial kernel for odd cycle transversal
- Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs
- On the parameterized complexity of contraction to generalization of trees
- Parameterized complexity dichotomy for \textsc{Steiner Multicut}
- Efficient Probabilistically Checkable Debates
- On the compressibility of \(\mathcal{NP}\) instances and cryptographic applications
- On kernelization for edge dominating set under structural parameters
- On the parameterized complexity of the repetition free longest common subsequence problem
- Incompressible functions, relative-error extractors, and the power of nondeterministic reductions
- Kernel bounds for disjoint cycles and disjoint paths
- Kernelization of cycle packing with relaxed disjointness constraints
- Restricted and swap common superstring: a multivariate algorithmic perspective
- Dual parameterization of weighted coloring
- Dual parameterization of weighted coloring
- Monotonic reductions, representative equivalence, and compilation of intractable problems
- Incompressibility of \(H\)-free edge modification problems
- Algorithms and kernels for \textsc{Feedback Set} problems in generalizations of tournaments
- Kernel lower bounds using co-nondeterminism: finding induced hereditary subgraphs
- Two edge modification problems without polynomial kernels
- Data reduction for graph coloring problems
- Building large \(k\)-cores from sparse graphs
- Title not available (Why is that?)
- Confronting intractability via parameters
- Vertex cover structural parameterization revisited
- Meta-kernelization with structural parameters
- The kernelization complexity of connected domination in graphs with (no) small cycles
- Preprocessing subgraph and minor problems: when does a small vertex cover help?
- Kernel bounds for path and cycle problems
- New limits to classical and quantum instance compression
- Finding two edge-disjoint paths with length constraints
- On cutwidth parameterized by vertex cover
- Multivariate complexity analysis of geometric \textsc{Red Blue Set Cover}
- Co-nondeterminism in compositions: a kernelization lower bound for a Ramsey-type problem
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- Backdoors to tractable answer set programming
- A completeness theory for polynomial (Turing) kernelization
- On the parameterized complexity of finding separators with non-hereditary properties
- Fractals for kernelization lower bounds
- Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
- Introducing \textsf{lop}-kernels: a framework for kernelization lower bounds
- Fixed-parameter algorithms for DAG partitioning
- Kernels for packing and covering problems
- On the Complexity of Bounded Context Switching.
- Clique Cover and Graph Separation
- Finding cuts of bounded degree: complexity, FPT and exact algorithms, and kernelization
- Partially polynomial kernels for set cover and test cover
- On making a distinguished vertex of minimum degree by vertex deletion
- A multistage view on 2-satisfiability
- Two edge-disjoint paths with length constraints
- Instance compression for the polynomial hierarchy and beyond
- Some remarks on the incompressibility of width-parameterized SAT instances
- Approximate Turing Kernelization for Problems Parameterized by Treewidth
- A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F} \)-minor-free deletion
- Tractability, hardness, and kernelization lower bound for and/or graph solution
- Preprocessing to reduce the search space: antler structures for feedback vertex set
- Polynomial Kernels for Hitting Forbidden Minors under Structural Parameterizations.
- Title not available (Why is that?)
- Minimum separator reconfiguration
- A deterministic polynomial kernel for odd cycle transversal and vertex multiway cut in planar graphs
- On the parametrized complexity of read-once refutations in UTVPI+ constraint systems
- Complexity with Rod
- Twin-width. III: Max independent set, min dominating set, and coloring
- How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
- A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs
- Multistage \(s-t\) path: confronting similarity with dissimilarity
- Algorithms, Complexity, and Hans
- Crossing Paths with Hans Bodlaender: A Personal View on Cross-Composition for Sparsification Lower Bounds
- Hans Bodlaender and the Theory of Kernelization Lower Bounds
- Preprocessing to reduce the search space: antler structures for feedback vertex set
- Polynomial Kernel for Interval Vertex Deletion
- FPT is characterized by useful obstruction sets: connecting algorithms, kernels, and quasi-orders
- Lossy planarization: a constant-factor approximate kernelization for planar vertex deletion
- Indistinguishability obfuscation, range avoidance, and bounded arithmetic
- On some FPT problems without polynomial Turing compressions
- Zero-knowledge IOPs approaching witness length
- Succinct Permanent Is NEXP-Hard with Many Hard Instances
- Succinct interactive oracle proofs: applications and limitations
- A polynomial kernel for bipartite permutation vertex deletion
- Polynomial kernels for hitting forbidden minors under structural parameterizations
This page was built for publication: Infeasibility of instance compression and succinct PCPs for NP
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q619903)
