Copertina

Bounded-Depth Frege Lower Bounds for Random 3-CNFs via Deterministic Restrictions

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Gryaznov, Svyatoslav, Talebanfard, Navid
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Computational Complexity
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

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

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

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

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

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

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

Toward Better Depth Lower Bounds: Strong Composition of XOR and a Random Function
di: Chukhin, Nikolai, et al.
Pubblicazione: (2024)

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

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

Tight Streaming Lower Bounds for Deterministic Approximate Counting
di: Wang, Yichuan
Pubblicazione: (2024)

Local Enumeration: The Not-All-Equal Case
di: Gurumukhani, Mohit, et al.
Pubblicazione: (2025)

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

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

Exponential Lower Bounds on the Size of ResLin Proofs of Nearly Quadratic Depth
di: Bhattacharya, Sreejata Kishor, et al.
Pubblicazione: (2025)

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

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

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

A Quadratic Lower Bound for Noncommutative Circuits
di: Shastri, Pratik
Pubblicazione: (2026)

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

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

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

Lower Bounds for Conjunctive Query Evaluation
di: Mengel, Stefan
Pubblicazione: (2025)

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

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

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

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

Toward Better Depth Lower Bounds: A KRW-like theorem for Strong Composition
di: Meir, Or
Pubblicazione: (2023)

New Algebrization Barriers to Circuit Lower Bounds via Communication Complexity of Missing-String
di: Chen, Lijie, et al.
Pubblicazione: (2025)

Decision DNNFs with imbalanced conjunction cannot efficiently represent CNFs of bounded width
di: Razgon, Igor
Pubblicazione: (2025)

Improved Lower Bounds for QAC0
di: Joshi, Malvika Raj, et al.
Pubblicazione: (2025)

Algorithmic Structure in Subset Sum: Deterministic In-Bound Navigation and the Counting Complexity Divide
di: Nkosi, Thami
Pubblicazione: (2025)

Lower Bounds for Convexity Testing
di: Chen, Xi, et al.
Pubblicazione: (2024)

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

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

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

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

Upper and Lower Bounds on $T_1$ and $T_2$ Decision Tree Model
di: Alhamdan, Yousef M.
Pubblicazione: (2025)

Separations above TFNP from Sherali-Adams Lower Bounds
di: Fleming, Noah, et al.
Pubblicazione: (2026)

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

Optimal Lower Bounds for Symmetric Modular Circuits
di: Pago, Benedikt
Pubblicazione: (2026)