Buchumschlag

A note on Jerabek's paper "A simplified lower bound for implicational logic"

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Gordeev, Lev, Haeusler, Edward Hermann
Format:	Preprint
Veröffentlicht:	2026
Schlagworte:	Computational Complexity
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Proofs of NP = coNP = PSPACE: Current upgrade
von: Gordeev, Lev, et al.
Veröffentlicht: (2023)

On P Versus NP
von: Gordeev, Lev
Veröffentlicht: (2020)

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

A simplified lower bound for implicational logic
von: Jeřábek, Emil
Veröffentlicht: (2023)

Exponential lower bound via exponential sums
von: Bhattacharjee, Somnath, et al.
Veröffentlicht: (2026)

Simple general magnification of circuit lower bounds
von: Atserias, Albert, et al.
Veröffentlicht: (2025)

Depth lower bounds in Stabbing Planes for combinatorial principles
von: Dantchev, Stefan, et al.
Veröffentlicht: (2021)

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

On the horizontal compression of dag-derivations in minimal purely implicational logic
von: Haeusler, Edward Hermann, et al.
Veröffentlicht: (2022)

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

Quantum circuit lower bounds in the magic hierarchy
von: Parham, Natalie
Veröffentlicht: (2025)

On the consistency of stronger lower bounds for NEXP
von: Thapen, Neil
Veröffentlicht: (2025)

A quasi-optimal lower bound for skew polynomial multiplication
von: Chen, Qiyuan, et al.
Veröffentlicht: (2024)

A simplified version of the quantum OTOC$^{(2)}$ problem
von: King, Robbie, et al.
Veröffentlicht: (2025)

Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof
von: S., Karthik C., et al.
Veröffentlicht: (2023)

Computational lower bounds for multi-frequency group synchronization
von: Kireeva, Anastasia, et al.
Veröffentlicht: (2024)

Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds
von: Agarwal, Avantika, et al.
Veröffentlicht: (2024)

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

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

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

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

Resilient functions: Optimized, simplified, and generalized
von: Ivanov, Peter, et al.
Veröffentlicht: (2024)

Nine lower bound conjectures on streaming approximation algorithms for CSPs
von: Singer, Noah G.
Veröffentlicht: (2025)

Clifford testing: algorithms and lower bounds
von: Hinsche, Marcel, et al.
Veröffentlicht: (2025)

A note on approximating the average degree of bounded arboricity graphs
von: Eden, Talya, et al.
Veröffentlicht: (2026)

Optimal lower bounds for quantum state tomography
von: Scharnhorst, Thilo, et al.
Veröffentlicht: (2025)

A simplified proof of the CSP Dichotomy Conjecture and XY-symmetric operations
von: Zhuk, Dmitriy
Veröffentlicht: (2024)

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

Syndrome aware mitigation of logical errors
von: Aharonov, Dorit, et al.
Veröffentlicht: (2025)

On the local consequence of modal Product logic: standard completeness and decidability
von: Vidal, Amanda
Veröffentlicht: (2023)

An unconditional lower bound for the active-set method on the hypercube
von: Disser, Yann, et al.
Veröffentlicht: (2025)

A characterization of efficiently compilable constraint languages
von: Berkholz, Christoph, et al.
Veröffentlicht: (2023)

Capturing the polynomial hierarchy by second-order revised Krom logic
von: Wang, Kexu, et al.
Veröffentlicht: (2022)

Lower bounds for planar Arithmetic Circuits
von: Ramya, C., et al.
Veröffentlicht: (2025)

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

Beyond Bell sampling: stabilizer state learning and quantum pseudorandomness lower bounds on qudits
von: Allcock, Jonathan, et al.
Veröffentlicht: (2024)

A simple lower bound for the complexity of estimating partition functions on a quantum computer
von: Chen, Zherui, et al.
Veröffentlicht: (2024)

A degree 4 sum-of-squares lower bound for the clique number of the Paley graph
von: Kunisky, Dmitriy, et al.
Veröffentlicht: (2022)

A linear bound for the size of the finite terminal assembly of a directed non-cooperative tile assembly system
von: Ivanov, Sergiu, et al.
Veröffentlicht: (2024)

The monotonicity of the Franz-Parisi potential is equivalent with Low-degree MMSE lower bounds
von: Tsirkas, Konstantinos, et al.
Veröffentlicht: (2026)