Buchumschlag

The Complexity of Order-Finding for ROABPs

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Bhargava, Vishwas, Dutta, Pranjal, Ghosh, Sumanta, Tengse, Anamay
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Computational Complexity
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Explicit Commutative ROABPs from Partial Derivatives
von: Bhargava, Vishwas, et al.
Veröffentlicht: (2024)

Lower Bounds from Succinct Hitting Sets
von: Chatterjee, Prerona, et al.
Veröffentlicht: (2023)

On the Hardness of Order Finding and Equivalence Testing for ROABPs
von: Ramya, C., et al.
Veröffentlicht: (2025)

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

On the Existence of Algebraic Natural Proofs
von: Chatterjee, Prerona, et al.
Veröffentlicht: (2020)

Near-Optimal Bootstrapping of Hitting Sets for Algebraic Models
von: Kumar, Mrinal, et al.
Veröffentlicht: (2018)

IPS Lower Bounds for Formulas and Sum of ROABPs
von: Chatterjee, Prerona, et al.
Veröffentlicht: (2025)

Derandomizing Multivariate Polynomial Factoring for Low Degree Factors
von: Dutta, Pranjal, et al.
Veröffentlicht: (2024)

Exponential lower bound via exponential sums
von: Bhattacharjee, Somnath, et al.
Veröffentlicht: (2026)

Structure of sparse Boolean functions over Abelian groups, and its application to testing
von: Chakraborty, Sourav, et al.
Veröffentlicht: (2024)

Homogeneous Algebraic Complexity Theory and Algebraic Formulas
von: Dutta, Pranjal, et al.
Veröffentlicht: (2023)

Multiparty Communication Complexity of Collision Finding
von: Beame, Paul, et al.
Veröffentlicht: (2024)

Optimal Proof Systems for Complex Sets are Hard to Find
von: Egidy, Fabian, et al.
Veröffentlicht: (2024)

A Parameterized-Complexity Framework for Finding Local Optima
von: Ganian, Robert, et al.
Veröffentlicht: (2026)

Recent Advances in Debordering Methods
von: Dutta, Pranjal, et al.
Veröffentlicht: (2025)

The Complexity of Finding Missing Answer Repairs
von: Comer, Jesse, et al.
Veröffentlicht: (2026)

Characterizing and Testing Principal Minor Equivalence of Matrices
von: Chatterjee, Abhranil, et al.
Veröffentlicht: (2024)

Complexity of Constructing Minimal Faithful Permutation Representations for Fitting-free Groups
von: Levet, Michael, et al.
Veröffentlicht: (2025)

Second-Order Parameterizations for the Complexity Theory of Integrable Functions
von: Bacho, Aras, et al.
Veröffentlicht: (2025)

Computational Complexity of Finding Subgroups of a Given Order
von: Lakshmanan, K.
Veröffentlicht: (2025)

The Zeta ($ζ$) Notation for Complex Asymptotes
von: Dutta, Anurag, et al.
Veröffentlicht: (2023)

The Complexity of Finding and Counting Subtournaments
von: Döring, Simon, et al.
Veröffentlicht: (2025)

On the Complexity of the Skolem Problem at Low Orders
von: Bacik, Piotr, et al.
Veröffentlicht: (2025)

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

On the Complexity of p-Order Cone Programs
von: Blanco, Víctor, et al.
Veröffentlicht: (2025)

Learning Read-Once Determinants and the Principal Minor Assignment Problem
von: Aravind, Abhiram, et al.
Veröffentlicht: (2026)

The Complexity and Expressive Power of Second-Order Extended Logic
von: Feng, Shiguang, et al.
Veröffentlicht: (2022)

The Complexity of Symmetric Bimatrix Games with Common Payoffs
von: Ghosh, Abheek, et al.
Veröffentlicht: (2024)

The Structural Complexity Landscape of Finding Balance-Fair Shortest Paths
von: Bentert, Matthias, et al.
Veröffentlicht: (2024)

Space Complexity Dichotomies for Subgraph Finding Problems in the Streaming Model
von: Shih, Yu-Sheng, et al.
Veröffentlicht: (2026)

The Complexity of Finding Local Optima in Contrastive Learning
von: Yan, Jingming, et al.
Veröffentlicht: (2025)

Complexity of Finding and Enumerating Interconnection Trees
von: Demange, Noé, et al.
Veröffentlicht: (2026)

The Adaptive Complexity of Finding a Stationary Point
von: Zhou, Huanjian, et al.
Veröffentlicht: (2025)

The Randomized Query Complexity of Finding a Tarski Fixed Point on the Boolean Hypercube
von: Brânzei, Simina, et al.
Veröffentlicht: (2024)

Feasibly Constructive Proof of Schwartz-Zippel Lemma and the Complexity of Finding Hitting Sets
von: Atserias, Albert, et al.
Veröffentlicht: (2024)

Fixed-parameter debordering of Waring rank
von: Dutta, Pranjal, et al.
Veröffentlicht: (2024)

On the Hardness of Finding Temporally Connected Subgraphs of Any Size
von: Casteigts, Arnaud, et al.
Veröffentlicht: (2026)

The Computational Complexity of Finding Stationary Points in Non-Convex Optimization
von: Hollender, Alexandros, et al.
Veröffentlicht: (2023)

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

Order Retrieval in Compact Storage Systems
von: Fliedner, Malte, et al.
Veröffentlicht: (2025)