Cover Image

Descriptive complexity for neural networks via Boolean networks

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Ahvonen, Veeti, Heiman, Damian, Kuusisto, Antti
Format:	Preprint
Published:	2023
Subjects:	Computational Complexity Logic in Computer Science 68Q19 F.4.1; C.2.0; G.1.0
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Graph neural networks and MSO
by: Ahvonen, Veeti, et al.
Published: (2025)

Graded modal logic and counting message passing automata
by: Ahvonen, Veeti, et al.
Published: (2024)

Logical Characterizations of Recurrent Graph Neural Networks with Reals and Floats
by: Ahvonen, Veeti, et al.
Published: (2024)

Expressive Power of Graph Transformers via Logic
by: Ahvonen, Veeti, et al.
Published: (2025)

Cross-Attention and Encoder-Decoder Transformers: A Logical Characterization
by: Ahvonen, Veeti, et al.
Published: (2026)

Neural networks as fuzzy logic formulas
by: Heiman, Damian, et al.
Published: (2026)

Description Complexity of Unary Structures in First-Order Logic with Links to Entropy
by: Jaakkola, Reijo, et al.
Published: (2024)

Adversarial Barrier in Uniform Class Separation
by: Rosko, Milan
Published: (2025)

On the existence of strong proof complexity generators
by: Krajicek, Jan
Published: (2022)

Structure-Guided Automated Reasoning
by: Bannach, Max, et al.
Published: (2023)

A Theory for Probabilistic Polynomial-Time Reasoning
by: Chen, Lijie, et al.
Published: (2026)

Extended Nullstellensatz proof systems
by: Krajicek, Jan
Published: (2023)

The Complexity of Resilience Problems via Valued Constraint Satisfaction
by: Bodirsky, Manuel, et al.
Published: (2023)

Insignificant Choice Polynomial Time: A Logic Capturing PTIME
by: Schewe, Klaus-Dieter
Published: (2020)

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

Constraint Satisfaction Problems over Finitely Bounded Homogeneous Structures: a Dichotomy between FO and L-hard
by: Dorochko, Leonid, et al.
Published: (2026)

Smaller Depth-2 Linear Circuits for Disjointness Matrices
by: Ye, Lixi
Published: (2026)

Group Order Logic
by: Dahan, Anatole
Published: (2025)

A Bisimulation-Invariance-Based Approach to the Separation of Polynomial Complexity Classes
by: Bruse, Florian, et al.
Published: (2026)

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

On the Descriptive Complexity of Groups without Abelian Normal Subgroups
by: Grochow, Joshua A., et al.
Published: (2022)

On the Realizability of Prime Conjectures in Heyting Arithmetic
by: Rosko, Milan
Published: (2025)

On the Parallel Complexity of Group Isomorphism via Weisfeiler-Leman
by: Grochow, Joshua A., et al.
Published: (2021)

Count-Free Weisfeiler--Leman and Group Isomorphism
by: Collins, Nathaniel A., et al.
Published: (2022)

A proof complexity conjecture and the Incompleteness theorem
by: Krajicek, Jan
Published: (2023)

Efficient Solving of Quantified Inequality Constraints over the Real Numbers
by: Ratschan, Stefan
Published: (2002)

A Complexity Dichotomy for Temporal Valued Constraint Satisfaction Problems
by: Bodirsky, Manuel, et al.
Published: (2024)

I/O complexity and pebble games with partial computations
by: Sobczyk, Aleksandros
Published: (2024)

Complexities of Well-Quasi-Ordered Substructural Logics
by: Galatos, Nikolaos, et al.
Published: (2025)

A correspondence between the time and space complexity
by: Latkin, Ivan V.
Published: (2023)

Propositional dynamic logic and asynchronous cascade decompositions for regular trace languages
by: Adsul, Bharat, et al.
Published: (2024)

The Solver's Paradox in Formal Problem Spaces
by: Rosko, Milan
Published: (2025)

Probabilistic Shoenfield Machines
by: Bujok, Maksymilian, et al.
Published: (2024)

Graded Monad Coalgebras for Continuous-Time Transition Systems
by: Di Lavore, Elena, et al.
Published: (2026)

Simulating and model checking membrane systems using strategies in Maude
by: Rubio, Rubén, et al.
Published: (2024)

A Logspace Constructive Proof of L=SL
by: Buss, Sam, et al.
Published: (2025)

Strategies, model checking and branching-time properties in Maude
by: Rubio, Rubén, et al.
Published: (2024)

Model checking strategy-controlled systems in rewriting logic
by: Rubio, Rubén, et al.
Published: (2024)

Metalevel transformation of strategies
by: Rubio, Rubén, et al.
Published: (2024)

A Theory of Hanoi Omega-Automata and Games
by: Filiot, Emmanuel, et al.
Published: (2026)