On the public citation graph

New Limits to Classical and Quantum Instance Compression

0 signed · 133 inferred · view as graph

Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.

Is this your work? Sign in with ORCID and put your name on the claims that are yours.
Claim with ORCID
Reference health. See whether every reference in this work resolves to a known work and none has been retracted — and get a dated CiteStamped badge you can embed.
See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1002/047174882xopenalex-snapshot
Elements of Information Theory
inferredcites →https://doi.org/10.1006/inco.1995.1115openalex-snapshot
Approximable Sets
inferredcites →https://doi.org/10.1006/jcss.1995.1028openalex-snapshot
On Unique Satisfiability and the Threshold Behavior of Randomized Reductions
inferredcites →https://doi.org/10.1006/jcss.1999.1653openalex-snapshot
On Membership Comparable Sets
inferredcites →https://doi.org/10.1006/jcss.1999.1664openalex-snapshot
On Relationships between Statistical Zero-Knowledge Proofs
inferredcites →https://doi.org/10.1007/978-3-642-02927-1_32openalex-snapshot
Incompressibility through Colors and IDs
inferredcites →https://doi.org/10.1007/978-3-642-20712-9_8openalex-snapshot
Faster Polynomial Multiplication via Discrete Fourier Transforms
inferredcites →https://doi.org/10.1007/978-3-642-22006-7_37openalex-snapshot
Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization
inferredcites →https://doi.org/10.1007/978-3-642-22670-0_27openalex-snapshot
On the Complexity of Computational Problems Regarding Distributions
inferredcites →https://doi.org/10.1007/s00037-002-0169-0openalex-snapshot
On interactive proofs with a laconic prover
inferredcites →https://doi.org/10.1007/s00037-013-0071-yopenalex-snapshot
Derandomized Parallel Repetition Theorems for Free Games
inferredcites →https://doi.org/10.1007/s00224-010-9270-yopenalex-snapshot
Lower Bounds for Kernelizations and Other Preprocessing Procedures
inferredcites →https://doi.org/10.1007/s11856-012-0137-6openalex-snapshot
Entropy-based bounds on dimension reduction in L 1
inferredcites →https://doi.org/10.1016/0022-0000(88)90028-1openalex-snapshot
Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
inferredcites →https://doi.org/10.1016/0022-0000(91)90006-qopenalex-snapshot
Statistical zero-knowledge languages can be recognized in two rounds
inferredcites →https://doi.org/10.1016/0024-3795(94)90357-3openalex-snapshot
On sparse approximations to randomized strategies and convex combinations
inferredcites →https://doi.org/10.1016/0304-3975(83)90020-8openalex-snapshot
Some consequences of non-uniform conditions on uniform classes
inferredcites →https://doi.org/10.1016/0304-3975(86)90135-0openalex-snapshot
NP is as easy as detecting unique solutions
inferredcites →https://doi.org/10.1016/j.jcss.2007.06.016openalex-snapshot
Lower bounds for predecessor searching in the cell probe model
inferredcites →https://doi.org/10.1016/j.jcss.2007.06.020openalex-snapshot
Quantum certificate complexity
inferredcites →https://doi.org/10.1016/j.jcss.2009.04.001openalex-snapshot
On problems without polynomial kernels
inferredcites →https://doi.org/10.1016/j.jcss.2010.06.007openalex-snapshot
Infeasibility of instance compression and succinct PCPs for NP
inferredcites →https://doi.org/10.1016/j.tcs.2011.04.039openalex-snapshot
Kernel bounds for disjoint cycles and disjoint paths
inferredcites →https://doi.org/10.1016/j.tcs.2012.09.006openalex-snapshot
Kernel bounds for path and cycle problems
inferredcites →https://doi.org/10.1016/s0168-0072(95)00020-8openalex-snapshot
Advice classes of parameterized tractability
inferredcites →https://doi.org/10.1016/s0304-3975(01)00144-xopenalex-snapshot
Complexity measures and decision tree complexity: a survey
inferredcites →https://doi.org/10.1016/s0304-3975(01)00375-9openalex-snapshot
PSPACE has constant-round quantum interactive proof systems
inferredcites →https://doi.org/10.1016/s0890-5401(03)00091-9openalex-snapshot
Some connections between bounded query classes and non-uniform complexity
inferredcites →https://doi.org/10.1109/18.782097openalex-snapshot
Improved decoding of Reed-Solomon and algebraic-geometry codes
inferredcites →https://doi.org/10.1109/ccc.1997.612295openalex-snapshot
Six hypotheses in search of a theorem
inferredcites →https://doi.org/10.1109/ccc.2008.21openalex-snapshot
NP-Hard Sets Are Exponentially Dense Unless coNP C NP/poly
inferredcites →https://doi.org/10.1109/focs.2006.54openalex-snapshot
On the Compressibility of NP Instances and Cryptographic Applications
inferredcites →https://doi.org/10.1109/focs.2009.30openalex-snapshot
Two-Message Quantum Interactive Proofs Are in PSPACE
inferredcites →https://doi.org/10.1109/sct.1994.315821openalex-snapshot
Polynomial time truth-table reductions to p-selective sets
inferredcites →https://doi.org/10.1109/sfcs.1978.37openalex-snapshot
Two theorems on random polynomial time
inferredcites →https://doi.org/10.1109/sfcs.1996.548475openalex-snapshot
Maximum likelihood decoding of Reed Solomon codes
inferredcites →https://doi.org/10.1109/sfcs.2002.1181970openalex-snapshot
Limits on the power of quantum statistical zero-knowledge
inferredcites →https://doi.org/10.1109/sffcs.1999.814608openalex-snapshot
Optimal lower bounds for quantum automata and random access codes
inferredcites →https://doi.org/10.1109/tit.2003.811927openalex-snapshot
Refinements of Pinsker's inequality
inferredcites →https://doi.org/10.1109/tit.2007.896888openalex-snapshot
Interaction in Quantum Communication
inferredcites →https://doi.org/10.1119/1.1463744openalex-snapshot
Quantum Computation and Quantum Information
inferredcites →https://doi.org/10.1137/0210008openalex-snapshot
Relative to a Random Oracle A , ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
inferredcites →https://doi.org/10.1137/0214024openalex-snapshot
Trade-Offs between Depth and Width in Parallel Computation
inferredcites →https://doi.org/10.1137/0220062openalex-snapshot
CREW PRAM s and Decision Trees
inferredcites →https://doi.org/10.1137/060668092openalex-snapshot
On the Compressibility of $\mathcal{NP}$ Instances and Cryptographic Applications
inferredcites →https://doi.org/10.1137/060670997openalex-snapshot
Zero-Knowledge against Quantum Attacks
inferredcites →https://doi.org/10.1137/1.9781611973099.6openalex-snapshot
Kernelization of Packing Problems
inferredcites →https://doi.org/10.1137/1.9781611973099.9openalex-snapshot
Weak Compositions and Their Applications to Polynomial Lower Bounds for Kernelization
inferredcites →https://doi.org/10.1137/s0097539793258131openalex-snapshot
Polynomial-Time Membership Comparable Sets
inferredcites →https://doi.org/10.1137/s0097539795280895openalex-snapshot
A Parallel Repetition Theorem
inferredcites →https://doi.org/10.1137/s0097539796297577openalex-snapshot
Reconstructing Algebraic Functions from Mixed Data
inferredcites →https://doi.org/10.1145/12130.12137openalex-snapshot
Private coins versus public coins in interactive proof systems
inferredcites →https://doi.org/10.1145/1233481.1233493openalex-snapshot
Invitation to data reduction and problem kernelization
inferredcites →https://doi.org/10.1145/1806689.1806725openalex-snapshot
Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
inferredcites →https://doi.org/10.1145/195058.195447openalex-snapshot
Simple strategies for large zero-sum games with applications to complexity theory
inferredcites →https://doi.org/10.1145/2049697.2049704openalex-snapshot
QIP = PSPACE
inferredcites →https://doi.org/10.1145/2422436.2422485openalex-snapshot
Properties and applications of boolean function composition
inferredcites →https://doi.org/10.1145/2635808openalex-snapshot
Co-Nondeterminism in Compositions
inferredcites →https://doi.org/10.1145/276698.276852openalex-snapshot
Honest-verifier statistical zero-knowledge equals general statistical zero-knowledge
inferredcites →https://doi.org/10.1145/28395.28418openalex-snapshot
The complexity of perfect zero-knowledge
inferredcites →https://doi.org/10.1145/335305.335387openalex-snapshot
Parallelization, amplification, and exponential time simulation of quantum interactive proof systems
inferredcites →https://doi.org/10.1145/505482.505499openalex-snapshot
Quantum computation and quantum information
inferredcites →https://doi.org/10.1145/636865.636868openalex-snapshot
A complete problem for statistical zero knowledge
inferredcites →https://doi.org/10.1145/779928.779933openalex-snapshot
Playing large games using simple strategies
inferredcites →https://doi.org/10.1145/780542.780560openalex-snapshot
Exponential lower bound for 2-query locally decodable codes via a quantum argument
inferredcites →https://doi.org/10.4230/lipics.stacs.2013.341openalex-snapshot
Abusing the Tutte Matrix: An Algebraic Instance Compression for the K-set-cycle Problem
inferredcites →https://doi.org/10.48550/arxiv.0906.1244openalex-snapshot
Generalised Pinsker Inequalities
inferredcites →https://doi.org/10.48550/arxiv.1011.4224openalex-snapshot
Cross-Composition: A New Technique for Kernelization Lower Bounds
inferredcites →https://doi.org/10.48550/arxiv.1106.4141openalex-snapshot
Kernel Bounds for Path and Cycle Problems
inferredcites →https://doi.org/10.48550/arxiv.1108.1283openalex-snapshot
Entropy-based Bounds on Dimension Reduction in L_1

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.1007/978-1-4471-5559-1_30openalex-snapshot
Kernelization Lower Bounds
inferred← citeshttps://doi.org/10.1007/978-1-4939-2864-4_521openalex-snapshot
Kernelization, Exponential Lower Bounds
inferred← citeshttps://doi.org/10.1007/978-1-4939-2864-4_529openalex-snapshot
Kernelization, Preprocessing for Treewidth
inferred← citeshttps://doi.org/10.1007/978-3-030-75242-2_16openalex-snapshot
A Multistage View on 2-Satisfiability
inferred← citeshttps://doi.org/10.1007/978-3-319-03898-8_18openalex-snapshot
A Completeness Theory for Polynomial (Turing) Kernelization
inferred← citeshttps://doi.org/10.1007/978-3-319-03898-8_19openalex-snapshot
On Sparsification for Computing Treewidth
inferred← citeshttps://doi.org/10.1007/978-3-319-03898-8_29openalex-snapshot
Treewidth and Pure Nash Equilibria
inferred← citeshttps://doi.org/10.1007/978-3-319-13524-3_1openalex-snapshot
Lower Bounds for Kernelization
inferred← citeshttps://doi.org/10.1007/978-3-319-13524-3_16openalex-snapshot
AND-compression of NP-complete Problems: Streamlined Proof and Minor Observations
inferred← citeshttps://doi.org/10.1007/978-3-319-22177-9_15openalex-snapshot
Multidimensional Binary Vector Assignment Problem: Standard, Structural and Above Guarantee Parameterizations
inferred← citeshttps://doi.org/10.1007/978-3-319-53733-7_25openalex-snapshot
Partitioning Graphs into Induced Subgraphs
inferred← citeshttps://doi.org/10.1007/978-3-642-27848-8_521-1openalex-snapshot
Kernelization, Exponential Lower Bounds
inferred← citeshttps://doi.org/10.1007/978-3-642-28050-4_20openalex-snapshot
On Cutwidth Parameterized by Vertex Cover
inferred← citeshttps://doi.org/10.1007/978-3-642-30891-8_12openalex-snapshot
Fixed-Parameter Tractability of Treewidth and Pathwidth
inferred← citeshttps://doi.org/10.1007/978-3-642-32589-2_2openalex-snapshot
New Races in Parameterized Algorithmics
inferred← citeshttps://doi.org/10.1007/978-3-642-40104-6_18openalex-snapshot
On Explaining Integer Vectors by Few Homogenous Segments
inferred← citeshttps://doi.org/10.1007/978-3-642-40104-6_21openalex-snapshot
Treewidth and Pathwidth Parameterized by the Vertex Cover Number
inferred← citeshttps://doi.org/10.1007/978-3-642-45043-3_23openalex-snapshot
FPT Is Characterized by Useful Obstruction Sets
inferred← citeshttps://doi.org/10.1007/978-3-662-44602-7_7openalex-snapshot
Treewidth Computation and Kernelization in the Parallel External Memory Model
inferred← citeshttps://doi.org/10.1007/978-3-662-48054-0_24openalex-snapshot
Polynomial Kernels for Weighted Problems
inferred← citeshttps://doi.org/10.1007/978-3-662-53644-5_7openalex-snapshot
Towards Non-Black-Box Separations of Public Key Encryption and One Way Function
inferred← citeshttps://doi.org/10.1007/s00236-022-00428-yopenalex-snapshot
Reoptimization of parameterized problems
inferred← citeshttps://doi.org/10.1007/s00453-012-9707-6openalex-snapshot
On Cutwidth Parameterized by Vertex Cover
inferred← citeshttps://doi.org/10.1007/s00453-014-9910-8openalex-snapshot
A Completeness Theory for Polynomial (Turing) Kernelization
inferred← citeshttps://doi.org/10.1007/s00453-014-9923-3openalex-snapshot
Pure Nash Equilibria in Graphical Games and Treewidth
inferred← citeshttps://doi.org/10.1007/s00453-014-9924-2openalex-snapshot
On Sparsification for Computing Treewidth
inferred← citeshttps://doi.org/10.1007/s00453-015-0110-yopenalex-snapshot
AND-Compression of NP-Complete Problems: Streamlined Proof and Minor Observations
inferred← citeshttps://doi.org/10.1007/s00453-018-0408-7openalex-snapshot
Parameterized Complexity of Length-bounded Cuts and Multicuts
inferred← citeshttps://doi.org/10.1016/j.artint.2014.06.006openalex-snapshot
Guarantees and limits of preprocessing in constraint satisfaction and reasoning
inferred← citeshttps://doi.org/10.1016/j.dam.2014.12.012openalex-snapshot
Treewidth and Pathwidth parameterized by the vertex cover number
inferred← citeshttps://doi.org/10.1016/j.jcss.2014.12.028openalex-snapshot
On explaining integer vectors by few homogeneous segments
inferred← citeshttps://doi.org/10.1016/j.jcss.2016.06.004openalex-snapshot
Polynomial kernels for weighted problems
inferred← citeshttps://doi.org/10.1109/focs.2012.46openalex-snapshot
Representative Sets and Irrelevant Vertices: New Tools for Kernelization
inferred← citeshttps://doi.org/10.1109/focs.2013.84openalex-snapshot
Nondeterministic Direct Product Reductions and the Success Probability of SAT Solvers
inferred← citeshttps://doi.org/10.1109/focs.2014.37openalex-snapshot
Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs
inferred← citeshttps://doi.org/10.1109/tit.2014.2339859openalex-snapshot
The Space Complexity of Recognizing Well-Parenthesized Expressions in the Streaming Model: The Index Function Revisited
inferred← citeshttps://doi.org/10.1137/1.9781611973730.19openalex-snapshot
Degree-3 Treewidth Sparsifiers
inferred← citeshttps://doi.org/10.1137/1.9781611973730.42openalex-snapshot
Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels
inferred← citeshttps://doi.org/10.1145/2488608.2488640openalex-snapshot
Shielding circuits with groups
inferred← citeshttps://doi.org/10.1145/2594439openalex-snapshot
Clique Cover and Graph Separation
inferred← citeshttps://doi.org/10.1145/2629620openalex-snapshot
Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
inferred← citeshttps://doi.org/10.1145/2635810openalex-snapshot
Compression via Matroids
inferred← citeshttps://doi.org/10.1145/2635820openalex-snapshot
FPT is characterized by useful obstruction sets
inferred← citeshttps://doi.org/10.1145/2650261openalex-snapshot
Kernelization Lower Bounds Through Colors and IDs
inferred← citeshttps://doi.org/10.1145/2851494openalex-snapshot
Experimental Evaluation of a Branch-and-Bound Algorithm for Computing Pathwidth and Directed Pathwidth
inferred← citeshttps://doi.org/10.1145/3155298openalex-snapshot
Kernels for (Connected) Dominating Set on Graphs with Excluded Topological Minors
inferred← citeshttps://doi.org/10.14279/depositonce-3922openalex-snapshot
Exploring parameter spaces in coping with computational intractability
inferred← citeshttps://doi.org/10.15496/publikation-26302openalex-snapshot
Having a Hard Time? Explore Parameterized Complexity!
inferred← citeshttps://doi.org/10.17760/d20005081openalex-snapshot
Towards bridging theory and implementation of cryptographic primitives
inferred← citeshttps://doi.org/10.4230/lipics.ccc.2015.488openalex-snapshot
Generalized Quantum Arthur-Merlin Games
inferred← citeshttps://doi.org/10.4230/lipics.icalp.2016.25openalex-snapshot
Fractals for Kernelization Lower Bounds, With an Application to Length-Bounded Cut Problems
inferred← citeshttps://doi.org/10.4230/lipics.stacs.2013.92openalex-snapshot
Linear kernels for (connected) dominating set on graphs with excluded topological subgraphs
inferred← citeshttps://doi.org/10.48550/arxiv.1104.4217openalex-snapshot
Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization
inferred← citeshttps://doi.org/10.48550/arxiv.1206.5941openalex-snapshot
Kernelization Lower Bounds By Cross-Composition
inferred← citeshttps://doi.org/10.48550/arxiv.1210.0257openalex-snapshot
Kernels for (connected) Dominating Set on graphs with Excluded Topological subgraphs
inferred← citeshttps://doi.org/10.48550/arxiv.1301.1517openalex-snapshot
Abusing the Tutte Matrix: An Algebraic Instance Compression for the K-set-cycle Problem
inferred← citeshttps://doi.org/10.48550/arxiv.1308.3665openalex-snapshot
On Sparsification for Computing Treewidth
inferred← citeshttps://doi.org/10.48550/arxiv.1404.7006openalex-snapshot
Parameterized Complexity Dichotomy for Steiner Multicut
inferred← citeshttps://doi.org/10.48550/arxiv.1503.06321openalex-snapshot
Parameterized Complexity of Critical Node Cuts
inferred← citeshttps://doi.org/10.48550/arxiv.1507.03439openalex-snapshot
Polynomial Kernels for Weighted Problems
inferred← citeshttps://doi.org/10.5255/ukda-sn-857898openalex-snapshot
Tracking Treatment Changes in People with Chronic Lung-Related Blood Pressure Problems: A Prospective Cohort Study, 2024-2025
inferred← citeshttps://doi.org/10.5555/3310435.3310538openalex-snapshot
Interval vertex deletion admits a polynomial kernel
inferred← citeshttps://doi.org/10.5753/etc.2021.16384openalex-snapshot
Sobre o Número de Orientação Própria de Grafos Cordais
Editorial review for independent work. ICSAC — the Institute for Complexity Science and Advanced Computing — runs a structured editorial panel for researchers publishing outside journals, and publishes on CiteStamp rails. Submission is free and goes through ORCID: icsacinstitute.org/submit.