Imagen de Portada

Tight Lower Bounds for Block-Structured Integer Programs

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Hunkenschröder, Christoph, Klein, Kim-Manuel, Koutecký, Martin, Lassota, Alexandra, Levin, Asaf
Formato:	Preprint
Publicado:	2024
Materias:	Computational Complexity
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Solving 4-Block Integer Linear Programs Faster Using Affine Decompositions of the Right-Hand Sides
por: Lassota, Alexandra, et al.
Publicado: (2026)

Parameterized Algorithms for Matching Integer Programs with Additional Rows and Columns
por: Lassota, Alexandra, et al.
Publicado: (2025)

(Near)-Optimal Algorithms for Sparse Separable Convex Integer Programs
por: Hunkenschröder, Christoph, et al.
Publicado: (2025)

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

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

Tight Streaming Lower Bounds for Deterministic Approximate Counting
por: Wang, Yichuan
Publicado: (2024)

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

Tight Quantum Depth Lower Bound for Solving Systems of Linear Equations
por: Wang, Qisheng, et al.
Publicado: (2024)

Tight Space Lower Bound for Pseudo-Deterministic Approximate Counting
por: Grossman, Ofer, et al.
Publicado: (2023)

A Tight Double-Exponentially Lower Bound for High-Multiplicity Bin Packing
por: Jansen, Klaus, et al.
Publicado: (2025)

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

When Majority Fails: Tight Bounds for Correlation Distillation Conjectures
por: Kamath, Pritish, et al.
Publicado: (2026)

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

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

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

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

Computational Complexity and Integer Programming Formulation of the Oredango Puzzle
por: Takahata, Takuma, et al.
Publicado: (2025)

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

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

Multiple Planted Structures Below $\sqrt{n}$: An SoS Integrality Gap and an SQ Lower Bound
por: Mosievskiy, Matvey, et al.
Publicado: (2026)

Tight Fine-Grained Bounds for Direct Access on Join Queries
por: Bringmann, Karl, et al.
Publicado: (2022)

A Quadratic Lower Bound for Noncommutative Circuits
por: Shastri, Pratik
Publicado: (2026)

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

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

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

Tight Bounds for Quantum Phase Estimation and Related Problems
por: Mande, Nikhil S., et al.
Publicado: (2023)

Quantum Lovász Local Lemma: Shearer's Bound is Tight
por: He, Kun, et al.
Publicado: (2018)

Treewidth Inapproximability and Tight ETH Lower Bound
por: Bonnet, Édouard
Publicado: (2024)

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

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

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

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

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

Lower Bounds for Conjunctive Query Evaluation
por: Mengel, Stefan
Publicado: (2025)

Efficient approximation schemes for scheduling on a stochastic number of machines
por: Epstein, Leah, et al.
Publicado: (2024)

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

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

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

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

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