Cover Image

Monotone Bounded Depth Formula Complexity of Graph Homomorphism Polynomials

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Komarath, Balagopal, Narayanan, Rohit
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

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

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

Sensitivity and Query Complexity under Uncertainty
by: Benson, Deepu, et al.
Published: (2025)

Hazard-free Decision Trees
by: Benson, Deepu, et al.
Published: (2025)

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

Optimal Monotone Depth-Three Circuit Lower Bounds for Majority
by: Gurumukhani, Mohit, et al.
Published: (2026)

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

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

The Fine-Grained Complexity of Graph Homomorphism Problems: Towards the Okrasa and Rzążewski Conjecture
by: Baril, Ambroise, et al.
Published: (2024)

On the Complexity of Hazard-Free Formulas
by: Arazi, Leah London, et al.
Published: (2024)

IPS Lower Bounds for Formulas and Sum of ROABPs
by: Chatterjee, Prerona, et al.
Published: (2025)

CLIQUE as an AND of Polynomial-Sized Monotone Constant-Depth Circuits
by: Bodnar, Levente
Published: (2024)

Complexity of Multiple-Hamiltonicity in Graphs of Bounded Degree
by: Liu, Brian, et al.
Published: (2024)

Monotone Circuit Complexity of Matching
by: Cavalar, Bruno, et al.
Published: (2025)

On Factorization of Sparse Polynomials of Bounded Individual Degree
by: Chuyoon, Aminadav, et al.
Published: (2026)

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

Planar Graph Homomorphisms: A Dichotomy and a Barrier from Quantum Groups
by: Cai, Jin-Yi, et al.
Published: (2026)

Lower Bounds for Bit Pigeonhole Principles in Bounded-Depth Resolution over Parities
by: Byramji, Farzan, et al.
Published: (2025)

Conditional Complexity Hardness: Monotone Circuit Size, Matrix Rigidity, and Tensor Rank
by: Chukhin, Nikolai, et al.
Published: (2024)

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

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

Bounded-Depth Frege Lower Bounds for Random 3-CNFs via Deterministic Restrictions
by: Gryaznov, Svyatoslav, et al.
Published: (2024)

Top-Down Lower Bounds for Depth-Four Circuits
by: Göös, Mika, et al.
Published: (2023)

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

Monotone Contractions
by: Batziou, Eleni, et al.
Published: (2024)

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

Parameterized Complexity Of Representing Models Of MSO Formulas
by: Kučera, Petr, et al.
Published: (2026)

Simple Norm Bounds for Polynomial Random Matrices via Decoupling
by: Tulsiani, Madhur, et al.
Published: (2024)

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

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

Tighter Bounds for the Randomized Polynomial-Time Simplex Algorithm for Linear Programming
by: Gibor, Daniel
Published: (2025)

Exponential Lower Bounds on the Size of ResLin Proofs of Nearly Quadratic Depth
by: Bhattacharya, Sreejata Kishor, et al.
Published: (2025)

Improved Bounds on the Space Complexity of Circuit Evaluation
by: Shalunov, Yakov
Published: (2025)

The Complexity of Logarithmic Space Bounded Counting Classes
by: Vijayaraghavan, T. C.
Published: (2025)

FormulaOne: Measuring the Depth of Algorithmic Reasoning Beyond Competitive Programming
by: Beniamini, Gal, et al.
Published: (2025)

A New Bound on Cofactors of Sparse Polynomials
by: Nahshon, Ido, et al.
Published: (2023)

Toward Better Depth Lower Bounds: Strong Composition of XOR and a Random Function
by: Chukhin, Nikolai, et al.
Published: (2024)

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

Oblivious Complexity Classes Revisited: Lower Bounds and Hierarchies
by: Gajulapalli, Karthik, et al.
Published: (2025)