:: Library Catalog

Saved in:

Bibliographic Details
Main Authors:	Calí, Andrea, Razgon, Igor
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity
Online Access:	https://arxiv.org/abs/2501.03710
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Decision DNNFs with imbalanced conjunction cannot efficiently represent CNFs of bounded width
by: Razgon, Igor
Published: (2025)

FPT Parameterisations of Fractional and Generalised Hypertree Width
by: Lanzinger, Matthias, et al.
Published: (2025)

Non-commutative linear logic fragments with sub-context-free complexity
by: Nishimiya, Yusaku, et al.
Published: (2025)

Quantum state testing with restricted measurements
by: Liu, Yuhan, et al.
Published: (2024)

A nearly-$4\log n$ depth lower bound for formulas with restriction on top
by: Wu, Hao
Published: (2024)

On complexity of substructure connectivity and restricted connectivity of graphs
by: Lü, Huazhong, et al.
Published: (2021)

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

On the complexity of Multipacking
by: Das, Sandip, et al.
Published: (2026)

Deterministic and Strongly Nondeterministic Decision Trees for Decision Tables from Closed Classes
by: Ostonov, Azimkhon, et al.
Published: (2023)

Hazard-free Decision Trees
by: Benson, Deepu, et al.
Published: (2025)

#P-hardness proofs of matrix immanants evaluated on restricted matrices
by: Miklos, Istvan, et al.
Published: (2021)

From FPT Decision to FPT Enumeration
by: Creignou, Nadia, et al.
Published: (2025)

Instance complexity of Boolean functions
by: Liu, Alison Hsiang-Hsuan, et al.
Published: (2023)

Unambiguous parity-query complexity
by: Gavinsky, Dmytro
Published: (2024)

Explaining the Ubiquity of Phase Transitions in Decision Problems
by: Jackson, Andrew
Published: (2025)

Search versus Decision for $\mathsf{S}_2^\mathsf{P}$
by: Fortnow, Lance
Published: (2025)

Between the deterministic and non-deterministic query complexity
by: Gerbner, Dániel
Published: (2019)

Boolean Circuit Complexity and Two-Dimensional Cover Problems
by: Cavalar, Bruno P., et al.
Published: (2025)

Phase Transitions in Decision Problems Over Odd-Sized Alphabets
by: Jackson, Andrew
Published: (2025)

Upper and Lower Bounds on $T_1$ and $T_2$ Decision Tree Model
by: Alhamdan, Yousef M.
Published: (2025)

On the complexity of embedding in graph products
by: Biedl, Therese, et al.
Published: (2023)

Some structural complexity results for $\exists\mathbb R$
by: Meer, Klaus, et al.
Published: (2025)

Unconventional complexity classes in unconventional computing (extended abstract)
by: Porreca, Antonio E.
Published: (2024)

The complexity of convexity number and percolation time in the cycle convexity
by: Lima, Carlos V. G. C., et al.
Published: (2024)

A new metric for evaluating the performance and complexity of computer programs: A new approach to the traditional ways of measuring the complexity of algorithms and estimating running times
by: Folea, Rares, et al.
Published: (2025)

Lower Bounds on Cardinality of Reducts for Decision Tables from Closed Classes
by: Ostonov, Azimkhon, et al.
Published: (2024)

A primer on the closure of algebraic complexity classes under factoring
by: Bhargav, C. S., et al.
Published: (2025)

Communication complexity of pointer chasing via the fixed-set lemma
by: Viola, Emanuele
Published: (2025)

Polynomial and analytic methods for classifying complexity of planar graph homomorphisms
by: Cai, Jin-Yi, et al.
Published: (2024)

On the complexity of covering points by guillotine cuts
by: Garijo, Delia, et al.
Published: (2026)

On Condensation of Block Sensitivity, Certificate Complexity and the $\mathsf{AND}$ (and $\mathsf{OR}$) Decision Tree Complexity
by: Nalli, Sai Soumya, et al.
Published: (2026)

Positive Univariate Polynomials: SOS certificates, algorithms, bit complexity, and T-systems
by: Bender, Matías, et al.
Published: (2025)

On one-way functions and the average time complexity of almost-optimal compression
by: Zimand, Marius
Published: (2024)

Average-case deterministic query complexity of boolean functions with fixed weight
by: Li, Yuan, et al.
Published: (2024)

Proof complexity of Mal'tsev CSP
by: Gaysin, Azza
Published: (2025)

Relations between monotone complexity measures based on decision tree complexity
by: Byramji, Farzan, et al.
Published: (2024)

Monitoring graph edges via shortest paths: computational complexity and approximation algorithms
by: Colli, Giordano
Published: (2025)

Circuit metaconstruction in logspace for Rice-like complexity lower bounds in ANs and SGRs
by: Goubault-Larrecq, Aliénor, et al.
Published: (2025)

Low-soundness direct-product testers and PCPs from Kaufman--Oppenheim complexes
by: O'Donnell, Ryan, et al.
Published: (2025)

Magic and communication complexity
by: Girish, Uma, et al.
Published: (2025)