New Limits to Classical and Quantum Instance Compression
From MaRDI portal
Publication:3449566
DOI10.1137/130927115zbMath1330.68092OpenAlexW2255673366MaRDI QIDQ3449566
Publication date: 4 November 2015
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/56acde9ceb7bee02f8e1777fe92dd6e397eeba41
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Quantum algorithms and complexity in the theory of computing (68Q12)
Related Items
Hans Bodlaender and the Theory of Kernelization Lower Bounds, Parameterized complexity dichotomy for \textsc{Steiner Multicut}, Multistage vertex cover, Kernelization of Cycle Packing with Relaxed Disjointness Constraints, AND-compression of NP-complete problems: streamlined proof and minor observations, Fixed-Parameter Tractability of Treewidth and Pathwidth, Known Algorithms for Edge Clique Cover are Probably Optimal, Preprocessing to reduce the search space: antler structures for feedback vertex set, Parameterized complexity of \textsc{bandwidth} of \textsc{caterpillars} and \textsc{weighted path emulation}, Polynomial Kernel for Interval Vertex Deletion, Multistage \(s-t\) path: confronting similarity with dissimilarity, On the (Parameterized) Complexity of Recognizing Well-Covered $$(r,\ell )$$ -graphs, Polynomial kernels for hitting forbidden minors under structural parameterizations, Complexity with Rod, Fractals for Kernelization Lower Bounds, On cutwidth parameterized by vertex cover, Generalized Quantum Arthur--Merlin Games, Parameterized complexity of critical node cuts, A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs, Tight Upper and Lower Bounds for Leakage-Resilient, Locally Decodable and Updatable Non-malleable Codes, On the approximate compressibility of connected vertex cover, Unnamed Item, Tight upper and lower bounds for leakage-resilient, locally decodable and updatable non-malleable codes, Unnamed Item, On parameterized algorithms for fixed-order book thickness with respect to the pathwidth of the vertex ordering, On fixed-order book thickness parameterized by the pathwidth of the vertex ordering, Public-coin statistical zero-knowledge batch verification against malicious verifiers, A deterministic polynomial kernel for odd cycle transversal and vertex multiway cut in planar graphs, On some FPT problems without polynomial Turing compressions, Constant-Round Interactive Proofs for Delegating Computation, Best-case and worst-case sparsifiability of Boolean CSPs, A polynomial kernel for bipartite permutation vertex deletion
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- AND-compression of NP-complete problems: streamlined proof and minor observations
- Entropy-based bounds on dimension reduction in \(L^1\)
- Fundamentals of parameterized complexity
- Lower bounds for kernelizations and other preprocessing procedures
- Infeasibility of instance compression and succinct PCPs for NP
- Kernel bounds for disjoint cycles and disjoint paths
- Advice classes of parametrized tractability
- Some consequences of non-uniform conditions on uniform classes
- Statistical zero-knowledge languages can be recognized in two rounds
- On problems without polynomial kernels
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- On sparse approximations to randomized strategies and convex combinations
- On interactive proofs with a laconic prover
- PSPACE has constant-round quantum interactive proof systems
- On relationships between statistical zero-knowledge proofs
- Lower bounds for predecessor searching in the cell probe model
- Simple strategies for large zero-sum games with applications to complexity theory
- FPT is characterized by useful obstruction sets
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- Kernel Bounds for Path and Cycle Problems
- Zero-knowledge against quantum attacks
- Abusing the Tutte Matrix: An Algebraic Instance Compression for the K-set-cycle Problem
- Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization
- On the Compressibility of $\mathcal{NP}$ Instances and Cryptographic Applications
- On the Complexity of Computational Problems Regarding Distributions
- Parallelization, amplification, and exponential time simulation of quantum interactive proof systems
- A complete problem for statistical zero knowledge
- Interaction in Quantum Communication
- Incompressibility through Colors and IDs
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- A Parallel Repetition Theorem
- Refinements of Pinsker's inequality
- Two-Message Quantum Interactive Proofs Are in PSPACE
- Computational Complexity
- Elements of Information Theory
