:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Bilardi, Gianfranco, De Stefani, Lorenzo
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity F.2
Online Access:	https://arxiv.org/abs/2410.20547
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Direct Sums for Parity Decision Trees
by: Besselman, Tyler, et al.
Published: (2024)

On the computational complexity of Data Flow Analysis
by: Sood, Gaurav, et al.
Published: (2013)

Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs
by: Gupta, Chetan, et al.
Published: (2025)

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

The complexity of finding coset-generating polymorphisms and the promise metaproblem
by: Bodirsky, Manuel, et al.
Published: (2026)

Towards universally optimal sorting algorithms
by: Sen, Sandeep
Published: (2025)

Computable Bounds and Monte Carlo Estimates of the Expected Edit Distance
by: Bilardi, Gianfranco, et al.
Published: (2022)

Correspondences in computational and dynamical complexity II: forcing complex reductions
by: Everett, Samuel
Published: (2026)

On bounded depth proofs for Tseitin formulas on the grid; revisited
by: Håstad, Johan, et al.
Published: (2022)

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

The framework to unify all complexity dichotomy theorems for Boolean tensor networks
by: Xia, Mingji
Published: (2026)

A Polynomial Time Algorithm for 3SAT
by: Quigley, Robert
Published: (2024)

The Complexity of Graph Exploration Games
by: Fuchs, Janosch, et al.
Published: (2023)

QSETH strikes again: finer quantum lower bounds for lattice problem, strong simulation, hitting set problem, and more
by: Chen, Yanlin, et al.
Published: (2023)

Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz
by: Conneryd, Jonas, et al.
Published: (2025)

Fast Simulation of Cellular Automata by Self-Composition
by: Natal, Joseph, et al.
Published: (2024)

NP-Completeness Proofs of Puzzles using the T-Metacell Framework
by: Kiatchaipipat, Nattapol, et al.
Published: (2025)

When Does Sparsity Help for k-Independent Set in Hypergraphs and Other Boolean CSPs?
by: Fritsch, Timo, et al.
Published: (2026)

Algorithms and Turing Kernels for Detecting and Counting Small Patterns in Unit Disk Graphs
by: Nederlof, Jesper, et al.
Published: (2023)

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

Tight bounds on depth-2 QAC-circuits computing parity
by: Fenner, Stephen, et al.
Published: (2025)

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

Graph Threading with Turn Costs
by: Demaine, Erik D., et al.
Published: (2024)

Hypercontractivity on HDX II: Symmetrization and q-Norms
by: Hopkins, Max
Published: (2024)

Optimal lower bounds for Quantum Learning via Information Theory
by: Hadiashar, Shima Bab, et al.
Published: (2023)

Sum-of-squares lower bounds for Non-Gaussian Component Analysis
by: Diakonikolas, Ilias, et al.
Published: (2024)

Proving Unsatisfiability with Hitting Formulas
by: Filmus, Yuval, et al.
Published: (2023)

Lower Bounds for CSP Hierarchies Through Ideal Reduction
by: Conneryd, Jonas, et al.
Published: (2025)

A Compendium of Subset Search Problems and Reductions relating to the Parsimonious Property
by: Bartlett, Celina Janet
Published: (2025)

The complexity of computing in continuous time: space complexity is precision
by: Blanc, Manon, et al.
Published: (2024)

A Fine-Grained Complexity View on Propositional Abduction -- Algorithms and Lower Bounds
by: Lagerkvist, Victor, et al.
Published: (2025)

On Finding Randomly Planted Cliques in Arbitrary Graphs
by: Agrimonti, Francesco, et al.
Published: (2025)

Complexity of Firefighting on Graphs
by: Althoetmar, Julius, et al.
Published: (2025)

Matrix-by-matrix multiplication algorithm with $O(N^2log_2N)$ computational complexity for variable precision arithmetic
by: Paszyński, Maciej
Published: (2024)

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

On Some Fundamental Problems for Multi-Agent Systems Over Multilayer Networks
by: Rosenkrantz, Daniel J., et al.
Published: (2025)

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

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

Eliminating Illusion in Directed Networks
by: Jana, Sougata, et al.
Published: (2026)

How to compute the volume in low dimension?
by: Cornelissen, Arjan, et al.
Published: (2025)