Cover Image

VP, VNP and Algebraic Branching Programs over Min-Plus Semirings

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Komarath, Balagopal, Mittal, Harshil, Sarma, Jayalal
Format:	Preprint
Published:	2026
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

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

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

Range Avoidance in Boolean Circuits via Turan-type Bounds
by: Kuntewar, Neha, et al.
Published: (2025)

A Hierarchy of Tinhofer Graphs: Separations and Membership Testing
by: Bhattacharjee, Sutanay, et al.
Published: (2026)

If VNP is hard, then so are equations for it
by: Kumar, Mrinal, et al.
Published: (2020)

On Condensation of Block Sensitivity, Certificate Complexity and the $\mathsf{AND}$ (and $\mathsf{OR}$) Decision Tree Complexity
by: Nalli, Sai Soumya, et al.
Published: (2026)

Bounds for Hardness Condensation in the Query Model
by: Kayal, Chandrima, et al.
Published: (2026)

Almost-catalytic Computation
by: Bisoyi, Sagar, et al.
Published: (2024)

Multiquadratic Sum-of-Squares Lower Bounds Imply VNC$^1$ $\neq$ VNP
by: Rossman, Benjamin, et al.
Published: (2025)

Circuits and Formulas for Datalog over Semirings
by: Fan, Austen Z., et al.
Published: (2025)

New Perspectives on Semiring Applications to Dynamic Programming
by: Baril, Ambroise, et al.
Published: (2025)

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

An Unconditional Barrier for Proving Multilinear Algebraic Branching Program Lower Bounds
by: Kush, Deepanshu
Published: (2026)

Fagin's Theorem for Semiring Turing Machines
by: Badia, Guillermo, et al.
Published: (2025)

Logic and Computation through the Lens of Semirings
by: Barlag, Timon, et al.
Published: (2025)

Lower Bounds for Set-Multilinear Branching Programs
by: Chatterjee, Prerona, et al.
Published: (2023)

Partial Minimum Branching Program Size Problem is ETH-hard
by: Glinskih, Ludmila, et al.
Published: (2024)

Baby PIH: Parameterized Inapproximability of Min CSP
by: Guruswami, Venkatesan, et al.
Published: (2023)

On the Hierarchies for Deterministic, Nondeterministic and Probabilistic Ordered Read-k-times Branching Programs
by: Khadiev, Kamil
Published: (2016)

New Sufficient Algebraic Conditions for Local Consistency over Homogeneous Structures of Finite Duality
by: Nagy, Tomáš, et al.
Published: (2025)

Explicit Directional Affine Extractors and Improved Hardness for Linear Branching Programs
by: Li, Xin, et al.
Published: (2023)

Multiplayer Parallel Repetition Is the Same as High-Dimensional Extremal Combinatorics
by: Mittal, Kunal
Published: (2025)

A Lower Bound on the Constant in the Fourier Min-Entropy/Influence Conjecture
by: Biswas, Aniruddha, et al.
Published: (2022)

Biased Linearity Testing in the 1% Regime
by: Khot, Subhash, et al.
Published: (2025)

Quantum Query-Space Lower Bounds Using Branching Programs
by: Bera, Debajyoti, et al.
Published: (2024)

Algebraic Pseudorandomness in $VNC^0$
by: Andrews, Robert
Published: (2025)

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

MaxMin Separation Problems: FPT Algorithms for $st$-Separator and Odd Cycle Transversal
by: Gaikwad, Ajinkya, et al.
Published: (2025)

One-Way Functions and Polynomial Time Dimension
by: Nandakumar, Satyadev, et al.
Published: (2024)

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

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

On the Parameterized Complexity of Min-Sum-Radii
by: Kumar, Pankaj, et al.
Published: (2026)

Algebraic Global Gadgetry for Surjective Constraint Satisfaction
by: Chen, Hubie
Published: (2020)

The Complexity of Min-Max Optimization with Product Constraints
by: Bernasconi, Martino, et al.
Published: (2026)

Improved Parallel Repetition for GHZ-Supported Games via Spreadness
by: Liu, Yang P., et al.
Published: (2026)

Parameterized Max Min Feedback Vertex Set
by: Lampis, Michael, et al.
Published: (2023)

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

Improved Hardness Results for Min-Max Optimization with Coupled Constraints
by: Bernasconi, Martino, et al.
Published: (2024)

Weighted Pseudorandom Generators for Read-Once Branching Programs via Weighted Pseudorandom Reductions
by: Cheng, Kuan, et al.
Published: (2025)