Cover Image

Recovery Reductions, Conjectures, and Barriers

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Nareddy, Tejas, Mishra, 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

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)

Reductive Shafarevich Conjecture
by: Deng, Ya, et al.
Published: (2023)

Aaronson-Ambainis Conjecture Is True For Random Restrictions
by: Bhattacharya, Sreejata Kishor
Published: (2024)

On the Keevash-Knox-Mycroft Conjecture
by: Gan, Luyining, et al.
Published: (2022)

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

Refuting the Direct Sum Conjecture for Total Functions in Deterministic Communication Complexity
by: Mackenzie, Simon, et al.
Published: (2024)

A Lower Bound on the Constant in the Fourier Min-Entropy/Influence Conjecture
by: Biswas, Aniruddha, et al.
Published: (2022)

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

The Rank-Ramsey Problem and the Log-Rank Conjecture
by: Beniamini, Gal, et al.
Published: (2024)

A Quantum Unique Games Conjecture
by: Mousavi, Hamoon, et al.
Published: (2024)

Tensor Hinted Mv Conjectures
by: Song, Zhao
Published: (2026)

The Fine-Grained Complexity of Graph Homomorphism Problems: Towards the Okrasa and Rzążewski Conjecture
by: Baril, Ambroise, et al.
Published: (2024)

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

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

Breaking the Temporal Complexity Barrier: Bucket Calculus for Parallel Machine Scheduling
by: Mohammad, Noor Islam S.
Published: (2026)

Large Average Subtensor Problem: Ground-State, Algorithms, and Algorithmic Barriers
by: R., Abhishek Hegade K., et al.
Published: (2025)

$\exists\mathbb{R}$-Completeness of Tensor Degeneracy and a Derandomization Barrier for Hyperdeterminants
by: Majumdar, Angshul
Published: (2026)

Planar Graph Homomorphisms: A Dichotomy and a Barrier from Quantum Groups
by: Cai, Jin-Yi, et al.
Published: (2026)

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

New Algebrization Barriers to Circuit Lower Bounds via Communication Complexity of Missing-String
by: Chen, Lijie, et al.
Published: (2025)

The Quasi-Polynomial Low-Degree Conjecture is False
by: Buhai, Rares-Darius, et al.
Published: (2025)

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

A New Reduction Method from Multivariate Polynomials to Univariate Polynomials
by: Wang, Cancan, et al.
Published: (2024)

Lower Bounds on Cardinality of Reducts for Decision Tables from Closed Classes
by: Ostonov, Azimkhon, et al.
Published: (2024)

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

An Intrinsic Barrier for Resolving P = NP (2-SAT as Flat, 3-SAT as High-Dimensional Void-Rich)
by: Alasli, M.
Published: (2025)

Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture
by: Gharibian, Sevag, et al.
Published: (2021)

Guidable Local Hamiltonian Problems with Implications to Heuristic Ansätze State Preparation and the Quantum PCP Conjecture
by: Weggemans, Jordi, et al.
Published: (2023)

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

Proof of Hiding Conjecture in Gaussian Boson Sampling
by: Shou, Laura, et al.
Published: (2025)

A Subexponential Reduction from Product Partition to Subset Sum
by: Costandin, Marius
Published: (2024)

Modular Counting CSP: Reductions and Algorithms
by: Kazeminia, Amirhossein, et al.
Published: (2025)

Specification and Automatic Verification of Computational Reductions
by: Grange, Julien, et al.
Published: (2024)

Structure Theorems (and Fast Algorithms) for List Recovery of Subspace-Design Codes
by: Goyal, Rohan, et al.
Published: (2025)

A simplified proof of the CSP Dichotomy Conjecture and XY-symmetric operations
by: Zhuk, Dmitriy
Published: (2024)

An Unconditional Barrier for Proving Multilinear Algebraic Branching Program Lower Bounds
by: Kush, Deepanshu
Published: (2026)

Barriers to Complexity-Theoretic Proofs that "AGI" Using Machine Learning is Impossible
by: Guerzhoy, Michael
Published: (2024)

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

Information Redistribution Under Reductions in NP Search
by: Wei, Jing-Yuan
Published: (2026)