Cover Image

Reductions Between Code Equivalence Problems

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Cheraghchi, Mahdi, Shagrithaya, Nikhil, Veliche, Alexandra
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

Parameterized Inapproximability of the Minimum Distance Problem over all Fields and the Shortest Vector Problem in all $\ell_p$ Norms
by: Bennett, Huck, et al.
Published: (2022)

Optimal Erasure Codes and Codes on Graphs
by: Chen, Yeyuan, et al.
Published: (2025)

Gap Preserving Reductions Between Reconfiguration Problems
by: Ohsaka, Naoto
Published: (2022)

Exploring the Reductions Between SSP-NP-complete Problems and Developing a Compendium Website Displaying the Results
by: Pfaue, Femke
Published: (2024)

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

Equivalent Instances for Scheduling and Packing Problems
by: Jansen, Klaus, et al.
Published: (2025)

Tight Bounds for Quantum Phase Estimation and Related Problems
by: Mande, Nikhil S., et al.
Published: (2023)

Equivalence of Countable and Computable
by: Zhang, Hantao
Published: (2024)

Fine-Grained Equivalence for Problems Related to Integer Linear Programming
by: Rohwedder, Lars, et al.
Published: (2024)

Random Reed-Solomon Codes and Random Linear Codes are Locally Equivalent
by: Levi, Matan, et al.
Published: (2024)

On the Hardness of Order Finding and Equivalence Testing for ROABPs
by: Ramya, C., et al.
Published: (2025)

Query Complexity with Unknowns
by: Mande, Nikhil S., et al.
Published: (2024)

The Log-Rank Conjecture: New Equivalent Formulations
by: Hambardzumyan, Lianna, et al.
Published: (2025)

Instance complexity of Boolean functions
by: Liu, Alison Hsiang-Hsuan, et al.
Published: (2023)

Quasi-Linear Size PCPs with Small Soundness from HDX
by: Bafna, Mitali, et al.
Published: (2024)

Alphabet Reduction for Reconfiguration Problems
by: Ohsaka, Naoto
Published: (2024)

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

Polynomial Equivalence of Extended Chemical Reaction Models
by: Bajaj, Divya, et al.
Published: (2025)

Towards Geometry-Preserving Reductions Between Constraint Satisfaction Problems (and other problems in NP)
by: Istrate, Gabriel
Published: (2024)

A Compendium of Reductions: reductions.network
by: Grüne, Christoph, et al.
Published: (2025)

Lower bounds for quantum-inspired classical algorithms via communication complexity
by: Mande, Nikhil S., et al.
Published: (2024)

On the Equivalence of Gaussian Graphical Models Defined on Complete Bipartite Graphs
by: Molkaraie, Mehdi
Published: (2025)

On Computability of Computable Problems
by: Khaliq, Asad
Published: (2023)

The Stochastic Arrival Problem
by: Webster, Thomas
Published: (2022)

What Juris Hartmanis taught me about Reductions
by: Immerman, Neil
Published: (2024)

Rewindable Quantum Computation and Its Equivalence to Cloning and Adaptive Postselection
by: Hiromasa, Ryo, et al.
Published: (2022)

Identifying Codes Kernelization Limitations
by: Banik, Aritra, et al.
Published: (2025)

On the Hardness of the Drone Delivery Problem
by: Bartlmae, Simon, et al.
Published: (2025)

The Greedy Coin Change Problem
by: Gupta, Shreya, et al.
Published: (2024)

Continuous Defensive Domination Problems
by: Grüne, Christoph, et al.
Published: (2026)

A Multivariate to Bivariate Reduction for Noncommutative Rank and Related Results
by: Arvind, Vikraman, et al.
Published: (2024)

A parametric version of the Hilbert Nullstellensatz
by: Manssour, Rida Ait El, et al.
Published: (2024)

Between the deterministic and non-deterministic query complexity
by: Gerbner, Dániel
Published: (2019)

Toward a Uniform Algorithm and Uniform Reduction for Constraint Problems
by: Barto, Libor, et al.
Published: (2026)

Parameterized Algorithms for Matching Integer Programs with Additional Rows and Columns
by: Lassota, Alexandra, et al.
Published: (2025)

Solving 4-Block Integer Linear Programs Faster Using Affine Decompositions of the Right-Hand Sides
by: Lassota, Alexandra, et al.
Published: (2026)

Total Search Problems in $\mathsf{ZPP}$
by: Fleming, Noah, et al.
Published: (2025)

Inverse Intersections for Boolean Satisfiability Problems
by: Homer, Paul W.
Published: (2025)

Parameterized Complexity of the Star Decomposition Problem
by: Hajebi, Sahab, et al.
Published: (2024)

On the Complexity of Problems on Tree-structured Graphs
by: Bodlaender, Hans L., et al.
Published: (2022)