Imagen de Portada

On the Hardness of Order Finding and Equivalence Testing for ROABPs

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Ramya, C., Shastri, Pratik
Formato:	Preprint
Publicado:	2025
Materias:	Computational Complexity
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

The Complexity of Order-Finding for ROABPs
por: Bhargava, Vishwas, et al.
Publicado: (2024)

Lower bounds for planar Arithmetic Circuits
por: Ramya, C., et al.
Publicado: (2025)

Efficient Polynomial Identity Testing Over Nonassociative Algebras
por: Mukhopadhyay, Partha, et al.
Publicado: (2025)

A Quadratic Lower Bound for Noncommutative Circuits
por: Shastri, Pratik
Publicado: (2026)

IPS Lower Bounds for Formulas and Sum of ROABPs
por: Chatterjee, Prerona, et al.
Publicado: (2025)

Explicit Commutative ROABPs from Partial Derivatives
por: Bhargava, Vishwas, et al.
Publicado: (2024)

Optimal Proof Systems for Complex Sets are Hard to Find
por: Egidy, Fabian, et al.
Publicado: (2024)

On the Hardness of Finding Temporally Connected Subgraphs of Any Size
por: Casteigts, Arnaud, et al.
Publicado: (2026)

Generalized and Unified Equivalences between Hardness and Pseudoentropy
por: Hu, Lunjia, et al.
Publicado: (2025)

Hardness of Finding Kings and Strong Kings
por: Alaoui, Ziad Ismaili, et al.
Publicado: (2025)

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

Carrying is Hard: Exploring the Gap between Hardness for NP and PSPACE for the Hanano and Jelly no Puzzles
por: Chavrimootoo, Michael C., et al.
Publicado: (2026)

Testing Sumsets is Hard
por: Chen, Xi, et al.
Publicado: (2024)

Equivalence of Countable and Computable
por: Zhang, Hantao
Publicado: (2024)

On the Existence of Algebraic Natural Proofs
por: Chatterjee, Prerona, et al.
Publicado: (2020)

Characterizing and Testing Principal Minor Equivalence of Matrices
por: Chatterjee, Abhranil, et al.
Publicado: (2024)

Reductions Between Code Equivalence Problems
por: Cheraghchi, Mahdi, et al.
Publicado: (2025)

An Algebraic Rigidity Framework for Order-Oblivious Deterministic Black-Box PIT of ROABPs
por: Singh, Shalender, et al.
Publicado: (2026)

Hardness of SetCover Reoptimization
por: Jansen, Klaus, et al.
Publicado: (2025)

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

A Brief Note on a Recent Claim About NP-Hard Problems and BQP
por: Chavrimootoo, Michael C.
Publicado: (2024)

Hardness of clique approximation for monotone circuits
por: Błasiok, Jarosław, et al.
Publicado: (2025)

Bounds for Hardness Condensation in the Query Model
por: Kayal, Chandrima, et al.
Publicado: (2026)

Hardness Amplification via Group Theory
por: Nareddy, Tejas, et al.
Publicado: (2024)

Feature Selection and Junta Testing are Statistically Equivalent
por: Beretta, Lorenzo, et al.
Publicado: (2025)

Are Depth-2 Regular Expressions Hard to Intersect?
por: Ascone, Rocco, et al.
Publicado: (2025)

Near Optimal Hardness of Approximating $k$-CSP
por: Minzer, Dor, et al.
Publicado: (2025)

Higher Hardness Results for the Reconfiguration of Odd Matchings
por: Dorfer, Joseph
Publicado: (2026)

Hard-to-Sample Distributions from Robust Extractors
por: Byramji, Farzan, et al.
Publicado: (2026)

Tetris is Hard with Just One Piece Type
por: MIT Hardness Group, et al.
Publicado: (2026)

Hard CNF Instances for Ideal Proof Systems
por: Hakoniemi, Tuomas, et al.
Publicado: (2026)

Compression of Voxelized Vector Field Data by Boxes is Hard
por: Zhang, Simon
Publicado: (2025)

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

Hardness of Random Reordered Encodings of Parity for Resolution and CDCL
por: Chew, Leroy, et al.
Publicado: (2024)

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

Multiparty Communication Complexity of Collision Finding
por: Beame, Paul, et al.
Publicado: (2024)

Worst-Case and Average-Case Hardness of Hypercycle and Database Problems
por: Fu, Cheng-Hao, et al.
Publicado: (2025)

PCP-free APX-Hardness of Nearest Codeword and Minimum Distance
por: Bhattiprolu, Vijay, et al.
Publicado: (2025)

On the NP-Hardness Approximation Curve for Max-2Lin(2)
por: Martinsson, Björn
Publicado: (2024)

On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results
por: Guruswami, Venkatesan, et al.
Publicado: (2023)