Imagen de Portada

Optimal Depth-Three Circuits for Inner Product

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Gurumukhani, Mohit, Kleber, Daniel, Paturi, Ramamohan, Rosin, Christopher, 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 Monotone Depth-Three Circuit Lower Bounds for Majority
por: Gurumukhani, Mohit, et al.
Publicado: (2026)

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

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

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)

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

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

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

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

The Computational Complexity of Circuit Discovery for Inner Interpretability
por: Adolfi, Federico, et al.
Publicado: (2024)

Constant-Depth Arithmetic Circuits for Linear Algebra Problems
por: Andrews, Robert, et al.
Publicado: (2024)

Polynomial Identity Testing and Reconstruction for Depth-4 Powering Circuits of High Degree
por: Shpilka, Amir, et al.
Publicado: (2026)

Randomized Black-Box PIT for Small Depth +-Regular Non-commutative Circuits
por: Bharadwaj, G V Sumukha, et al.
Publicado: (2024)

Thermodynamic Signature of Logical Depth in Quantum Circuits
por: Ibnouhsein, Issam
Publicado: (2025)

Classical Simulability of Quantum Circuits with Shallow Magic Depth
por: Zhang, Yifan, et al.
Publicado: (2024)

Towards Deterministic Algorithms for Constant-Depth Factors of Constant-Depth Circuits
por: Kumar, Mrinal, et al.
Publicado: (2024)

Lifting with Inner Functions of Polynomial Discrepancy
por: Manor, Yahel, et al.
Publicado: (2024)

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

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

On the Minimum Depth of Circuits with Linear Number of Wires Encoding Good Codes
por: Drucker, Andrew, et al.
Publicado: (2024)

Polynomial-Time Classical Simulation of Noisy IQP Circuits with Constant Depth
por: Rajakumar, Joel, et al.
Publicado: (2024)

Symmetric Distributions from Shallow Circuits
por: Kane, Daniel M., et al.
Publicado: (2025)

Nearest Neighbor Complexity and Boolean Circuits
por: DiCicco, Mason, et al.
Publicado: (2024)

The Jacobi Factoring Circuit: Quantum Factoring with Near-Linear Gates and Sublinear Space and Depth
por: Kahanamoku-Meyer, Gregory D., et al.
Publicado: (2024)

Efficient Matrix Product State Learning in Logarithmic Depth
por: Lin, Chia-Ying, et al.
Publicado: (2025)

Arithmetic Circuits with Division
por: Sacher, Silas Cato
Publicado: (2025)

On the Constant-Depth Circuit Complexity of Generating Quasigroups
por: Collins, Nathaniel A., et al.
Publicado: (2024)

Proof Systems Based on Structured Circuits
por: Micun, Matthäus, et al.
Publicado: (2026)

Symmetric Algebraic Circuits and Homomorphism Polynomials
por: Dawar, Anuj, et al.
Publicado: (2025)

Simple Circuit Extensions for XOR in PTIME
por: Carmosino, Marco, et al.
Publicado: (2025)

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

Circuits and Backdoors: Five Shades of the SETH
por: Lampis, Michael
Publicado: (2024)

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

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

Nondeterministic Auxiliary Depth-Bounded Storage Automata and Semi-Unbounded Fan-in Cascading Circuits
por: Yamakami, Tomoyuki
Publicado: (2024)

Are Depth-2 Regular Expressions Hard to Intersect?
por: Ascone, Rocco, et al.
Publicado: (2025)

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

Boolean Circuit Complexity and Two-Dimensional Cover Problems
por: Cavalar, Bruno P., et al.
Publicado: (2025)