:: Library Catalog

Copertina

Salvato in:

Dettagli Bibliografici
Autori principali:	Nagy, Tomáš, Pinsker, Michael, Wrona, Michał
Natura:	Preprint
Pubblicazione:	2025
Soggetti:	Computational Complexity
Accesso online:	https://arxiv.org/abs/2502.02090
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

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

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

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

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

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

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

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

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

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

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

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

Low-Rank Tensor Decomposition over Finite Fields
di: Yang, Jason
Pubblicazione: (2024)

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

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

Algebraic Pseudorandomness in $VNC^0$
di: Andrews, Robert
Pubblicazione: (2025)

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

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

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

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

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

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

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

Algebraic Global Gadgetry for Surjective Constraint Satisfaction
di: Chen, Hubie
Pubblicazione: (2020)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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