Buchumschlag

Exponential Lower Bounds on the Size of ResLin Proofs of Nearly Quadratic Depth

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Bhattacharya, Sreejata Kishor, Chattopadhyay, Arkadev
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Computational Complexity
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Exponential Separation Between Powers of Regular and General Resolution Over Parities
von: Bhattacharya, Sreejata Kishor, et al.
Veröffentlicht: (2024)

Aaronson-Ambainis Conjecture Is True For Random Restrictions
von: Bhattacharya, Sreejata Kishor
Veröffentlicht: (2024)

Exact versus Approximate Representations of Boolean Functions in the De Morgan Basis
von: Chattopadhyay, Arkadev, et al.
Veröffentlicht: (2025)

A Quadratic Lower Bound for Noncommutative Circuits
von: Shastri, Pratik
Veröffentlicht: (2026)

Exponential Lower Bounds for Smooth 3-LCCs and Sharp Bounds for Designs
von: Kothari, Pravesh K., et al.
Veröffentlicht: (2024)

Lower Bounds against the Ideal Proof System in Finite Fields
von: Elbaz, Tal, et al.
Veröffentlicht: (2025)

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

Lower Bounds for Bit Pigeonhole Principles in Bounded-Depth Resolution over Parities
von: Byramji, Farzan, et al.
Veröffentlicht: (2025)

Optimal Monotone Depth-Three Circuit Lower Bounds for Majority
von: Gurumukhani, Mohit, et al.
Veröffentlicht: (2026)

Treedepth Inapproximability and Exponential ETH Lower Bound
von: Bonnet, Édouard, et al.
Veröffentlicht: (2025)

Bounded-Depth Frege Lower Bounds for Random 3-CNFs via Deterministic Restrictions
von: Gryaznov, Svyatoslav, et al.
Veröffentlicht: (2024)

Lower Bounds for Unitary Property Testing with Proofs and Advice
von: Weggemans, Jordi
Veröffentlicht: (2024)

Symmetric Exponential Time Requires Near-Maximum Circuit Size: Simplified, Truly Uniform
von: Li, Zeyong
Veröffentlicht: (2023)

Finding Bugs in Short Proofs: The Metamathematics of Resolution Lower Bounds
von: Li, Jiawei, et al.
Veröffentlicht: (2024)

Exponential Lower Bounds for 2-query Relaxed Locally Decodable Codes
von: Block, Alexander R., et al.
Veröffentlicht: (2026)

Exponential Lower Bounds for Locally Decodable and Correctable Codes for Insertions and Deletions
von: Blocki, Jeremiah, et al.
Veröffentlicht: (2021)

Exponential-Size Circuit Complexity is Comeager in Symmetric Exponential Time
von: Hitchcock, John M.
Veröffentlicht: (2026)

Toward Better Depth Lower Bounds: Strong Composition of XOR and a Random Function
von: Chukhin, Nikolai, et al.
Veröffentlicht: (2024)

Tight Quantum Depth Lower Bound for Solving Systems of Linear Equations
von: Wang, Qisheng, et al.
Veröffentlicht: (2024)

Near-Optimal Space Lower Bounds for Streaming CSPs
von: Fei, Yumou, et al.
Veröffentlicht: (2026)

A Quadratic Lower Bound for Stable Roommates Solvability
von: Rosenbaum, Will
Veröffentlicht: (2025)

A Tight Double-Exponentially Lower Bound for High-Multiplicity Bin Packing
von: Jansen, Klaus, et al.
Veröffentlicht: (2025)

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

On the Bit Size of Sum-of-Squares Proofs for Symmetric Formulations
von: Bortolotti, Alex, et al.
Veröffentlicht: (2025)

Local Enumeration and Majority Lower Bounds
von: Gurumukhani, Mohit, et al.
Veröffentlicht: (2024)

Lower Bounds for Approximate Sign Rank
von: Bindua, Riju, et al.
Veröffentlicht: (2026)

Spectral Lower Bounds for Local Search
von: Brânzei, Simina, et al.
Veröffentlicht: (2024)

Superpolynomial Length Lower Bounds for Tree-Like Semantic Proof Systems with Bounded Line Size
von: de Rezende, Susanna F., et al.
Veröffentlicht: (2026)

IPS Lower Bounds for Formulas and Sum of ROABPs
von: Chatterjee, Prerona, et al.
Veröffentlicht: (2025)

Lower Bounds for Set-Multilinear Branching Programs
von: Chatterjee, Prerona, et al.
Veröffentlicht: (2023)

Lower Bounds from Succinct Hitting Sets
von: Chatterjee, Prerona, et al.
Veröffentlicht: (2023)

Toward Better Depth Lower Bounds: A KRW-like theorem for Strong Composition
von: Meir, Or
Veröffentlicht: (2023)

Oblivious Complexity Classes Revisited: Lower Bounds and Hierarchies
von: Gajulapalli, Karthik, et al.
Veröffentlicht: (2025)

Convergent Gate Elimination and Constructive Circuit Lower Bounds
von: Carmosino, Marco, et al.
Veröffentlicht: (2026)

Tight Lower Bounds for Block-Structured Integer Programs
von: Hunkenschröder, Christoph, et al.
Veröffentlicht: (2024)

Lower Bounds for Subset Sum in Resolution with Modular Counting
von: Part, Fedor
Veröffentlicht: (2022)

Lower Bounds for Conjunctive Query Evaluation
von: Mengel, Stefan
Veröffentlicht: (2025)

A Lower Bound on Conservative Elementary Object Systems Coverability
von: Di Cosmo, Francesco, et al.
Veröffentlicht: (2025)

Spectral Certificates and Sum-of-Squares Lower Bounds for Semirandom Hamiltonians
von: Kocurek, Nicholas
Veröffentlicht: (2025)

Upper and Lower Bounds on $T_1$ and $T_2$ Decision Tree Model
von: Alhamdan, Yousef M.
Veröffentlicht: (2025)