Copertina

An Unconditional Barrier for Proving Multilinear Algebraic Branching Program Lower Bounds

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autore principale:	Kush, Deepanshu
Natura:	Preprint
Pubblicazione:	2026
Soggetti:	Computational Complexity Combinatorics Probability
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

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

Noise Sensitivity and Learning Lower Bounds for Hierarchical Functions
di: Li, Rupert, et al.
Pubblicazione: (2025)

Permanents of random matrices over finite fields
di: Hunter, Zach, et al.
Pubblicazione: (2026)

Optimal Union Probability Interval Is NP-Hard
di: Kaski, Petteri, et al.
Pubblicazione: (2026)

On hardness of computing analytic Brouwer degree
di: Chakraborty, Somnath
Pubblicazione: (2023)

Separating complexity classes of LCL problems on grids
di: Berlow, Katalin, et al.
Pubblicazione: (2025)

Improved Lower Bounds for all Odd-Query Locally Decodable Codes
di: Basu, Arpon, et al.
Pubblicazione: (2024)

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

Universality for roots of derivatives of entire functions via finite free probability
di: Campbell, Andrew, et al.
Pubblicazione: (2024)

Polynomial-time sampling despite disorder chaos
di: Ma, Eric, et al.
Pubblicazione: (2025)

Computational hardness of detecting graph lifts and certifying lift-monotone properties of random regular graphs
di: Kunisky, Dmitriy, et al.
Pubblicazione: (2024)

Some easy optimization problems have the overlap-gap property
di: Li, Shuangping, et al.
Pubblicazione: (2024)

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

Upper Bounds for Symmetric Approximate Bounded Indistinguishability
di: Williamson, Christopher
Pubblicazione: (2026)

Systems of Discrete Differential Equations, Constructive Algebraicity of the Solutions
di: Notarantonio, Hadrien, et al.
Pubblicazione: (2023)

AC^0[p]-Frege Cannot Efficiently Prove that Constant-Depth Algebraic Circuit Lower Bounds are Hard
di: Lu, Jiaqi, et al.
Pubblicazione: (2025)

Sharp Thresholds Imply Circuit Lower Bounds: from random 2-SAT to Planted Clique
di: Gamarnik, David, et al.
Pubblicazione: (2023)

Infinite circle patterns in the Weil-Petersson class
di: Lam, Wai Yeung
Pubblicazione: (2026)

Decay of correlations and zeros for the hard-core model
di: Peters, Han, et al.
Pubblicazione: (2026)

The stochastic block model has the overlap graph property for modularity
di: Bhamidi, Shankar, et al.
Pubblicazione: (2026)

Optimal Hardness of Online Algorithms for Large Common Induced Subgraphs
di: Gamarnik, David, et al.
Pubblicazione: (2026)

Algorithmic Phase Transition for Large Independent Sets in Dense Hypergraphs
di: Dhawan, Abhishek, et al.
Pubblicazione: (2026)

Sharp Online Hardness for Large Balanced Independent Sets
di: Dhawan, Abhishek, et al.
Pubblicazione: (2025)

The Low-Degree Hardness of Finding Large Independent Sets in Sparse Random Hypergraphs
di: Dhawan, Abhishek, et al.
Pubblicazione: (2024)

Inference of rankings planted in random tournaments
di: Kunisky, Dmitriy, et al.
Pubblicazione: (2024)

Statistical inference of a ranked community in a directed graph
di: Kunisky, Dmitriy, et al.
Pubblicazione: (2024)

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

Reasonable Bounds for Combinatorial Lines of Length Three
di: Bhangale, Amey, et al.
Pubblicazione: (2024)

On Sampling Lower Bounds for Polynomials
di: Khodabandeh, Mohammad Mahdi, et al.
Pubblicazione: (2026)

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

Random infinite ideal angled graphs and ideal hyperbolic polyhedra
di: Ge, Huabin, et al.
Pubblicazione: (2026)

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

Bounded degree QBF and positional games
di: Oijid, Nacim
Pubblicazione: (2024)

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

Lower Bounds for the Probability of a Union via Chordal Graphs
di: Dohmen, Klaus
Pubblicazione: (2010)

Low Acceptance Agreement Tests via Bounded-Degree Symplectic HDXs
di: Dikstein, Yotam, et al.
Pubblicazione: (2024)

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

Fine-Grained Cryptanalysis: Tight Conditional Bounds for Dense k-SUM and k-XOR
di: Dinur, Itai, et al.
Pubblicazione: (2021)

Forest Covers and Bounded Forest Covers
di: Gaur, Daya Ram, et al.
Pubblicazione: (2024)

Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles
di: Alrabiah, Omar, et al.
Pubblicazione: (2024)