Cover Image

Top-Down Lower Bounds for Depth-Four Circuits

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Göös, Mika, Riazanov, Artur, Sofronova, Anastasia, Sokolov, Dmitry
Format:	Preprint
Published:	2023
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Monotone Circuit Complexity of Matching
by: Cavalar, Bruno, et al.
Published: (2025)

Pseudodeterministic Communication Complexity
by: Göös, Mika, et al.
Published: (2025)

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

Sampling Permutations with Cell Probes is Hard
by: Alekseev, Yaroslav, et al.
Published: (2025)

Equality is Far Weaker than Constant-Cost Communication
by: Göös, Mika, et al.
Published: (2025)

No Constant-Cost Protocol for Point--Line Incidence
by: Göös, Mika, et al.
Published: (2026)

Supercritical Tradeoffs for Monotone Circuits
by: Göös, Mika, et al.
Published: (2024)

Partial Minimum Branching Program Size Problem is ETH-hard
by: Glinskih, Ludmila, et al.
Published: (2024)

Sign-Rank of $k$-Hamming Distance is Constant
by: Göös, Mika, et al.
Published: (2025)

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

Better Boosting of Communication Oracles, or Not
by: Harms, Nathaniel, et al.
Published: (2024)

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

Spiky Rank and Its Applications to Rigidity and Circuits
by: Hambardzumyan, Lianna, et al.
Published: (2026)

Certificate Games and Consequences for the Classical Adversary Bound
by: Chakraborty, Sourav, et al.
Published: (2022)

A Quadratic Lower Bound for Noncommutative Circuits
by: Shastri, Pratik
Published: (2026)

Constant-Cost Communication is not Reducible to k-Hamming Distance
by: Fang, Yuting, et al.
Published: (2024)

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

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

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

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

Optimal Lower Bounds for Symmetric Modular Circuits
by: Pago, Benedikt
Published: (2026)

Quantum Communication Advantage in TFNP
by: Göös, Mika, et al.
Published: (2024)

Polynomial Lower Bounds for Arithmetic Circuits over Non-Commutative Rings
by: Raz, Ran
Published: (2026)

Average-Case Hardness of Binary-Encoded Clique in Proof and Communication Complexity
by: de Rezende, Susanna F., et al.
Published: (2026)

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

Improved Circuit Lower Bounds and Quantum-Classical Separations
by: Grewal, Sabee, et al.
Published: (2024)

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

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

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

Separations in Proof Complexity and TFNP
by: Göös, Mika, et al.
Published: (2022)

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

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

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

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

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

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

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

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

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

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