:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Baraskar, Omkar, Dewan, Agrim, Saha, Chandan, Sinha, Pulkit
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity
Online Access:	https://arxiv.org/abs/2410.12251
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Communication Complexity is NP-hard
by: Hirahara, Shuichi, et al.
Published: (2025)

Proper vs Improper Quantum PAC learning
by: Nayak, Ashwin, et al.
Published: (2024)

NP-hardness of SVP in Euclidean Space
by: Wan, Daqing
Published: (2026)

Optimizing for aggressive-style strategies in Flesh and Blood is NP-hard
by: Romão, Leonardo Gasparini, et al.
Published: (2025)

Positivity of the symmetric group characters is as hard as the polynomial time hierarchy
by: Ikenmeyer, Christian, et al.
Published: (2022)

Computing the EHZ capacity is NP-hard
by: Leipold, Karla, et al.
Published: (2024)

King Chasing Problem in Chinese Chess is NP-hard
by: Li, Chao, et al.
Published: (2026)

Quantum Max-Cut is NP hard to approximate
by: Piddock, Stephen
Published: (2025)

Nearly optimal algorithms to learn sparse quantum Hamiltonians in physically motivated distances
by: Abbas, Amira, et al.
Published: (2025)

Invariant polynomials, gaps, and sparseness
by: D'Angelo, John P., et al.
Published: (2025)

Prove Symbolic Regression is NP-hard by Symbol Graph
by: Song, Jinglu, et al.
Published: (2024)

Data Debugging is NP-hard for Classifiers Trained with SGD
by: Guo, Zizheng, et al.
Published: (2024)

Freeze-Tag is NP-hard in 2D with $L_1$ distance
by: Silva, Lucas de Oliveira, et al.
Published: (2025)

Approximating 1-in-3 SAT by linearly ordered hypergraph 3-colouring is NP-hard
by: Krokhin, Andrei, et al.
Published: (2025)

Two NP-hard Extensions of the Spearman Footrule even for a Small Constant Number of Voters
by: Durand, Martin
Published: (2026)

Computational-Statistical Tradeoffs from NP-hardness
by: Blanc, Guy, et al.
Published: (2025)

Unconditionally separating noisy $\mathsf{QNC}^0$ from bounded polynomial threshold circuits of constant depth
by: Hsieh, Min-Hsiu, et al.
Published: (2024)

The color code, the surface code, and the transversal CNOT: NP-hardness of minimum-weight decoding
by: Gu, Shouzhen, et al.
Published: (2026)

A note on polynomial-time tolerant testing stabilizer states
by: Arunachalam, Srinivasan, et al.
Published: (2024)

Fast interpolation and multiplication of unbalanced polynomials
by: Giorgi, Pascal, et al.
Published: (2024)

Fast polynomial computations with space constraints
by: Grenet, Bruno
Published: (2025)

P=NP
by: Deng, Zikang
Published: (2024)

Constant congestion linkages in polynomially strong digraphs in polynomial time
by: Lopes, Raul, et al.
Published: (2024)

Proofs of NP = coNP = PSPACE: Current upgrade
by: Gordeev, Lev, et al.
Published: (2023)

On $NP \cap coNP$ proof complexity generators
by: Krajicek, Jan
Published: (2025)

Wataridori is NP-Complete
by: Ruangwises, Suthee
Published: (2026)

P vs. NP
by: Uribe, Daniel
Published: (2016)

On P Versus NP
by: Gordeev, Lev
Published: (2020)

Nondango is NP-Complete
by: Ruangwises, Suthee
Published: (2023)

Fourier growth of structured $\mathbb{F}_2$-polynomials and applications
by: Błasiok, Jarosław, et al.
Published: (2021)

Constant-depth circuits for polynomial GCD over any characteristic
by: Bhattacharjee, Somnath, et al.
Published: (2025)

Halfspaces are hard to test with relative error
by: Chen, Xi, et al.
Published: (2025)

On the support of measures of large entropy for polynomial-like maps
by: Bazarbaev, Sardor, et al.
Published: (2024)

A Critique of Lin's "On $\text{NP}$ versus $\text{coNP}$ and Frege Systems"
by: DeJesse, Nicholas, et al.
Published: (2025)

BusOut is NP-complete
by: Ishibashi, Takehiro, et al.
Published: (2025)

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

Grothendieck inequalities characterize converses to the polynomial method
by: Briët, Jop, et al.
Published: (2022)

Inapproximability of the independent set polynomial in the complex plane
by: Bezakova, Ivona, et al.
Published: (2017)

Optimal lower bounds for Quantum Learning via Information Theory
by: Hadiashar, Shima Bab, et al.
Published: (2023)

Modular composition & polynomial GCD in the border of small, shallow circuits
by: Andrews, Robert, et al.
Published: (2025)