:: Library Catalog

Imagen de Portada

Guardado en:

Detalles Bibliográficos
Autores principales:	Nagy, Tomáš, Pinsker, Michael, Wrona, Michał
Formato:	Preprint
Publicado:	2025
Materias:	Computational Complexity
Acceso en línea:	https://arxiv.org/abs/2502.02090
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

An order out of nowhere: a new algorithm for infinite-domain CSPs
por: Mottet, Antoine, et al.
Publicado: (2023)

Constraint Satisfaction Problems over Finitely Bounded Homogeneous Structures: a Dichotomy between FO and L-hard
por: Dorochko, Leonid, et al.
Publicado: (2026)

Collapsing the bounded width hierarchy for infinite-domain CSPs: when symmetries are enough
por: Mottet, Antoine, et al.
Publicado: (2021)

An algebraic proof of the dichotomy for graph orientation problems with forbidden tournaments
por: Feller, Roman, et al.
Publicado: (2024)

The complete classification for quantified equality constraints
por: Zhuk, Dmitriy, et al.
Publicado: (2021)

Strict width for Constraint Satisfaction Problems over homogeneous strucures of finite duality
por: Nagy, Tomáš, et al.
Publicado: (2024)

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

Homogeneous Algebraic Complexity Theory and Algebraic Formulas
por: Dutta, Pranjal, et al.
Publicado: (2023)

VP, VNP and Algebraic Branching Programs over Min-Plus Semirings
por: Komarath, Balagopal, et al.
Publicado: (2026)

Consistent Query Answering over SHACL Constraints
por: Ahmetaj, Shqiponja, et al.
Publicado: (2024)

Equations over Finite Monoids with Infinite Promises
por: Larrauri, Alberto, et al.
Publicado: (2025)

Low-Rank Tensor Decomposition over Finite Fields
por: Yang, Jason
Publicado: (2024)

On Sufficient Conditions for the class $S^*_\cosh\sqrt{z}$
por: Kumar, S. Sivaprasad, et al.
Publicado: (2023)

Optimal Inapproximability of Generalized Linear Equations over a Finite Group
por: Bhangale, Amey, et al.
Publicado: (2026)

Algebraic Pseudorandomness in $VNC^0$
por: Andrews, Robert
Publicado: (2025)

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

The Algebraic Cost of a Boolean Sum
por: Orzel, Ian, et al.
Publicado: (2025)

Symmetric Algebraic Circuits and Homomorphism Polynomials
por: Dawar, Anuj, et al.
Publicado: (2025)

Local Correction of Linear Functions over the Boolean Cube
por: Amireddy, Prashanth, et al.
Publicado: (2024)

Optimal Inapproximability of Promise Equations over Finite Groups
por: Butti, Silvia, et al.
Publicado: (2024)

On the Complexity of Pure-State Consistency of Local Density Matrices
por: Kamminga, Jonas, et al.
Publicado: (2024)

Query complexity of Boolean functions on the middle slice of the cube
por: Gerbner, Dániel, et al.
Publicado: (2023)

Algebraic Global Gadgetry for Surjective Constraint Satisfaction
por: Chen, Hubie
Publicado: (2020)

Poincaré Duality and Multiplicative Structures on Quantum Codes
por: Li, Yiming, et al.
Publicado: (2025)

Precoloring extension with demands on paths
por: Das, Arun Kumar, et al.
Publicado: (2025)

New results in canonical polyadic decomposition over finite fields
por: Yang, Jason
Publicado: (2025)

Necessary and Sufficient Oracles: Toward a Computational Taxonomy For Reinforcement Learning
por: Rohatgi, Dhruv, et al.
Publicado: (2025)

Complex Boolean Turing Machines: An Algebraic Semantic Framework for Computational Complexity
por: Zheng, Bojin, et al.
Publicado: (2026)

Systems of Discrete Differential Equations, Constructive Algebraicity of the Solutions
por: Notarantonio, Hadrien, et al.
Publicado: (2023)

Dual-Tape Perspective and Generator Independence: The Algebraic Foundation of Real Boolean Turing Machines
por: Zheng, Jingwen, et al.
Publicado: (2026)

Simple Linear Loops: Algebraic Invariants and Applications
por: Manssour, Rida Ait El, et al.
Publicado: (2024)

Automated Lower Bounds for Small Matrix Multiplication Complexity over Finite Fields
por: Wang, Chengu
Publicado: (2026)

Local Enumeration and Majority Lower Bounds
por: Gurumukhani, Mohit, et al.
Publicado: (2024)

Attacking the Polynomials in the Maze of Finite Fields problem
por: Barbero, Àngela, et al.
Publicado: (2026)

AC^0[p]-Frege Cannot Efficiently Prove that Constant-Depth Algebraic Circuit Lower Bounds are Hard
por: Lu, Jiaqi, et al.
Publicado: (2025)

Information-Based Complexity vs Computational Complexity in Phaseless Polynomial Interpolation
por: Przybyłek, Michał R., et al.
Publicado: (2026)

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

On Closure Properties of Read-Once Oblivious Algebraic Branching Programs
por: Armand, Jules, et al.
Publicado: (2025)

Unifying the Three Algebraic Approaches to the CSP via Minimal Taylor Algebras
por: Barto, Libor, et al.
Publicado: (2021)

List Locally Surjective Homomorphisms in Hereditary Graph Classes
por: Dvořák, Pavel, et al.
Publicado: (2022)