Copertina

Lower Bounds in Algebraic Complexity via Symmetry and Homomorphism Polynomials

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Dwivedi, Prateek, Pago, Benedikt, Seppelt, Tim
Natura:	Preprint
Pubblicazione:	2026
Soggetti:	Computational Complexity Discrete Mathematics Logic in Computer Science Group Theory
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

An Algorithmic Meta Theorem for Homomorphism Indistinguishability
di: Seppelt, Tim
Pubblicazione: (2024)

Logical Equivalences, Homomorphism Indistinguishability, and Forbidden Minors
di: Seppelt, Tim
Pubblicazione: (2023)

Homomorphism Indistinguishability, Multiplicity Automata Equivalence, and Polynomial Identity Testing
di: Černý, Marek, et al.
Pubblicazione: (2025)

Lasserre Hierarchy for Graph Isomorphism and Homomorphism Indistinguishability
di: Roberson, David E., et al.
Pubblicazione: (2023)

Monotone Bounded-Depth Complexity of Homomorphism Polynomials
di: Bhargav, C. S., et al.
Pubblicazione: (2025)

Distinguishing Graphs by Counting Homomorphisms from Sparse Graphs
di: Neuen, Daniel, et al.
Pubblicazione: (2026)

Optimal Lower Bounds for Symmetric Modular Circuits
di: Pago, Benedikt
Pubblicazione: (2026)

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

The Rise of Plurimorphisms: Algebraic Approach to Approximation
di: Barto, Libor, et al.
Pubblicazione: (2024)

Derandomized Non-Abelian Homomorphism Testing in Low Soundness Regime
di: Mittal, Tushant, et al.
Pubblicazione: (2024)

Complexity lower bounds for succinct binary structures of bounded clique-width with restrictions
di: Geniet, Colin, et al.
Pubblicazione: (2026)

Permutation clones that preserve relations
di: Boykett, Tim
Pubblicazione: (2024)

Graph Homomorphisms and Universal Algebra
di: Bodirsky, Manuel
Pubblicazione: (2026)

The Identity Problem in the special affine group of $\mathbb{Z}^2$
di: Dong, Ruiwen
Pubblicazione: (2023)

Ordering groups and the Identity Problem
di: Bodart, Corentin, et al.
Pubblicazione: (2024)

The Unit Gap: How Sharing Works in Boolean Circuits
di: Krinkin, Kirill
Pubblicazione: (2026)

Small unsatisfiable $k$-CNFs with bounded literal occurrence
di: Zhang, Tianwei, et al.
Pubblicazione: (2024)

Rice-like complexity lower bounds for Boolean and uniform automata networks
di: Goubault-Larrecq, Aliénor, et al.
Pubblicazione: (2024)

Lower Bounds for Symmetric Circuits for the Determinant
di: Dawar, Anuj, et al.
Pubblicazione: (2021)

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

Going deep and going wide: Counting logic and homomorphism indistinguishability over graphs of bounded treedepth and treewidth
di: Adler, Isolde, et al.
Pubblicazione: (2025)

Restricted CSPs and F-free Digraph Algorithmics
di: Guzmán-Pro, Santiago, et al.
Pubblicazione: (2025)

The Richness of CSP Non-redundancy
di: Brakensiek, Joshua, et al.
Pubblicazione: (2025)

A Classification of Long-Refinement Graphs for Colour Refinement
di: Kiefer, Sandra, et al.
Pubblicazione: (2025)

CMSO-transducing tree-like graph decompositions
di: Campbell, Rutger, et al.
Pubblicazione: (2024)

Weighted basic parallel processes and combinatorial enumeration
di: Clemente, Lorenzo
Pubblicazione: (2024)

Lower Bounds on Inverse Cellular Automata via Proof Complexity
di: Kapytka, Maryia
Pubblicazione: (2026)

Computability of extender sets in multidimensional subshifts: asymptotic growths, dynamical constraints
di: Callard, Antonin, et al.
Pubblicazione: (2024)

Nested Sequents for Intuitionistic Grammar Logics via Structural Refinement
di: Lyon, Tim S.
Pubblicazione: (2022)

Super-linear Lower Bounds for CSP Non-Redundancy via Shrinking Instances
di: Brakensiek, Joshua, et al.
Pubblicazione: (2026)

On Numbers of Simplicial Walks and Equivalent Canonizations for Graph Recognition
di: Černý, Marek
Pubblicazione: (2026)

Smaller Circuits for Bit Addition
di: Goncharov, Mikhail, et al.
Pubblicazione: (2025)

Arity hierarchies for quantifiers closed under partial polymorphisms
di: Dawar, Anuj, et al.
Pubblicazione: (2025)

Complexity Aspects of Homomorphisms of Ordered Graphs
di: Čertík, Michal, et al.
Pubblicazione: (2025)

Explicit Lossless Vertex Expanders
di: Hsieh, Jun-Ting, et al.
Pubblicazione: (2025)

On the Complexity of Problems on Graphs Defined on Groups
di: Das, Bireswar, et al.
Pubblicazione: (2025)

Symmetric Proofs in the Ideal Proof System
di: Dawar, Anuj, et al.
Pubblicazione: (2025)

Lacon-, Shrub- and Parity-Decompositions: Characterizing Transductions of Bounded Expansion Classes
di: Dreier, Jan
Pubblicazione: (2021)

Forbidden Induced Subgraphs for Bounded Shrub-Depth and the Expressive Power of MSO
di: Mählmann, Nikolas
Pubblicazione: (2025)

Reconfiguring Graph Homomorphisms on the Sphere
di: Lee, Jae-Baek, et al.
Pubblicazione: (2018)