Cover Image

Depth lower bounds in Stabbing Planes for combinatorial principles

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Dantchev, Stefan, Galesi, Nicola, Ghani, Abdul, Martin, Barnaby
Format:	Preprint
Published:	2021
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Exponential lower bound via exponential sums
by: Bhattacharjee, Somnath, et al.
Published: (2026)

Simple general magnification of circuit lower bounds
by: Atserias, Albert, et al.
Published: (2025)

A note on Jerabek's paper "A simplified lower bound for implicational logic"
by: Gordeev, Lev, et al.
Published: (2026)

Circuit metaconstruction in logspace for Rice-like complexity lower bounds in ANs and SGRs
by: Goubault-Larrecq, Aliénor, et al.
Published: (2025)

Quantum circuit lower bounds in the magic hierarchy
by: Parham, Natalie
Published: (2025)

The complete classification for quantified equality constraints
by: Zhuk, Dmitriy, et al.
Published: (2021)

On the consistency of stronger lower bounds for NEXP
by: Thapen, Neil
Published: (2025)

A nearly-$4\log n$ depth lower bound for formulas with restriction on top
by: Wu, Hao
Published: (2024)

Complexity Framework For Forbidden Subgraphs V: Beyond Simple Graphs
by: Eagling-Vose, Tala, et al.
Published: (2025)

Restricted CSPs and F-free Digraph Algorithmics
by: Guzmán-Pro, Santiago, et al.
Published: (2025)

Graph Homomorphism, Monotone Classes and Bounded Pathwidth
by: Eagling-Vose, Tala, et al.
Published: (2024)

Computational lower bounds for multi-frequency group synchronization
by: Kireeva, Anastasia, et al.
Published: (2024)

Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds
by: Agarwal, Avantika, et al.
Published: (2024)

Query complexity lower bounds for local list-decoding and hard-core predicates (even for small rate and huge lists)
by: Ron-Zewi, Noga, et al.
Published: (2024)

A quasi-optimal lower bound for skew polynomial multiplication
by: Chen, Qiyuan, et al.
Published: (2024)

Complexity lower bounds for succinct binary structures of bounded clique-width with restrictions
by: Geniet, Colin, et al.
Published: (2026)

A note on quantum lower bounds for local search via congestion and expansion
by: Brânzei, Simina, et al.
Published: (2024)

Nine lower bound conjectures on streaming approximation algorithms for CSPs
by: Singer, Noah G.
Published: (2025)

Clifford testing: algorithms and lower bounds
by: Hinsche, Marcel, et al.
Published: (2025)

A combinatorial view of Holant problems on higher domains
by: Liu, Yin
Published: (2024)

An in-principle super-polynomial quantum advantage for approximating combinatorial optimization problems via computational learning theory
by: Pirnay, Niklas, et al.
Published: (2022)

Optimal lower bounds for quantum state tomography
by: Scharnhorst, Thilo, et al.
Published: (2025)

Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof
by: S., Karthik C., et al.
Published: (2023)

Rice-like complexity lower bounds for Boolean and uniform automata networks
by: Goubault-Larrecq, Aliénor, et al.
Published: (2024)

A lower bound on the field size of convolutional codes with a maximum distance profile and an improved construction
by: Chen, Zitan
Published: (2023)

On Detecting $H$-Induced Minors for Small $H$
by: Eagling-Vose, Tala, et al.
Published: (2026)

Curve Stabbing Depth: Data Depth for Plane Curves
by: Durocher, Stephane, et al.
Published: (2023)

An unconditional lower bound for the active-set method on the hypercube
by: Disser, Yann, et al.
Published: (2025)

The Complexity of Drawing Graphs on Few Lines and Few Planes
by: Chaplick, Steven, et al.
Published: (2016)

Are Depth-2 Regular Expressions Hard to Intersect?
by: Ascone, Rocco, et al.
Published: (2025)

Optimal Depth-Three Circuits for Inner Product
by: Gurumukhani, Mohit, et al.
Published: (2026)

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

Lower bounds for planar Arithmetic Circuits
by: Ramya, C., et al.
Published: (2025)

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

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

An unconditional lower bound for the active-set method in convex quadratic maximization
by: Bach, Eleon, et al.
Published: (2025)

Beyond Bell sampling: stabilizer state learning and quantum pseudorandomness lower bounds on qudits
by: Allcock, Jonathan, et al.
Published: (2024)

On the complexity of freezing automata networks of bounded pathwidth
by: Goles, Eric, et al.
Published: (2025)

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

Randomized Black-Box PIT for Small Depth +-Regular Non-commutative Circuits
by: Bharadwaj, G V Sumukha, et al.
Published: (2024)