Buchumschlag

Identifying Codes Kernelization Limitations

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Banik, Aritra, Patra, Praneet Kumar, Rescigno, Adele Anna, Sahu, Abhishek
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Computational Complexity
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Kidney Exchange: Faster Parameterized Algorithms and Tighter Lower Bounds
von: Banik, Aritra, et al.
Veröffentlicht: (2025)

Spanning Trees Minimizing Branching Costs
von: Gargano, Luisa, et al.
Veröffentlicht: (2024)

Inclusive and Exclusive Vertex Splitting into Specific Graph Classes: NP Hardness and Algorithms
von: Gaikwad, Ajinkya, et al.
Veröffentlicht: (2025)

Parameterized Complexity of (d,r)-Domination via Modular Decomposition
von: Cordasco, Gennaro, et al.
Veröffentlicht: (2024)

Distance Vector Domination
von: Cordasco, Gennaro, et al.
Veröffentlicht: (2024)

Limits of Kernelization and Parametrization for Phylogenetic Diversity with Dependencies
von: Holtgrefe, Niels, et al.
Veröffentlicht: (2026)

On Kernelization with Access to NP-Oracles
von: Molter, Hendrik, et al.
Veröffentlicht: (2025)

The Optimization of Random Tree Codes for Limited Computational Resources
von: Bacinoglu, B. Tan
Veröffentlicht: (2025)

Recovery Reductions, Conjectures, and Barriers
von: Nareddy, Tejas, et al.
Veröffentlicht: (2025)

New Techniques for Constructing Rare-Case Hard Functions
von: Nareddy, Tejas, et al.
Veröffentlicht: (2024)

Hardness Amplification via Group Theory
von: Nareddy, Tejas, et al.
Veröffentlicht: (2024)

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

Advances in List Decoding of Polynomial Codes
von: Kumar, Mrinal, et al.
Veröffentlicht: (2026)

High Rate Multivariate Polynomial Evaluation Codes
von: Kopparty, Swastik, et al.
Veröffentlicht: (2024)

Limit on the computational power of $\mathrm{C}$-random strings
von: Milovanov, Alexey
Veröffentlicht: (2026)

Reductions Between Code Equivalence Problems
von: Cheraghchi, Mahdi, et al.
Veröffentlicht: (2025)

Limitations of Affine Integer Relaxations for Solving Constraint Satisfaction Problems
von: Lichter, Moritz, et al.
Veröffentlicht: (2024)

Limits of Sequential Local Algorithms on the Random $k$-XORSAT Problem
von: Yung, Kingsley
Veröffentlicht: (2024)

Limit-sure reachability for small memory policies in POMDPs is NP-complete
von: Asadi, Ali, et al.
Veröffentlicht: (2024)

Optimal Coding for Randomized Kolmogorov Complexity and Its Applications
von: Hirahara, Shuichi, et al.
Veröffentlicht: (2024)

Kernelization Bounds for Constrained Coloring
von: Haviv, Ishay
Veröffentlicht: (2026)

Isomorphism Testing of Rooted Trees in Linear Time
von: Lindeberg, Anna
Veröffentlicht: (2024)

Good Locally Testable Codes with Small Alphabet and Small Query Size
von: First, Uriya, et al.
Veröffentlicht: (2025)

Statistical and Computational Guarantees of Kernel Max-Sliced Wasserstein Distances
von: Wang, Jie, et al.
Veröffentlicht: (2024)

Parameterized Complexity of Finding a Maximum Common Vertex Subgraph Without Isolated Vertices
von: Dey, Palash, et al.
Veröffentlicht: (2026)

Limits of structures and Total NP Search Problems
von: Ježil, Ondřej
Veröffentlicht: (2023)

The Limits of Tractable Marginalization
von: Broadrick, Oliver, et al.
Veröffentlicht: (2025)

An exposition of recent list-size bounds of FRS Codes
von: Garg, Abhibhav, et al.
Veröffentlicht: (2025)

A Linear Kernel for Planar Vector Domination
von: Sahili, Mahabba El, et al.
Veröffentlicht: (2023)

New Pseudorandom Generators and Correlation Bounds Using Extractors
von: Kumar, Vinayak M.
Veröffentlicht: (2025)

Oblivious Deletion Codes
von: Con, Roni, et al.
Veröffentlicht: (2025)

Transcendental Encoding conjecture
von: Keshavan, Anand Kumar, et al.
Veröffentlicht: (2025)

Kernelization Complexity of Solution Discovery Problems
von: Grobler, Mario, et al.
Veröffentlicht: (2024)

Improved Lower Bounds for all Odd-Query Locally Decodable Codes
von: Basu, Arpon, et al.
Veröffentlicht: (2024)

When Majority Fails: Tight Bounds for Correlation Distillation Conjectures
von: Kamath, Pritish, et al.
Veröffentlicht: (2026)

Separations above TFNP from Sherali-Adams Lower Bounds
von: Fleming, Noah, et al.
Veröffentlicht: (2026)

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

Decoding Balanced Linear Codes With Preprocessing
von: Bogdanov, Andrej, et al.
Veröffentlicht: (2025)

If VNP is hard, then so are equations for it
von: Kumar, Mrinal, et al.
Veröffentlicht: (2020)

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