Cover Image

Lower Bounds for Set-Multilinear Branching Programs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chatterjee, Prerona, Kush, Deepanshu, Saraf, Shubhangi, Shpilka, Amir
Format:	Preprint
Published:	2023
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

Lower Bounds from Succinct Hitting Sets
by: Chatterjee, Prerona, et al.
Published: (2023)

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

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

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

Improved Debordering of Waring Rank
by: Shpilka, Amir
Published: (2025)

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

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

Polynomial-Time PIT from (Almost) Necessary Assumptions
by: Andrews, Robert, et al.
Published: (2025)

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

Simple Constructions of Unique Neighbor Expanders from Error-correcting Codes
by: Kopparty, Swastik, et al.
Published: (2023)

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

Constant-depth circuits for polynomial GCD over any characteristic
by: Bhattacharjee, Somnath, et al.
Published: (2025)

Closure under factorization from a result of Furstenberg
by: Bhattacharjee, Somnath, et al.
Published: (2025)

Tight Lower Bounds for Block-Structured Integer Programs
by: Hunkenschröder, Christoph, et al.
Published: (2024)

Deterministic factorization of constant-depth algebraic circuits in subexponential time
by: Bhattacharjee, Somnath, et al.
Published: (2025)

Local Enumeration and Majority Lower Bounds
by: Gurumukhani, Mohit, et al.
Published: (2024)

Lower Bounds for Approximate Sign Rank
by: Bindua, Riju, et al.
Published: (2026)

Spectral Lower Bounds for Local Search
by: Brânzei, Simina, et al.
Published: (2024)

Exponential Lower Bounds for Smooth 3-LCCs and Sharp Bounds for Designs
by: Kothari, Pravesh K., et al.
Published: (2024)

A Quadratic Lower Bound for Noncommutative Circuits
by: Shastri, Pratik
Published: (2026)

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

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

Convergent Gate Elimination and Constructive Circuit Lower Bounds
by: Carmosino, Marco, et al.
Published: (2026)

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

Lower Bounds for Subset Sum in Resolution with Modular Counting
by: Part, Fedor
Published: (2022)

Lower Bounds for Conjunctive Query Evaluation
by: Mengel, Stefan
Published: (2025)

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

A Lower Bound on Conservative Elementary Object Systems Coverability
by: Di Cosmo, Francesco, et al.
Published: (2025)

Lower Bounds against the Ideal Proof System in Finite Fields
by: Elbaz, Tal, et al.
Published: (2025)

Spectral Certificates and Sum-of-Squares Lower Bounds for Semirandom Hamiltonians
by: Kocurek, Nicholas
Published: (2025)

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

Query Lower Bounds for Correlation Clustering under Memory Constraints
by: Garg, Sumegha, et al.
Published: (2026)

Upper and Lower Bounds on $T_1$ and $T_2$ Decision Tree Model
by: Alhamdan, Yousef M.
Published: (2025)

Separations above TFNP from Sherali-Adams Lower Bounds
by: Fleming, Noah, et al.
Published: (2026)

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

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

Low Rank Matrix Rigidity: Tight Lower Bounds and Hardness Amplification
by: Alman, Josh, et al.
Published: (2025)

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

Lower Bounds on Cardinality of Reducts for Decision Tables from Closed Classes
by: Ostonov, Azimkhon, et al.
Published: (2024)