Buchumschlag

Symmetric Arithmetic Circuits

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Dawar, Anuj, Wilsenach, Gregory
Format:	Preprint
Veröffentlicht:	2020
Schlagworte:	Computational Complexity Discrete Mathematics Logic in Computer Science F.1.3; F.2.1
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Lower Bounds for Symmetric Circuits for the Determinant
von: Dawar, Anuj, et al.
Veröffentlicht: (2021)

PosSLP and Sum of Squares
von: Bläser, Markus, et al.
Veröffentlicht: (2024)

Notes on CSPs and Polymorphisms
von: Brady, Zarathustra
Veröffentlicht: (2022)

The Banach-Butterfly Invariant: Influence-Adaptive Walsh Geometry for Ternary Polynomial Threshold Functions
von: Pavlov, Gorgi
Veröffentlicht: (2026)

Hardness of busy beaver value BB(15)
von: Stérin, Tristan, et al.
Veröffentlicht: (2021)

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

Hereditary First-Order Logic: the tractable quantifier prefix classes
von: Bodirsky, Manuel, et al.
Veröffentlicht: (2024)

On the Computational Power of Extensional ESO
von: Bodirsky, Manuel, et al.
Veröffentlicht: (2025)

Imperative process algebra and models of computation
von: Middelburg, C. A.
Veröffentlicht: (2022)

On the Satisfaction Probabilities of $k$-CNF Formulas
von: Tantau, Till
Veröffentlicht: (2022)

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

On the Counting Complexity of the Skolem Problem
von: Jindal, Gorav, et al.
Veröffentlicht: (2024)

On the Complexity of Problems on Graphs Defined on Groups
von: Das, Bireswar, et al.
Veröffentlicht: (2025)

Characterizing NC1 with Typed Monoids
von: Dawar, Anuj, et al.
Veröffentlicht: (2025)

SAT problem and Limit of Solomonoff's inductive reasoning theory
von: Pan, Feng
Veröffentlicht: (2025)

Algorithmic hardness of the partition function for nucleic acid strands
von: Ducloz, Gwendal, et al.
Veröffentlicht: (2025)

The Bit Complexity of Dynamic Algebraic Formulas and their Determinants
von: Anand, Emile, et al.
Veröffentlicht: (2024)

Polynomial-time Tractable Problems over the $p$-adic Numbers
von: Fehm, Arno, et al.
Veröffentlicht: (2025)

A Note on the NP-Hardness of PARTITION Via First-Order Projections
von: Iturralde, Paúl Risco
Veröffentlicht: (2025)

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

Rankwidth of Graphs with Balanced Separations: Expansion for Dense Graphs
von: Anand, Emile
Veröffentlicht: (2025)

On Sampling Lower Bounds for Polynomials
von: Khodabandeh, Mohammad Mahdi, et al.
Veröffentlicht: (2026)

Homomorphism Indistinguishability and Game Comonads for Restricted Conjunction and Requantification
von: Schindling, Georg
Veröffentlicht: (2025)

Constructibility and the P versus NP problem
von: Hole, Arne
Veröffentlicht: (2024)

Towards New Characterizations of Small Circuit Classes via Discrete Ordinary Differential Equations
von: Antonelli, Melissa, et al.
Veröffentlicht: (2025)

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

A Complete Finitary Refinement Type System for Scott-Open Properties
von: Riba, Colin, et al.
Veröffentlicht: (2026)

Arithmetic Complexity of Solutions of the Dirichlet Problem
von: Boche, Holger, et al.
Veröffentlicht: (2026)

Graph Neural Networks and Arithmetic Circuits
von: Barlag, Timon, et al.
Veröffentlicht: (2024)

Average Attention Transformers and Arithmetic Circuits
von: Ehrmuth, Lena, et al.
Veröffentlicht: (2026)

Supercritical Tradeoffs for Monotone Circuits
von: Göös, Mika, et al.
Veröffentlicht: (2024)

Guaranteed Bounds on Posterior Distributions of Discrete Probabilistic Programs with Loops
von: Zaiser, Fabian, et al.
Veröffentlicht: (2024)

Recurrent Graph Neural Networks and Arithmetic Circuits
von: Barlag, Timon, et al.
Veröffentlicht: (2026)

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

Finitely (In)tractable Promise Constraint Satisfaction Problems
von: Asimi, Kristina, et al.
Veröffentlicht: (2020)

Col is PSPACE-complete on Triangular Grids
von: Burke, Kyle, et al.
Veröffentlicht: (2025)

A LOCAL View of the Polynomial Hierarchy
von: Reiter, Fabian
Veröffentlicht: (2023)

Lower Bounds on Inverse Cellular Automata via Proof Complexity
von: Kapytka, Maryia
Veröffentlicht: (2026)

Failure of the strong feasible disjunction property
von: Krajicek, Jan
Veröffentlicht: (2026)

On the Complexity of Determinations
von: Hellerstein, Joseph M.
Veröffentlicht: (2026)