Imagen de Portada

Symmetric Algebraic Circuits and Homomorphism Polynomials

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Dawar, Anuj, Pago, Benedikt, Seppelt, Tim
Formato:	Preprint
Publicado:	2025
Materias:	Computational Complexity
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Lower Bounds in Algebraic Complexity via Symmetry and Homomorphism Polynomials
por: Dwivedi, Prateek, et al.
Publicado: (2026)

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

Optimal Lower Bounds for Symmetric Modular Circuits
por: Pago, Benedikt
Publicado: (2026)

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

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

An Algorithmic Meta Theorem for Homomorphism Indistinguishability
por: Seppelt, Tim
Publicado: (2024)

Symmetric Arithmetic Circuits
por: Dawar, Anuj, et al.
Publicado: (2020)

Logical Equivalences, Homomorphism Indistinguishability, and Forbidden Minors
por: Seppelt, Tim
Publicado: (2023)

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

Limitations of Affine Integer Relaxations for Solving Constraint Satisfaction Problems
por: Lichter, Moritz, et al.
Publicado: (2024)

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

Preservation Theorems in Semiring Semantics
por: Brinke, Sophie, et al.
Publicado: (2026)

Monotone Bounded Depth Formula Complexity of Graph Homomorphism Polynomials
por: Komarath, Balagopal, et al.
Publicado: (2025)

Undefinability of Approximation of 2-to-2 Games
por: Dawar, Anuj, et al.
Publicado: (2025)

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

Symmetric Distributions from Shallow Circuits
por: Kane, Daniel M., et al.
Publicado: (2025)

Computing the Elementary Symmetric Polynomials in Positive Characteristics
por: Orzel, Ian
Publicado: (2025)

Beyond Bilinear Complexity: What Works and What Breaks with Many Modes?
por: Brand, Cornelius, et al.
Publicado: (2026)

Exponential-Size Circuit Complexity is Comeager in Symmetric Exponential Time
por: Hitchcock, John M.
Publicado: (2026)

Polynomial Lower Bounds for Arithmetic Circuits over Non-Commutative Rings
por: Raz, Ran
Publicado: (2026)

Polynomial Identity Testing and Reconstruction for Depth-4 Powering Circuits of High Degree
por: Shpilka, Amir, et al.
Publicado: (2026)

Symmetric Exponential Time Requires Near-Maximum Circuit Size: Simplified, Truly Uniform
por: Li, Zeyong
Publicado: (2023)

Simple Circuit Extensions for XOR in PTIME
por: Carmosino, Marco, et al.
Publicado: (2025)

Convergent Gate Elimination and Constructive Circuit Lower Bounds
por: Carmosino, Marco, 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)

Homomorphism Counts to Trees
por: Dawar, Anuj
Publicado: (2024)

Polynomial-Time Classical Simulation of Noisy IQP Circuits with Constant Depth
por: Rajakumar, Joel, et al.
Publicado: (2024)

Polynomial-Time Classical Simulation of Noisy Quantum Circuits with Naturally Fault-Tolerant Gates
por: Nelson, Jon, et al.
Publicado: (2024)

Planar Graph Homomorphisms: A Dichotomy and a Barrier from Quantum Groups
por: Cai, Jin-Yi, 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)

A New Reduction Method from Multivariate Polynomials to Univariate Polynomials
por: Wang, Cancan, et al.
Publicado: (2024)

Graph Homomorphism, Monotone Classes and Bounded Pathwidth
por: Eagling-Vose, Tala, et al.
Publicado: (2024)

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

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

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

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

Locally Sampleable Uniform Symmetric Distributions
por: Kane, Daniel M., et al.
Publicado: (2024)

Choiceless Computation and Symmetry: Limitations of Definability
por: Pago, Benedikt
Publicado: (2024)

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