Imagen de Portada

Explicit Commutative ROABPs from Partial Derivatives

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Bhargava, Vishwas, Tengse, Anamay
Formato:	Preprint
Publicado:	2024
Materias:	Computational Complexity F.1.3; I.1.1
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Near-Optimal Bootstrapping of Hitting Sets for Algebraic Models
por: Kumar, Mrinal, et al.
Publicado: (2018)

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

Catalytic Computing and Register Programs Beyond Log-Depth
por: Alekseev, Yaroslav, et al.
Publicado: (2025)

A point to set principle for finite-state dimension
por: Mayordomo, Elvira
Publicado: (2022)

Reachability with Restricted Reactions in Inhibitory Chemical Reaction Networks
por: Bajaj, Divya, et al.
Publicado: (2026)

Graph Neural Networks and Arithmetic Circuits
por: Barlag, Timon, et al.
Publicado: (2024)

Average Attention Transformers and Arithmetic Circuits
por: Ehrmuth, Lena, et al.
Publicado: (2026)

Recurrent Graph Neural Networks and Arithmetic Circuits
por: Barlag, Timon, et al.
Publicado: (2026)

Imperative process algebra and models of computation
por: Middelburg, C. A.
Publicado: (2022)

On the Counting Complexity of the Skolem Problem
por: Jindal, Gorav, et al.
Publicado: (2024)

On the Complexity of the Conditional Independence Implication Problem With Bounded Cardinalities
por: Makowski, Michał
Publicado: (2024)

Problems from Optimization and Computational Algebra Equivalent to Hilbert's Nullstellensatz
por: Bläser, Markus, et al.
Publicado: (2025)

Tight bounds on depth-2 QAC-circuits computing parity
por: Fenner, Stephen, et al.
Publicado: (2025)

Clique Is Hard on Average for Sherali-Adams with Bounded Coefficients
por: de Rezende, Susanna F., et al.
Publicado: (2024)

Supercritical Tradeoffs for Monotone Circuits
por: Göös, Mika, et al.
Publicado: (2024)

Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz
por: Conneryd, Jonas, et al.
Publicado: (2025)

On bounded depth proofs for Tseitin formulas on the grid; revisited
por: Håstad, Johan, et al.
Publicado: (2022)

Superpolynomial Length Lower Bounds for Tree-Like Semantic Proof Systems with Bounded Line Size
por: de Rezende, Susanna F., et al.
Publicado: (2026)

Transitions in Dynamic Point Labeling
por: Depian, Thomas, et al.
Publicado: (2022)

Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs
por: de Rezende, Susanna F., et al.
Publicado: (2019)

Stochastic well-structured transition systems
por: Aspnes, James
Publicado: (2025)

L is different from NP
por: Montoya, J. Andres
Publicado: (2024)

The Serial Scaling Hypothesis
por: Liu, Yuxi, et al.
Publicado: (2025)

Functional Closure Properties of Finite $\mathbb{N}$-weighted Automata
por: Dörfler, Julian, et al.
Publicado: (2024)

Regular Model Checking for Systems with Effectively Regular Reachability Relation
por: Esparza, Javier, et al.
Publicado: (2025)

Search versus Search for Collapsing Electoral Control Types
por: Carleton, Benjamin, et al.
Publicado: (2022)

Anyone but Him: The Complexity of Precluding an Alternative
por: Hemaspaandra, Edith, et al.
Publicado: (2005)

Hausdorff Reductions and the Exponential Hierarchies
por: Malizia, Enrico
Publicado: (2024)

Separation Results for Constant-Depth and Multilinear Ideal Proof Systems
por: Behera, Amik Raj, et al.
Publicado: (2026)

Completing the Complexity Classification of 2-Solo Chess: Knights and Kings are Hard
por: Kühn, Kolja, et al.
Publicado: (2026)

Gaps, Ambiguity, and Establishing Complexity-Class Containments via Iterative Constant-Setting
por: Hemaspaandra, Lane A., et al.
Publicado: (2021)

Disjunctive Complexity
por: Ivanov, Nikita, et al.
Publicado: (2025)

Understanding Robust Catalytic Computing
por: Koucký, Michal, et al.
Publicado: (2026)

Shifted Partial Derivative Polynomial Rank and Codimension
por: Edwards, Darren J.
Publicado: (2025)

Explicit separations between randomized and deterministic Number-on-Forehead communication
por: Kelley, Zander, et al.
Publicado: (2023)

$\rm P$ has polynomial-time finite-state verifiers
por: Gezer, M. Utkan, et al.
Publicado: (2023)

Complexity Classes Arising from Circuits over Finite Algebraic Structures
por: Kawałek, Piotr, et al.
Publicado: (2026)

The Bit Complexity of Dynamic Algebraic Formulas and their Determinants
por: Anand, Emile, et al.
Publicado: (2024)

Towards New Characterizations of Small Circuit Classes via Discrete Ordinary Differential Equations
por: Antonelli, Melissa, et al.
Publicado: (2025)

Structure of sparse Boolean functions over Abelian groups, and its application to testing
por: Chakraborty, Sourav, et al.
Publicado: (2024)