Image de couverture de livre

Lower bounds for planar Arithmetic Circuits

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Ramya, C., Shastri, Pratik
Format:	Preprint
Publié:	2025
Sujets:	Computational Complexity
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

A Quadratic Lower Bound for Noncommutative Circuits
par: Shastri, Pratik
Publié: (2026)

On the Hardness of Order Finding and Equivalence Testing for ROABPs
par: Ramya, C., et autres
Publié: (2025)

Efficient Polynomial Identity Testing Over Nonassociative Algebras
par: Mukhopadhyay, Partha, et autres
Publié: (2025)

Polynomial Lower Bounds for Arithmetic Circuits over Non-Commutative Rings
par: Raz, Ran
Publié: (2026)

Arithmetic Circuits with Division
par: Sacher, Silas Cato
Publié: (2025)

Constant-Depth Arithmetic Circuits for Linear Algebra Problems
par: Andrews, Robert, et autres
Publié: (2024)

Convergent Gate Elimination and Constructive Circuit Lower Bounds
par: Carmosino, Marco, et autres
Publié: (2026)

Top-Down Lower Bounds for Depth-Four Circuits
par: Göös, Mika, et autres
Publié: (2023)

Optimal Monotone Depth-Three Circuit Lower Bounds for Majority
par: Gurumukhani, Mohit, et autres
Publié: (2026)

Optimal Lower Bounds for Symmetric Modular Circuits
par: Pago, Benedikt
Publié: (2026)

New Algebrization Barriers to Circuit Lower Bounds via Communication Complexity of Missing-String
par: Chen, Lijie, et autres
Publié: (2025)

Improved Circuit Lower Bounds and Quantum-Classical Separations
par: Grewal, Sabee, et autres
Publié: (2024)

Lower bounds for set-blocked clauses proofs
par: Yolcu, Emre
Publié: (2024)

Circuit metaconstruction in logspace for Rice-like complexity lower bounds in ANs and SGRs
par: Goubault-Larrecq, Aliénor, et autres
Publié: (2025)

Symmetric Arithmetic Circuits
par: Dawar, Anuj, et autres
Publié: (2020)

If VNP is hard, then so are equations for it
par: Kumar, Mrinal, et autres
Publié: (2020)

AC^0[p]-Frege Cannot Efficiently Prove that Constant-Depth Algebraic Circuit Lower Bounds are Hard
par: Lu, Jiaqi, et autres
Publié: (2025)

New Lower-bounds for Quantum Computation with Non-Collapsing Measurements
par: Miloschewsky, David, et autres
Publié: (2024)

Witnessing Flows in Arithmetic
par: Tabatabai, Amirhossein Akbar
Publié: (2024)

On the Existence of Algebraic Natural Proofs
par: Chatterjee, Prerona, et autres
Publié: (2020)

Arithmetic Circuits and Neural Networks for Regular Matroids
par: Hertrich, Christoph, et autres
Publié: (2025)

Lower bounds for quantum-inspired classical algorithms via communication complexity
par: Mande, Nikhil S., et autres
Publié: (2024)

Quadratic Lower bounds on the Approximate Stabilizer Rank: A Probabilistic Approach
par: Mehraban, Saeed, et autres
Publié: (2023)

Lower bounds on pure dynamic programming for connectivity problems on graphs of bounded path-width
par: Kluk, Kacper, et autres
Publié: (2025)

Feasibility of Primality in Bounded Arithmetic
par: Jalali, Raheleh, et autres
Publié: (2025)

Boolean Circuit Complexity and Two-Dimensional Cover Problems
par: Cavalar, Bruno P., et autres
Publié: (2025)

Polynomial and analytic methods for classifying complexity of planar graph homomorphisms
par: Cai, Jin-Yi, et autres
Publié: (2024)

Toward a Characterization of Simulation Between Arithmetic Theories
par: Monroe, Hunter
Publié: (2026)

Sharp Thresholds Imply Circuit Lower Bounds: from random 2-SAT to Planted Clique
par: Gamarnik, David, et autres
Publié: (2023)

Local Enumeration and Majority Lower Bounds
par: Gurumukhani, Mohit, et autres
Publié: (2024)

Lower Bounds for Approximate Sign Rank
par: Bindua, Riju, et autres
Publié: (2026)

Spectral Lower Bounds for Local Search
par: Brânzei, Simina, et autres
Publié: (2024)

Symmetric Distributions from Shallow Circuits
par: Kane, Daniel M., et autres
Publié: (2025)

Symmetric Algebraic Circuits and Homomorphism Polynomials
par: Dawar, Anuj, et autres
Publié: (2025)

Simple Circuit Extensions for XOR in PTIME
par: Carmosino, Marco, et autres
Publié: (2025)

Proof Systems Based on Structured Circuits
par: Micun, Matthäus, et autres
Publié: (2026)

Circuits and Backdoors: Five Shades of the SETH
par: Lampis, Michael
Publié: (2024)

Nearest Neighbor Complexity and Boolean Circuits
par: DiCicco, Mason, et autres
Publié: (2024)

IPS Lower Bounds for Formulas and Sum of ROABPs
par: Chatterjee, Prerona, et autres
Publié: (2025)

Lower Bounds for Set-Multilinear Branching Programs
par: Chatterjee, Prerona, et autres
Publié: (2023)