Imagen de Portada

Realizable Circuit Complexity: Embedding Computation in Space-Time

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Prada, Benjamin, Mali, Ankur
Formato:	Preprint
Publicado:	2025
Materias:	Computational Complexity Machine Learning F.1.0; F.1.3
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Graph-Based Deterministic Polynomial Framwork for NP Problems
por: Lee, Changryeol
Publicado: (2025)

Nonuniform Deterministic Finite Automata over finite algebraic structures
por: Idziak, Paweł M., et al.
Publicado: (2025)

Complexity Classes Arising from Circuits over Finite Algebraic Structures
por: Kawałek, Piotr, et al.
Publicado: (2026)

Constructibility and the P versus NP problem
por: Hole, Arne
Publicado: (2024)

Catalytic Computing and Register Programs Beyond Log-Depth
por: Alekseev, Yaroslav, et al.
Publicado: (2025)

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

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

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

Disjunctive Complexity
por: Ivanov, Nikita, et al.
Publicado: (2025)

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

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

Understanding Robust Catalytic Computing
por: Koucký, Michal, et al.
Publicado: (2026)

Completing the Complexity Classification of 2-Solo Chess: Knights and Kings are Hard
por: Kühn, Kolja, et al.
Publicado: (2026)

Gaps, Ambiguity, and Establishing Complexity-Class Containments via Iterative Constant-Setting
por: Hemaspaandra, Lane A., et al.
Publicado: (2021)

A point to set principle for finite-state dimension
por: Mayordomo, Elvira
Publicado: (2022)

Reachability with Restricted Reactions in Inhibitory Chemical Reaction Networks
por: Bajaj, Divya, et al.
Publicado: (2026)

A Note On The Natural Range Of Unambiguous-SAT
por: Pay, Tayfun
Publicado: (2023)

On the Complexity of Determinations
por: Hellerstein, Joseph M.
Publicado: (2026)

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

Certificate-Sensitive Subset Sum: Realizing Instance Complexity
por: Salas, Jesus
Publicado: (2025)

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

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

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

L is different from NP
por: Montoya, J. Andres
Publicado: (2024)

Separation Results for Constant-Depth and Multilinear Ideal Proof Systems
por: Behera, Amik Raj, et al.
Publicado: (2026)

Hausdorff Reductions and the Exponential Hierarchies
por: Malizia, Enrico
Publicado: (2024)

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

Symmetric Arithmetic Circuits
por: Dawar, Anuj, et al.
Publicado: (2020)

CLIQUE as an AND of Polynomial-Sized Monotone Constant-Depth Circuits
por: Bodnar, Levente
Publicado: (2024)

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

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

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

The Serial Scaling Hypothesis
por: Liu, Yuxi, et al.
Publicado: (2025)

Structure of sparse Boolean functions over Abelian groups, and its application to testing
por: Chakraborty, Sourav, et al.
Publicado: (2024)

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

Explicit Commutative ROABPs from Partial Derivatives
por: Bhargava, Vishwas, et al.
Publicado: (2024)

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

On the Complexity of the Conditional Independence Implication Problem With Bounded Cardinalities
por: Makowski, Michał
Publicado: (2024)

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

Formula Size-Depth Tradeoffs for Iterated Sub-Permutation Matrix Multiplication
por: Rossman, Benjamin
Publicado: (2024)