Cover Image

Identifying Codes Kernelization Limitations

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Banik, Aritra, Patra, Praneet Kumar, Rescigno, Adele Anna, Sahu, Abhishek
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Kidney Exchange: Faster Parameterized Algorithms and Tighter Lower Bounds
by: Banik, Aritra, et al.
Published: (2025)

Spanning Trees Minimizing Branching Costs
by: Gargano, Luisa, et al.
Published: (2024)

Inclusive and Exclusive Vertex Splitting into Specific Graph Classes: NP Hardness and Algorithms
by: Gaikwad, Ajinkya, et al.
Published: (2025)

Parameterized Complexity of (d,r)-Domination via Modular Decomposition
by: Cordasco, Gennaro, et al.
Published: (2024)

Distance Vector Domination
by: Cordasco, Gennaro, et al.
Published: (2024)

Limits of Kernelization and Parametrization for Phylogenetic Diversity with Dependencies
by: Holtgrefe, Niels, et al.
Published: (2026)

On Kernelization with Access to NP-Oracles
by: Molter, Hendrik, et al.
Published: (2025)

The Optimization of Random Tree Codes for Limited Computational Resources
by: Bacinoglu, B. Tan
Published: (2025)

Recovery Reductions, Conjectures, and Barriers
by: Nareddy, Tejas, et al.
Published: (2025)

New Techniques for Constructing Rare-Case Hard Functions
by: Nareddy, Tejas, et al.
Published: (2024)

Hardness Amplification via Group Theory
by: Nareddy, Tejas, et al.
Published: (2024)

Relaxed vs. Full Local Decodability with Few Queries: Equivalence and Separations for Linear Codes
by: Grigorescu, Elena, et al.
Published: (2025)

Advances in List Decoding of Polynomial Codes
by: Kumar, Mrinal, et al.
Published: (2026)

High Rate Multivariate Polynomial Evaluation Codes
by: Kopparty, Swastik, et al.
Published: (2024)

Limit on the computational power of $\mathrm{C}$-random strings
by: Milovanov, Alexey
Published: (2026)

Reductions Between Code Equivalence Problems
by: Cheraghchi, Mahdi, et al.
Published: (2025)

Limitations of Affine Integer Relaxations for Solving Constraint Satisfaction Problems
by: Lichter, Moritz, et al.
Published: (2024)

Limits of Sequential Local Algorithms on the Random $k$-XORSAT Problem
by: Yung, Kingsley
Published: (2024)

Limit-sure reachability for small memory policies in POMDPs is NP-complete
by: Asadi, Ali, et al.
Published: (2024)

Optimal Coding for Randomized Kolmogorov Complexity and Its Applications
by: Hirahara, Shuichi, et al.
Published: (2024)

Kernelization Bounds for Constrained Coloring
by: Haviv, Ishay
Published: (2026)

Isomorphism Testing of Rooted Trees in Linear Time
by: Lindeberg, Anna
Published: (2024)

Good Locally Testable Codes with Small Alphabet and Small Query Size
by: First, Uriya, et al.
Published: (2025)

Statistical and Computational Guarantees of Kernel Max-Sliced Wasserstein Distances
by: Wang, Jie, et al.
Published: (2024)

Parameterized Complexity of Finding a Maximum Common Vertex Subgraph Without Isolated Vertices
by: Dey, Palash, et al.
Published: (2026)

Limits of structures and Total NP Search Problems
by: Ježil, Ondřej
Published: (2023)

The Limits of Tractable Marginalization
by: Broadrick, Oliver, et al.
Published: (2025)

An exposition of recent list-size bounds of FRS Codes
by: Garg, Abhibhav, et al.
Published: (2025)

A Linear Kernel for Planar Vector Domination
by: Sahili, Mahabba El, et al.
Published: (2023)

New Pseudorandom Generators and Correlation Bounds Using Extractors
by: Kumar, Vinayak M.
Published: (2025)

Oblivious Deletion Codes
by: Con, Roni, et al.
Published: (2025)

Transcendental Encoding conjecture
by: Keshavan, Anand Kumar, et al.
Published: (2025)

Kernelization Complexity of Solution Discovery Problems
by: Grobler, Mario, et al.
Published: (2024)

Improved Lower Bounds for all Odd-Query Locally Decodable Codes
by: Basu, Arpon, et al.
Published: (2024)

When Majority Fails: Tight Bounds for Correlation Distillation Conjectures
by: Kamath, Pritish, et al.
Published: (2026)

Separations above TFNP from Sherali-Adams Lower Bounds
by: Fleming, Noah, et al.
Published: (2026)

Rank Bounds and PIT for $Σ^3 ΠΣΠ^d$ circuits via a non-linear Edelstein-Kelly theorem
by: Garg, Abhibhav, et al.
Published: (2025)

Decoding Balanced Linear Codes With Preprocessing
by: Bogdanov, Andrej, et al.
Published: (2025)

If VNP is hard, then so are equations for it
by: Kumar, Mrinal, et al.
Published: (2020)

Small Even Covers, Locally Decodable Codes and Restricted Subgraphs of Edge-Colored Kikuchi Graphs
by: Hsieh, Jun-Ting, et al.
Published: (2024)