Imagen de Portada

Optimal Monotone Depth-Three Circuit Lower Bounds for Majority

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Gurumukhani, Mohit, Kleber, Daniel, Paturi, Ramamohan, Rosin, Christopher, Saks, Michael, Talebanfard, Navid
Formato:	Preprint
Publicado:	2026
Materias:	Computational Complexity
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

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

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

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

On Extremal Properties of k-CNF: Capturing Threshold Functions
por: Gurumukhani, Mohit, et al.
Publicado: (2024)

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

On the Existence of Seedless Condensers: Exploring the Terrain
por: Chattopadhyay, Eshan, et al.
Publicado: (2023)

Extractors for Polynomial Sources over $\mathbb{F}_2$
por: Chattopadhyay, Eshan, et al.
Publicado: (2023)

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

Optimal Lower Bounds for Symmetric Modular Circuits
por: Pago, Benedikt
Publicado: (2026)

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

Monotone Bounded-Depth Complexity of Homomorphism Polynomials
por: Bhargav, C. S., et al.
Publicado: (2025)

A Quadratic Lower Bound for Noncommutative Circuits
por: Shastri, Pratik
Publicado: (2026)

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

Improved Bounds for Coin Flipping, Leader Election, and Random Selection
por: Chattopadhyay, Eshan, et al.
Publicado: (2025)

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

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

Condensing and Extracting Against Online Adversaries
por: Chattopadhyay, Eshan, et al.
Publicado: (2024)

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

Monotone Circuit Complexity of Matching
por: Cavalar, Bruno, et al.
Publicado: (2025)

Two-Sided Lossless Expanders in the Unbalanced Setting
por: Chattopadhyay, Eshan, et al.
Publicado: (2024)

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

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

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

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

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

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

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

Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH
por: Guruswami, Venkatesan, et al.
Publicado: (2024)

CLIQUE as an AND of Polynomial-Sized Monotone Constant-Depth Circuits
por: Bodnar, Levente
Publicado: (2024)

Conditional Complexity Hardness: Monotone Circuit Size, Matrix Rigidity, and Tensor Rank
por: Chukhin, Nikolai, et al.
Publicado: (2024)

Near-Optimal Space Lower Bounds for Streaming CSPs
por: Fei, Yumou, et al.
Publicado: (2026)

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

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

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

Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs
por: Singer, Noah G., et al.
Publicado: (2026)

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

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

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

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

Improved Bounds on the Space Complexity of Circuit Evaluation
por: Shalunov, Yakov
Publicado: (2025)