Cover Image

Monotone Bounded-Depth Complexity of Homomorphism Polynomials

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bhargav, C. S., Chen, Shiteng, Curticapean, Radu, Dwivedi, Prateek
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity Discrete Mathematics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

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

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

A Distance Amplification Lemma for Monotonicity
by: Minzer, Dor
Published: (2025)

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

Property Testing in Bounded Degree Hypergraphs
by: Aaronson, Hugo, et al.
Published: (2025)

Testing Isomorphism of Graphs in Polynomial Time
by: Xue, Rui
Published: (2023)

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

A Courcelle-Type Metatheorem for Rank-Bounded Unconstrained Binary Optimization
by: Harary, Marc
Published: (2025)

Parameterized Complexity of Segment Routing
by: Bazgan, Cristina, et al.
Published: (2025)

On the Incompressibility of Truth With Application to Circuit Complexity
by: Tonon, Luke
Published: (2025)

The Parameterized Complexity of Terminal Monitoring Set
by: Aravind, N. R., et al.
Published: (2024)

Graph Homomorphisms and Universal Algebra
by: Bodirsky, Manuel
Published: (2026)

A Simple Sub-Polynomial Degree Coboundary Expander
by: Hopkins, Max, et al.
Published: (2026)

Complexity of the Freezing Majority Rule with L-shaped Neighborhoods
by: Concha-Vega, Pablo, et al.
Published: (2025)

Complexity of Boolean automata networks under block-parallel update modes
by: Perrot, Kévin, et al.
Published: (2024)

Chernoff Bounds and Reverse Hypercontractivity on HDX
by: Dikstein, Yotam, et al.
Published: (2024)

Bounded degree QBF and positional games
by: Oijid, Nacim
Published: (2024)

An Algorithmic Meta Theorem for Homomorphism Indistinguishability
by: Seppelt, Tim
Published: (2024)

Polynomial-Time Pseudodeterministic Construction of Primes
by: Chen, Lijie, et al.
Published: (2023)

Logical Equivalences, Homomorphism Indistinguishability, and Forbidden Minors
by: Seppelt, Tim
Published: (2023)

Matching Cut and Variants on Bipartite Graphs of Bounded Radius and Diameter
by: Lucke, Felicia
Published: (2025)

Structural Origins of Cubic Complexity in Pebble Motion
by: Nakamigawa, Tomoki, et al.
Published: (2025)

Computational Complexity of Covering Two-vertex Multigraphs with Semi-edges
by: Bok, Jan, et al.
Published: (2021)

Complexity results for a cops and robber game on directed graphs
by: Ben-Ameur, Walid, et al.
Published: (2024)

Complexity of approximate conflict-free, linearly-ordered, and nonmonochromatic hypergraph colourings
by: Nakajima, Tamio-Vesa, et al.
Published: (2025)

Complexity and algorithms for matching cut problems in graphs without long induced paths and cycles
by: Le, Hoang-Oanh, et al.
Published: (2023)

On the Complexity of Recoverable Robust Optimization in the Polynomial Hierarchy
by: Grüne, Christoph, et al.
Published: (2024)

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

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

Is Graph Local Complementation Inherently Sequential?
by: Concha-Vega, Pablo
Published: (2025)

How to Reconfigure Your Alliances
by: Fernau, Henning, et al.
Published: (2025)

List Decoding Quotient Reed-Muller Codes
by: Gotlib, Omri, et al.
Published: (2025)

On the complexity of freezing automata networks of bounded pathwidth
by: Goles, Eric, et al.
Published: (2025)

Enumeration With Nice Roman Domination Properties
by: Mann, Kevin
Published: (2025)

The PPP-completeness of the Ward-Szabo theorem
by: Ishizuka, Takashi
Published: (2025)

Maximum Reachability Orientation of Mixed Graphs
by: Hörsch, Florian
Published: (2025)

On the enumeration of Tarski fixed points
by: Müller, Julian
Published: (2023)

Edge-Disjoint Paths in Eulerian Digraphs
by: Cavallaro, Dario, et al.
Published: (2024)

Relations between monotone complexity measures based on decision tree complexity
by: Byramji, Farzan, et al.
Published: (2024)