Cover Image

Symmetric Arithmetic Circuits

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Dawar, Anuj, Wilsenach, Gregory
Format:	Preprint
Published:	2020
Subjects:	Computational Complexity Discrete Mathematics Logic in Computer Science F.1.3; F.2.1
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Lower Bounds for Symmetric Circuits for the Determinant
by: Dawar, Anuj, et al.
Published: (2021)

PosSLP and Sum of Squares
by: Bläser, Markus, et al.
Published: (2024)

Notes on CSPs and Polymorphisms
by: Brady, Zarathustra
Published: (2022)

The Banach-Butterfly Invariant: Influence-Adaptive Walsh Geometry for Ternary Polynomial Threshold Functions
by: Pavlov, Gorgi
Published: (2026)

Hardness of busy beaver value BB(15)
by: Stérin, Tristan, et al.
Published: (2021)

Misère Partizan Arc Kayles is PSPACE-complete, even on Planar Graphs
by: Burke, Kyle, et al.
Published: (2025)

Hereditary First-Order Logic: the tractable quantifier prefix classes
by: Bodirsky, Manuel, et al.
Published: (2024)

On the Computational Power of Extensional ESO
by: Bodirsky, Manuel, et al.
Published: (2025)

Imperative process algebra and models of computation
by: Middelburg, C. A.
Published: (2022)

On the Satisfaction Probabilities of $k$-CNF Formulas
by: Tantau, Till
Published: (2022)

Reduction of the graph isomorphism problem to equality checking of $n$-variables polynomials and the algorithms that use the reduction
by: Prolubnikov, Alexander
Published: (2015)

On the Counting Complexity of the Skolem Problem
by: Jindal, Gorav, et al.
Published: (2024)

On the Complexity of Problems on Graphs Defined on Groups
by: Das, Bireswar, et al.
Published: (2025)

Characterizing NC1 with Typed Monoids
by: Dawar, Anuj, et al.
Published: (2025)

SAT problem and Limit of Solomonoff's inductive reasoning theory
by: Pan, Feng
Published: (2025)

Algorithmic hardness of the partition function for nucleic acid strands
by: Ducloz, Gwendal, et al.
Published: (2025)

The Bit Complexity of Dynamic Algebraic Formulas and their Determinants
by: Anand, Emile, et al.
Published: (2024)

Polynomial-time Tractable Problems over the $p$-adic Numbers
by: Fehm, Arno, et al.
Published: (2025)

A Note on the NP-Hardness of PARTITION Via First-Order Projections
by: Iturralde, Paúl Risco
Published: (2025)

Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs
by: de Rezende, Susanna F., et al.
Published: (2019)

Rankwidth of Graphs with Balanced Separations: Expansion for Dense Graphs
by: Anand, Emile
Published: (2025)

On Sampling Lower Bounds for Polynomials
by: Khodabandeh, Mohammad Mahdi, et al.
Published: (2026)

Homomorphism Indistinguishability and Game Comonads for Restricted Conjunction and Requantification
by: Schindling, Georg
Published: (2025)

Constructibility and the P versus NP problem
by: Hole, Arne
Published: (2024)

Towards New Characterizations of Small Circuit Classes via Discrete Ordinary Differential Equations
by: Antonelli, Melissa, et al.
Published: (2025)

A SAT-based Approach for Specification, Analysis, and Justification of Reductions between NP-complete Problems
by: Janičić, Predrag
Published: (2025)

A Complete Finitary Refinement Type System for Scott-Open Properties
by: Riba, Colin, et al.
Published: (2026)

Arithmetic Complexity of Solutions of the Dirichlet Problem
by: Boche, Holger, et al.
Published: (2026)

Graph Neural Networks and Arithmetic Circuits
by: Barlag, Timon, et al.
Published: (2024)

Average Attention Transformers and Arithmetic Circuits
by: Ehrmuth, Lena, et al.
Published: (2026)

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

Guaranteed Bounds on Posterior Distributions of Discrete Probabilistic Programs with Loops
by: Zaiser, Fabian, et al.
Published: (2024)

Recurrent Graph Neural Networks and Arithmetic Circuits
by: Barlag, Timon, et al.
Published: (2026)

Beyond Worst-Case Subset Sum: An Adaptive, Structure-Aware Solver with Sub-$2^{n/2}$ Enumeration
by: Salas, Jesus
Published: (2025)

Finitely (In)tractable Promise Constraint Satisfaction Problems
by: Asimi, Kristina, et al.
Published: (2020)

Col is PSPACE-complete on Triangular Grids
by: Burke, Kyle, et al.
Published: (2025)

A LOCAL View of the Polynomial Hierarchy
by: Reiter, Fabian
Published: (2023)

Lower Bounds on Inverse Cellular Automata via Proof Complexity
by: Kapytka, Maryia
Published: (2026)

Failure of the strong feasible disjunction property
by: Krajicek, Jan
Published: (2026)

On the Complexity of Determinations
by: Hellerstein, Joseph M.
Published: (2026)