:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Doty, David, Heckmann, Ben
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity
Online Access:	https://arxiv.org/abs/2405.08649
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Robust predicate and function computation in continuous chemical reaction networks
by: Calabrese, Kim, et al.
Published: (2025)

Analog computation with transcriptional networks
by: Doty, David, et al.
Published: (2025)

Reverse-Robust Computation with Chemical Reaction Networks
by: Kini, Ravi, et al.
Published: (2026)

On the computational power of $C$-random strings
by: Milovanov, Alexey
Published: (2024)

Limit on the computational power of $\mathrm{C}$-random strings
by: Milovanov, Alexey
Published: (2026)

On the power of counting the total number of computation paths of NPTMs
by: Bakali, Eleni, et al.
Published: (2023)

Oracle separation of QMA and QCMA with bounded adaptivity
by: Ben-David, Shalev, et al.
Published: (2024)

Bounding the computational power of bosonic systems
by: Upreti, Varun, et al.
Published: (2025)

On the complexity of freezing automata networks of bounded pathwidth
by: Goles, Eric, et al.
Published: (2025)

A universal bound on the space complexity of Directed Acyclic Graph computations
by: Bilardi, Gianfranco, et al.
Published: (2024)

Is stochastic thermodynamics the key to understanding the energy costs of computation?
by: Wolpert, David, et al.
Published: (2023)

Stochastic thermodynamics of computation
by: Wolpert, David H.
Published: (2019)

Direct Product Theorems for Randomized Query Complexity
by: Ben-David, Shalev, et al.
Published: (2025)

Rice-like complexity lower bounds for Boolean and uniform automata networks
by: Goubault-Larrecq, Aliénor, et al.
Published: (2024)

Negations are powerful even in small depth
by: Cavalar, Bruno, et al.
Published: (2025)

Lower bounds for planar Arithmetic Circuits
by: Ramya, C., et al.
Published: (2025)

New Lower-bounds for Quantum Computation with Non-Collapsing Measurements
by: Miloschewsky, David, et al.
Published: (2024)

Time hierarchies for sublogarithmic-space quantum computation
by: Say, A. C. Cem
Published: (2025)

Exponential lower bound via exponential sums
by: Bhattacharjee, Somnath, et al.
Published: (2026)

Simple general magnification of circuit lower bounds
by: Atserias, Albert, et al.
Published: (2025)

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

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

On the power of adaption and randomization
by: Krieg, David, et al.
Published: (2024)

Depth lower bounds in Stabbing Planes for combinatorial principles
by: Dantchev, Stefan, et al.
Published: (2021)

Fast polynomial computations with space constraints
by: Grenet, Bruno
Published: (2025)

A computing machinery using a continuous memory tape
by: Oktar, Yigit
Published: (2023)

Oracle Separations for the Quantum-Classical Polynomial Hierarchy
by: Agarwal, Avantika, et al.
Published: (2024)

Separations in query complexity for total search problems
by: Ben-David, Shalev, et al.
Published: (2024)

Man, these New York Times games are hard! A computational perspective
by: Alberti, Alessandro Giovanni, et al.
Published: (2025)

Symmetric quantum computation
by: Castro-Silva, Davi, et al.
Published: (2025)

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

A note on Jerabek's paper "A simplified lower bound for implicational logic"
by: Gordeev, Lev, et al.
Published: (2026)

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

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

Monte Carlo to Las Vegas for Recursively Composed Functions
by: Al-Dhalaan, Bandar, et al.
Published: (2026)

A Compendium of Reductions: reductions.network
by: Grüne, Christoph, et al.
Published: (2025)

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

The power of quantum circuits in sampling
by: Blanc, Guy, et al.
Published: (2025)

QBF Merge Resolution is powerful but unnatural
by: Mahajan, Meena, et al.
Published: (2022)

Recursion and proof theoretical characterizations of small circuit classes with modulo counting via discrete differential equations (long version)
by: Antonelli, Melissa, et al.
Published: (2026)