Cover Image

Partial Minimum Branching Program Size Problem is ETH-hard

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Glinskih, Ludmila, Riazanov, Artur
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Resolution Over Linear Equations: Combinatorial Games for Tree-like Size and Space
by: Gryaznov, Svyatoslav, et al.
Published: (2024)

Better Boosting of Communication Oracles, or Not
by: Harms, Nathaniel, et al.
Published: (2024)

Equality is Far Weaker than Constant-Cost Communication
by: Göös, Mika, et al.
Published: (2025)

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

Searching for Falsified Clause in Random (log n)-CNFs is Hard for Randomized Communication
by: Riazanov, Artur, et al.
Published: (2025)

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

Pseudodeterministic Communication Complexity
by: Göös, Mika, et al.
Published: (2025)

Spiky Rank and Its Applications to Rigidity and Circuits
by: Hambardzumyan, Lianna, et al.
Published: (2026)

Improved Lower Bounds for Approximating Parameterized Nearest Codeword and Related Problems under ETH
by: Li, Shuangle, et al.
Published: (2024)

Average-Case Hardness of Binary-Encoded Clique in Proof and Communication Complexity
by: de Rezende, Susanna F., et al.
Published: (2026)

Sampling Permutations with Cell Probes is Hard
by: Alekseev, Yaroslav, et al.
Published: (2025)

Tight Lower Bound for Approximating Parametrized Maximum Likelihood Decoding under ETH
by: Gupta, Rishav, et al.
Published: (2026)

Treedepth Inapproximability and Exponential ETH Lower Bound
by: Bonnet, Édouard, et al.
Published: (2025)

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

Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH
by: Guruswami, Venkatesan, et al.
Published: (2024)

Proving Unsatisfiability with Hitting Formulas
by: Filmus, Yuval, et al.
Published: (2023)

King Chasing Problem in Chinese Chess is NP-hard
by: Li, Chao, et al.
Published: (2026)

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

Parameterized Inapproximability of the Minimum Distance Problem over all Fields and the Shortest Vector Problem in all $\ell_p$ Norms
by: Bennett, Huck, et al.
Published: (2022)

Retracted: Branch-and-Reduction Algorithm for Indefinite Quadratic Programming Problem
by: Complexity
Published: (2024)

Mind the Gap? Not for SVP Hardness under ETH!
by: Aggarwal, Divesh, et al.
Published: (2025)

A Gap-ETH-Tight Approximation Scheme for Euclidean TSP
by: Kisfaludi-Bak, Sándor, et al.
Published: (2020)

Pseudodeterministic Algorithms for Minimum Cut Problems
by: Agarwala, Aryan, et al.
Published: (2025)

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

Phase Transitions in Decision Problems Over Odd-Sized Alphabets
by: Jackson, Andrew
Published: (2025)

Improved Hardness of BDD and SVP Under Gap-(S)ETH
by: Bennett, Huck, et al.
Published: (2021)

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

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

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

Injective hardness condition for PCSPs
by: Banakh, Demian, et al.
Published: (2024)

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

Communication Complexity is NP-hard
by: Hirahara, Shuichi, et al.
Published: (2025)

Maximizing Minimum Cycle Bases Intersection
by: Watel, Dimitri, et al.
Published: (2024)

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

Coordinating "7 Billion Humans" is hard
by: Panconesi, Alessandro, et al.
Published: (2024)

Improved Hardness and Approximations for Cardinality-Based Minimum $s$-$t$ Cuts Problems in Hypergraphs
by: Adriaens, Florian, et al.
Published: (2024)

Minimum cost flow decomposition on arc-coloured networks
by: Neto, Claudio Carvalho, et al.
Published: (2025)

On the hardness of finding normal surfaces
by: Burton, Benjamin A., et al.
Published: (2019)

A SAT Solver and Computer Algebra Attack on the Minimum Kochen-Specker Problem
by: Li, Zhengyu, et al.
Published: (2023)

PCP-free APX-Hardness of Nearest Codeword and Minimum Distance
by: Bhattiprolu, Vijay, et al.
Published: (2025)